問題2-21〜22

mapを使い、一段抽象の壁を作ってみるための問題です。
まずは、問題2-21の穴埋め問題です。

(define (map proc items)
  (if (null? items)
      '()
      (cons (proc (car items))
            (map proc (cdr items)))))

(define (square x) (* x x))

(define (square-list1 items)
  (if (null? items)
      '()
      (cons (square (car items))
            (square-list1 (cdr items)))))

(square-list1 (list 1 2 3 4))

(define (square-list2 items)
  (map square items))

(square-list2 (list 1 2 3 4))

=>(1 4 9 16)
=>(1 4 9 16)

次の問題2-22は、normal-order/applicative-order evaluationについて考えなければならない問題です。Reasonerの最初のコードの場合、iterに渡されるthingsがnullになるまで再帰処理が続いていく訳ですが、この繰り返し処理が終わるまでは、iterの中にあるconsは評価されないのが問題だと思いました。iterの中のnull判定に最初に引っかかってanswerが返される時、その実体は、square-listに入った直後に渡されるnilとなります。再帰処理が終わったら、徐々に元の処理に戻っていく過程でconsが評価されるため、逆順になってしまうのかと考えましたが、ここまで書いてみて頭がこんがらがってしまいました。評価順序を図に書いてみます。

(define (square x) (* x x))

(define (square-list3 items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items '()))

(square-list3 (list 1 2 3 4))

=>(16 9 4 1)

(cons (square (car (list 4))) '())
(cons (square (car (list 3 4))) (list 16))
(cons (square (car (list 2 3 4))) (list 9 16))
(cons (square (car (list 1 2 3 4))) (list 4 9 16))

=>(16)
=>(9 16)
=>(4 9 16)
=>(1 4 9 16)

squareが評価されるタイミングがこれでは正しくないような気がしますが、イメージをつかむ為には良い方法だと思いました。このあたりについても理解が曖昧なままなので、しっかりと抑えておきたいところです。
Reasonerの第二のコードが動かないことについては、現時点でははっきりとはわかりませんが、squareの評価タイミングが問題だということは、実行時のエラーメッセージを見るとわかります。

(define (square x) (* x x))

(define (square-list4 items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (cdr things))))))
  (iter items '()))

(square-list4 (list 1 2 3 4))

=>*: expects type <number> as 1st argument, given: (2 3 4); other arguments were: (2 3 4)

このあたりについては、後日考えてみることにします。