lambda式についてリストについて

lispはリストというとすぐにリストを思い浮かべる。リストというのはこういう構造。consを重ねて創り出して、carとcdrで分解する。

;; cons
(list 1 2 3) ; => (1 2 3)

(cons 1 (cons 2 (cons 3 '()))) ; => (1 2 3)

(use srfi-1)
(cons* 1 2 (cons 3 '())) ; => (1 2 3)

;; car,cdr
(car (cons 1 2)) ; => 1
(cdr (cons 1 2)) ; => 2

関数定義も見掛け上はリストのように見える。

(define (car? x y)
  (equal? (car y) x))

(car? 1 (cons 1 2)) ; => #t
(car? 2 (list 1 2)) ; => #f

関数は引数とその利用方法が書かれた名前のついた何かだ。名前のついていないものは無名関数と言われる。ラムダ式とか単にラムダと呼ばれることもあるかもしれない。

ということは、名前のついたラムダは関数で、それもまた見掛け上はリストのように見える。

((lambda (x y) (equal? x (car y))) 1 (cons 1 2)) ; => #t

変数に名前をつけるのはdefineなので関数定義は実質ラムダと変数束縛の組み合わせに過ぎないとも言える。

(define x 10)
(+ x x) ; => 20

(define car? (lambda (x y) (equal? x (car y))))
;;(define (car? x y) (equal? x (car y)))

(car? 1 (list 1 2 3)) ; => #t

関数を組み合わせて関数を作ることができる。大きく複雑な処理の内容を小さな関数の組み合わせとして記述することもあるだろうし。小さな関数を組み合わせて、大きな処理を行う関数を創り出していくこともあるかもしれない。どちらにせよ、関数を組み合わせて関数を作ることができるし、逆に与えられた関数を小さな関数に分解することもできる。

(define (add x y)
  (+ x y))

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

(define (ints i j fn)
  (if (> i j) 0 (fn i (ints (+ i 1) j fn))))

(define (sum i j)
  (ints i j +))

(define (inc x y)
  (+ 1 y))

(define (count i j)
  (ints i j inc))

(define (ave i j)
  (/ (sum i j) (count i j)))

(define (left-only f)
  (lambda (g) (lambda (x y) (g (f x) y))))

(define (sqave i j)
  (ints i j ((left-only square) add)))

(define (V i j)
  (- (sqave i j) (ave i j)))

(count 1 10) ; => 10
(sum 1 10) ; => 55
(V 1 10) ; => 759/2

リストを作る機能を持った関数というものがあるらしい。consと言われている。組み込みの関数として定義されている。そしてそれは組み込みではあるものの関数であることには代わりがない。ここで、もう少し強いことが言えたら面白いかもしれない。

前者であるならすこしつまらない。だからこうでないことを望む

「リストというデータ構造がある。このリストを作成するために組み込みの関数consがある。リストは組み込みの関数を使う以外で作ることができないし、その組み込みで提供されている関数は1つ下のレイヤーに降りない限りその振る舞いをシミュレートすることはできない。つまり組み込みの関数は暗黙のビルディングブロック(構成要素)として提供されていて、それを天下り式に使うことしかできない。」

これから使ってみたいデータ構造があるとして、それがどのようにして作られているのか知ることができないというのはつまらない。そしてこうであることを望む。

「リストというデータ構造がある。それを構成／アクセスするための関数が用意されている。その関数はさらに小さな関数の組み合わせでできている(関数を組み合わせて作ることができる)。なぜなら、関数は関数を作ることができて、それは逆に言えば関数は関数に分解できるということであるから。」

もちろん、分解できる最小の単位に限りはあるかもしれない。だから関数を分解するにつれて分解不能な関数にぶち当たるという予想はそうおかしなことではないし、正しい。でも、リストの構成要素のcons,car,cdrが関数それもラムダで定義することができれば面白い。

やってみよう。

consは以下のような関数。2つの引数を取って、その2つの引数を保持する何かを返す。
consと同じような動作をする関数cons:を考えてみる。ここで最後に「:」をつけたのは、組み込みの関数と区別をつけるため。

;; cons: :: a -> a -> (a, a) ?
(cons: 1 2) => ?

cons:を2つの引数に適用すると何かが返ってくるらしい。その何かを取り扱う関数としてcarとcdrが用意されている。
以下のような振る舞いをするのが正しい。

(car: (cons: 1 2)) => 1 
(cdr: (cons: 1 2)) => 2

形を見ずに動作だけを見ると、以下のような動作をしていた。

cons 2つの引数を取って何かを返す。
car 2つの引数のうち1つ目の引数を返す
cdr 2つの引数のうち2つ目の引数を返す

下2つのような振る舞いをする関数を定義してみよう。そうするとリストを関数で定義することに近づけるかもしれない。
上の通りの考え方でcar,cdrらしいものを定義してみる。

;; %car:: a -> b -> a
(define (%car x y) x)
;; %cdr:: a -> b -> b
(define (%cdr x y) y)

(%car 1 2) => 1
(%cdr 1 2) => 2

当然このままではつかえないし、cons:と%car,%cdrを結びつけることができない。何よりcons:はまだ定義もしていない。
とりあえず、分かっていることとできることからcons:になりそうなものを作ってみることにする。

cons:は引数を2つとる。そして2つの引数を保持する何かを返す。今までの話から構成要素には関数以外出てきていない(数値などを抜かして)。
つまり、2つの引数を保持する何かというのは関数ということになる。

関数を返す関数ということは、特に名前が着いていなければ、戻り値としてラムダを返すということ

(define (cons: x y)
  (lambda ...))

今度は%car,%cdrを考えてみる。%car,%cdrは2つの引数を取ってどちらか一方を返す関数だった。
おそらく、cons:の戻り値として返す何かも2つの引数をとる関数なのかもしれない。

;; cons: a -> b -> (a -> b -> ?)
(define (cons: x y)
  (lambda (z) (z x y)))

ここでは2つの引数をとる関数fを引数に取るラムダを返してみた。
consとcar,cdr系の関数との引数と戻り値の形が一致した。2つの関数を組み合わせて使える。

((cons: 1 2) %car) ; => 1
((cons: 1 2) %cdr) ; => 2

car,cdrと振る舞いは一緒になった。しかし利用する際の形が違う。

ここでcons:を適用している部分も何らかの関数fだと考えてみる。

((lambda (f) (f %car))
 (cons: 1 2)) ; => 1
((lambda (f) (f %cdr))
 (cons: 1 2)) ; => 2

そしてcons:の適用の部分を単なる引数として考えてみることにする。

(lambda (arg)
  ((lambda (f) (f %car))
   arg))

また元々のcar,cdrは以下のような形式で使うのだった。

(car: (cons: 1 2))

car:,cdr:はひとつの引数を取る。なので以下のような形式の関数になりそう。

(define (car: arg)
  ((lambda (f) (f %car))
   arg))
(define (cdr: arg)
  ((lambda (f) (f %cdr))
   arg))

使ってみる。

(car: (cons: 1 2)) ; => 1
(cdr: (cons: 1 2)) ; => 2

できている。すべてのラムダを展開すると以下のようになっている。

(define (cons: x y)
  (lambda (z) (z x y)))

(define (car: arg)
  ((lambda (f)
     (f (lambda (x y) x)))
   arg))

(define (cdr: arg)
  ((lambda (f)
     (f (lambda (x y) y)))
   arg))

;; 引数としてラムダを直接渡すのが嫌なら
(define (car: arg)
  (((lambda (g)
      (lambda (f) (f g)))
    (lambda (x y) x))
   arg))

(define (cdr: arg)
  (((lambda (g)
      (lambda (f) (f g)))
    (lambda (x y) y))
   arg))

あとは何でもできる。(リストに他ならないので）

空(nil)かどうかだけは判断できるようにする。もちろん効率は無視。

(define (nil? x) (eq? x 'nil))

(nil? 'nil) ; => #t
(nil? (cdr (cons 1 'nil))) ; => #t

再帰を禁止しても、あとは何でもできる。

(define (foldr: kons knil xs) ;; やりたければYコンビネータで
  ((lambda (g kons knil xs)
     (g g kons knil xs))
   (lambda (g kons knil xs)
     (if (nil? xs)
         knil
         (kons (car: xs)
               (g g kons knil (cdr: xs)))))
   kons knil xs))

(define (unfold: p f g seed)
  ((lambda (k p f g seed)
     (k k p f g seed))
   (lambda (k p f g seed)
     (if (p seed)
         'nil
         (cons: (f seed)
               (k k p f g (g seed)))))
   p f g seed))

(define (sum: xs)
  (foldr: + 0 xs))
(define (ints: n)
  (unfold: (lambda (x) (> x n))
           (lambda (x) x)
           (lambda (x) (+ x 1))
           1))

(sum: (ints: 10)) ; => 55

filterとかmapも定義して組み合わせ（順列)を計算したり。

(define (filter: p xs)
  (foldr: (lambda (x r) (if (p x) (cons: x r) r))
          'nil xs))

(define (map: f xs)
  (foldr: (lambda (x r) (cons: (f x) r))
          'nil xs))

(define (append: xs ys)
  (foldr: cons: ys xs))

(define (append-map: f xs)
  (foldr: append: 'nil (map: f xs)))

(define (delete: x xs)
  (filter: (lambda (y) (not (equal? x y))) xs))

(define (permutation: n xs)
  ((lambda (g n xs)
     (g g n xs))
   (lambda (g n xs)
     (if (<= n 1)
         (map: (lambda (x) (cons: x 'nil)) xs)
         (append-map:
          (lambda (x)
            (map: (lambda (ys)
                    (cons: x ys))
                  (g g (- n 1) (delete: x xs))))
          xs)))
   n xs))

動く。

;; 普通のリストに戻す(1階だけ)
(define (view xs)
  (foldr: cons '() xs))

((compose (map$ view) view)
 (permutation: 2 (cons: 1 (cons: 2 (cons: 3 (cons: 4 'nil))))))
 ; => ((1 2) (1 3) (1 4) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (4 1) (4 2) (4 3))

misc

if文もラムダでかける。数もチャーチ数使えば。比較演算が分からない。