#9LISP の003回のチャレンジ問題の回答例

1. Schemeによる記号処理入門 より
   
   
   
   • 次のコードの評価を考えてみる
     
     

     
     (((lambda (x)(lambda (x)(+ x 1))) 2) 4)
     

     
     
     
   
   
   • 回答例:
     クロージャの問題。
     ラムダラムダだと見づらいんですが、define使って書き直して見た方が直感的です。
     題意の大枠の手続きの部分は、引数を一つ取り、手続きを返す高階手続き
     
     

     (define (hoge x) (lambda (x) (+ x 1)))

     
     
     と等価です。
     この手続きhogeに引数2を与えても、内側のラムダ式が返されるだけなんで、結果形式的には、題意は
     
     

     ((lambda (x) (+ x 1)) 4)

     
     
     として実行されます。また、クロージャにより、内側のxは外側のxから保護されているので丸っきり別物です。レキシカル・スコーピングですね。
     結果、5が返ります。
     この手の問題は、Schemeでは定番なんですけど、実はあんま好きじゃないです(笑)。「見づらさ」がとにかくトリッキーなだけ、って印象なんです。
     反面、ANSI Common Lispではこう言う問題は見かけませんね。
     ちなみに、題意のコードの「スタイル」ってのは実はletのマクロ(として実装されてれば、と言う話ですが)の展開形に他なりません。
     実は題意のコードは、
     
     

     
      ((let ((x 2))
          (lambda (x) (+ x 1)))
        4)
     

     
     
     と等価である、って事を付け加えておきます。
     これはletにより、xが2に束縛されていますが、ボディー部のxは外側のxと全く関係なく存在し、結果let式はボディーのラムダ式を「ただ返してる」に過ぎないのです。
     
   
   
   
   


2. SICP より
   
   
   
   • 組み込みの特殊形式if と同じ動作をするnew-if 手続きを定義してみる
     
     
     
     • ifがなぜ特殊形式であるか考えてみる
     
     
   • 回答例:
     多少インチキですが、題意の通りだとすると、
     
     

     
     (define-syntax new-if
       (syntax-rules ()
         ((_ pred then-clause else-clause)
          (cond (pred
          then-clause)
         (else
          else-clause)))))
     

     
     
     でしょう。
     ifが特殊形式である理由は、普通の手続きだと、ボディの評価を始める前に引数の評価を全て終えてからボディが実行される、からです。
     普通は問題が生じないのですが、再帰なんかの場合、「先に引数を評価」してしまうと、引数がいつまでも展開されていって、終了地点に到達しません。これを避ける為には条件に従って引数を評価したりしなかったり、と言う仕組みが必要になります。
     これがifが特殊形式でなければならない理由です。
     
   
   
   
   
