SICP по-русски

Еще одно интересное упражнение. Сразу вспоминается Пифагор со знаменитым высказыванием “всё есть число”. В данном случае пару неотрицательных целых чисел можно представить как единственное число. Для этого cons будет вычислять произведение 2^a3^b, как и предложено в условии (на самом деле вместо 2 и 3 можно использовать любые два взаимно простых числа). Процедуры car и cdr будут просто вычислять кратность двойки и тройки соответственно в разложении своего аргумента на простые сомножители (я обзову это вычисление факторизацией).

(define (cons a b)
  (* (power 2 a) (power 3 b)))

(define (car pair)
  (factor 2 pair))

(define (cdr pair)
  (factor 3 pair))

Для реализации возведения в степень и факторизации я выбрал простые алгоритмы, порождающие, однако, итеративные процессы. Можно также построить и более эффективные по сложности вычислений алгоритмы, что для возведения в степень уже обсуждалось в разделе 1.2.4.

(define (factor base value)
  (define (factor-iter value counter)
    (if (= (remainder value base) 0)
        (factor-iter (/ value base) (+ counter 1))
        counter))
  (factor-iter value 0))

(define (power base exponent)
  (define (power-iter base counter product)
    (if (= counter 0)
        product
        (power-iter base (- counter 1) (* base product))))
  (power-iter base exponent 1))

Это упражнение позволяет взглянуть на данные сложной структуры под еще одним интересным углом. Если в предыдущем упражнении мы сводили составные данные к процедурам, то в этом идет сведение к простейшим данным - числам.