wiki:Dev/lambda

λ計算に纏わる資料

recursion

  • lambdaを使った無名再帰は可能か?
    • たとえば以下のschemeコード
      (define (add n)
          (local
              (
                  ;; n-th composition of given funtion
                  ;;   repeat : func num -> func(func(func(func(func(..)))))
                  (define (repeat f n)
                      (cond
                          [(= n 0) (lambda (x) x)]
                          [else
                              (lambda (x)
                                  (f 
                                      (
                                          (repeat f (- n 1))
                                          x
                                      )
                                  )
                              )
                          ]
                      )
                  )
              )
              (repeat add1 n)
          )
      )
      
    • 上記コードにより以下が示される
      > ((add 4) 10)
      14
      
    • ここで、local内で定義されているrepeatを無名関数にすることは可能か?
      1. Perler的発想であれば、lambdaが暗黙的に$_のような変数(?)に代入を行い、それをlambdaの中で再帰的に呼ぶようにすれば可能ではないか。 (thx to twitter:VienosNotes)
  • wikipetan:ラムダ計算#.E5.86.8D.E5.B8.B0
    ラムダ計算では自分自身を含む関数は定義できない。
    
    • とあるので、本質的に不可能?
Last modified 7 years ago Last modified on Nov 28, 2010 10:11:17 PM