関数だけでリストを作った

今日のお昼休みの話題は、リストがないときにどうやってリスト的なモノを作るか→タプルでLispのconsに相当することをやればいい→じゃあタプルも無かったらどうか→チャーチ的な方法で関数だけでも作れるはず→じゃあ作ってみよう

作れるはずってことしか記憶になくてどうやって構築するのかわからなかったのだけどとりあえずノートを出してごにょごにょしてたらできた。要するに1番目の引数を返す関数と2番目の引数を返す関数が構築出来ればいいんだからfst = ^x. Kx, snd = ^x. Iなわけですね。KとIはそれぞれKコンビネータとIコンビネータIbisを使って実際に挙動を確認してみた:

Online interpreter
Ibis Interpreter
> let id = fun x -> x
- : ('a -> 'a) = <closure>
> let const = fun x -> (fun y -> x)
- : ('a -> ('b -> 'a)) = <closure>

> let fst = fun x -> const x
- : ('a -> ('b -> 'a)) = <closure>
> let snd = fun x -> id
- : ('a -> ('b -> 'b)) = <closure>
> let cons = fun x -> (fun y -> (fun z -> z x y))
- : ('a -> ('b -> (('a -> ('b -> 'c)) -> 'c))) = <closure>

> let list1 = cons 1 (cons 2 (cons 3 id))
- : ((int -> (((int -> (((int -> (('a -> 'a) -> 'b)) -> 'b) -> 'c)) -> 'c) -> 'd))
-> 'd) = <closure>
> list1 fst
- : int = 1
> list1 snd fst
- : int = 2
> list1 snd snd fst
- : int = 3