3. The Little Schemer より
   
   
   
   • 引数がatomであるか判定するatom?手続きを定義してみる
     
     
     
     • 回答例:
       
       

       
       (define (atom? x)
           (not (pair? x)))
       

       
       
       これはちょっと微妙な問題ですね(笑)。なんせANSI Common Lispと違って、Schemeにはアトムが定義されていません。
       ANSI Common Lisp上のatomの定義は「コンスじゃないもの」です。コンスかどうか調べる述語がANSI Common Lispではconspで、Schemeではpair?にあたります。
       
     
     
     
     
   
   
   • 引数のリストの要素がすべてatomであるか判定するlat?手続きを定義してみる
   
   
   • 回答例:
     
     

     
     (define (lat? ls)
       (call/cc
        (lambda (return)
          ;; 注:実は Scheme には atom と言う概念はありません
          ;; ANSI Common Lisp の定義に従うと
          ;; atom は pair じゃないもの、でO.K.です
          ;; しかし、CL では空リストが偽を表すのに対し、
          ;; Scheme では空リストは偽を表さず #t となります
          ;; その為、両者の計算結果に整合性が出ないので、
          ;; atom? を弄るのではなく、 lat? の最初で
          ;; 引数リスト ls の pair? 判定を加えました。
          ;; (ただし、論理的に必要か、と言われると疑問です)
          (and (pair? ls)
        (map (lambda (x)
        (let ((it (atom? x)))
          (if it it (return it)))) ls)
        #t))))
     

     
     
     若干トリッキーな書き方をしているように見えますが、ポイントは四つです。
     
     
     
     1. 高階手続きmapで引数のリストの各要素にatom?を適用する。
     
     
     2. 1番目の「要素への適用」で、どっかで#fが返ったら即座にcall/ccで処理を中断して#fを持って脱出する。結果、必ずしもリストの末尾まで走査しなくても良い。
     
     
     3. ポールグレアムのOn Lispに載っているアナフォリック・マクロの影響を受けてる。ただし、R5RSの衛生的マクロではアナフォリック・マクロは書けないので、アイディアだけ借用。述語による判定結果をitに束縛して、if内で使いまわしている。
     
     
     4. mapで引数リストを末尾まで走査し終わればリストの要素は全てatomである。またその結果は論理的には#tとなる。そのまま返しても論理上は構わないが、一応仕様に従って#tか#fを返すようにした。鍵はandでmapがリスト末尾まで走査終了＝#tなので、andの第二引数である#tが評価値として返される。
     
     
     
     
   
   
   • 引数で指定されたatomが引数のリスト内に存在するか判定するmember?手続きを定義してみる
   
   
   • 回答例:
     
     

     
     (define (member? atom ls)
       (call/cc
        (lambda (return)
          (not (map (lambda (x)
        (let ((it (eqv? atom x)))
          (if it (return it) it))) ls)))))
     

     
     
     解法のネタとしては前出のやり方と同じです。call/ccでの脱出を用いています。前問と逆で、itが#tの場合にitを持ったまま計算を脱出します。
     mapが引数リストの末尾まで走査してリストを返した場合、返り値のリストは論理的には#tとなります。従って、そのリストをnotで否定すれば与題の解となります。
     
   
   
4. Schemeで書いてみる




• FizzBuzz


• 回答例:
  

  
  (define (fizzbuzz ls)
    (map
     (lambda (x)
       (cond
        ((zero? (modulo x 15))
         "Fizz Buzz")
        ((zero? (modulo x 5))
         "Buzz")
        ((zero? (modulo x 3))
         "Fizz")
        (else
         x))) ls))
  

  
  
  これはまあ、定型的な解き方ですね。
  


• 階乗


• 回答例:
  
  

  
  (define (factorial k)
    (let loop ((n k) (return 1))
      (if (zero? n)
   return
   (loop (- n 1) (* return n)))))
  

  
  
  これも定番ですね。
  


• フィボナッチ数


• 回答例:
  
  

  
  (define (fibonacci n)
    (let loop ((count 0) (f0 0) (f1 1))
      (if (= n count)
   f0
   (loop (+ count 1) f1 (+ f0 f1)))))
  

  
  
  フィボナッチ数列は良く「複雑で計算コストがかかる再帰の例」として挙げられますが、実際は末尾再帰として上のように書くことが可能です。引数内処理を試みて、引数をどんどんズラしていくイメージで書けばそんなにコストはかからないでしょう。
  


• コラッツの問題


• 回答例:
  
  

  
  (define (a n)
    ;; ローカル手続きで f を定義
    (define (f n)
      (if (even? n)
   (/ n 2)
   (+ (* 3 n) 1)))
    ;; n が (* 3 (expt 2 53)) までは1へと収束する事が確かめられている
    ;; 基本的に未解決問題なので、(= i 1) が完全なベースケースかどうかは不明
    (let loop ((i n) (ls '()))
      (let ((ls0 (cons i ls)))
        (if (= i 1)
     (reverse ls0)
     (loop (f i) ls0)))))
  

  
  
  これは初見の問題でした。
  が、数学的なアルゴリズムは実は実装そのものはそんなに難しく無いですね。何せ、数学的な定義式を「そのまま」S式に置き換えれば一丁上がり、ですから。
  Wikipediaの指示に従って、手続きfを定義し、それを局所手続きとして実装しています。
  


• アッカーマン関数


• 回答例
  
  

  
  (define (ack m n)
    (cond
     ((zero? m)
      (+ n 1))
     ((zero? n)
      (ack (- m 1) 1))
     (else
      (ack (- m 1) (ack m (- n 1))))))
  

  
  
  アッカーマン関数はマジで計算負荷が大きい手続きとなります。あんまり大きい数を与えると処理が終わらないでしょう。
  定義的に言うと、「数式をそのままS式に置き換えた」だけで末尾再帰の式となります。
  ただし、形式的には末尾再帰ですが、引数内でまた末尾再帰が起こり、スタックが開放されないので、言わばこれは「最適化できない」末尾再帰の典型例だと思います。