Haskell のリストが分からない。遅延評価も分からない。

Haskell のリストはシンタックスシュガーだらけ

a = []
b = [1]
c = [1,2]
d = [1..10]
e = [1..]
f = [1,3..]
g = [ x * x | x <- f ]

逆に分かりにくいので書き直す

a = []
b = (:) 1 []
c = (:) 1 ((:) 2 [])
d = ff 10
    where
        ff 0 = []
        ff i = (:) 1 (map (+1) (ff ((-) i 1)))
e = (:) 1 (map (+1) e)
f = (:) 1 (map ((+) ((-) 3 1) f)
g = map (\x->x*x) f

うん、なるほど

ついでに map と同じ事をする関数 mymap を作ってみる

mymap f []         = []
mymap f ((:) x xs) = (:) (f x) (mymap f xs)

map (*2) [1,2,3] -- => [2,4,6]

うんうん、なるほど

ついでに !! と同じ事をする関数 mybikkuribikkuri を作ってみる

mybikkuribikkuri []         i = throw $ ErrorCall "index too large"
mybikkuribikkuri ((:) x xs) i = if i == 0 then x
                                          else mybikkuribikkuri xs ((-) i 1)

[1,2,3] `mybikkuribikkuri` 2 -- => 3

うんうんうん、なるほど

じゃあ JS で書いてみっかあ（ぉぃ

// グローバルオブジェクトを _ 変数に代入
var _ = (function(){ return this })();

// [] 関数を作る
_['[]'] = function() { return [] };

// : 関数を作る
_[':'] = function(value) { return function(list) { return [value, list] } };

// 足し算関数
_['+'] = function(a) { return function(b) { return a + b } };

// 引き算関数
_['-'] = function(a) { return function(b) { return a - b } };

// 掛け算関数
_['*'] = function(a) { return function(b) { return a * b } };

// !! 関数
_['!!'] = function(xs) { return function(i) {
  if (xs.length == 0) throw Error('index too large');
  var x = xs[0]; xs = xs[1];
  return i == 0 ? x : _['!!'] (xs) (_['-'] (i) (1))
} };

// map 関数
_['map'] = function(f) { return function(xs) {
  if (xs.length == 0) return [];
  var x = xs[0]; xs = xs[1];
  return _[':'] (f (x)) (_['map'] (f) (xs))
} };

_['a'] = function() { return _['[]']() };

_['b'] = function() { return _[':'] (1) (_['[]']()) };

_['c'] = function() { return _[':'] (1) (_[':'] (2) (_['[]']()) ) };

_['d'] = function() {
  var ff = function(i) { return (i == 0) ?
                                  _['[]']() :
                                  _[':'] (1) (_['map'] (_['+'] (1)) (ff (_['-'] (i) (1)))) };
  return ff (10) };

_['e'] = function() { return _[':'] (1) (_['map'] (_['+'] (1)) (_['e']())) }

_['f'] = function() { return _[':'] (1) (_['map'] (_['+'] (_['-'] (3) (1))) (_['f']())) }

_['g'] = function() { return _['map'] (function(x){ return _['*'] (x) (x) }) (_['f']()) }

おおおお。なんだこれ！？超わかりやすいじゃん JavaScript 愛してる！
あ、いたっ＞＜　そこ、ゴミ投げないで＞＜

ちょっと実行してみる

_['d']() // => [1, [2, [3, [4, [5, [6, [7, [8, [9, [10, []]]]]]]]]]]
_['!!'] (_['d']()) (2); // => 3

これはうまくいく
でも

_['!!'] (_['e']()) (2);

は、無限ループに陥ってしまう。
つまり、これでは Haskell のリストは完全には再現できていないことになる。

もうちょっと考えてみる

なんとなく、遅延評価が近いところまできている気がする

何故、無限ループに陥ったか

理由は !! 関数やコロン関数に引数を渡す前にリストを評価したからだ。
ということは、 map 関数はリストを受け取ってはいけないということか。
リストを返す関数を受け取ればいい

/*** このコードは動かない ***/

var _ = (function(){ return this })();
_['[]'] = function() { return [] };
_[':'] = function(value) { return function(list) { return [value, list] } };
_['+'] = function(a) { return function(b) { return a + b } };

_['map'] = function(f) { return function(xs) { // ここで、 xs は関数とする
  if (xs.length == 0) return [];

  /*** ここで xs から x を取り出したい ***/

  return _[':'] (f (x)) (_['map'] (f) (xs))
} };

_['!!'] = function(xs) { return function(i) { // ここで、 xs は関数とする
  if (xs.length == 0) throw Error('index too large');

  /*** ここで xs から x を取り出したい ***/

  return i == 0 ? x : _['!!'] (xs) (_['-'] (i) (1))
} };

_['e'] = function() { return _[':'] (1) (_['map'] (_['+'] (1)) (_['e'])) } // ここで map にはリストを返す関数を渡した

xs から x を取り出すことができない＞＜

何故だ＞＜

Haskell だとデータ構築子 (:) で作ったものはパターンマッチングで取り出せる

xs = (:) 1 ((:) 2 []) -- => [1, 2]

get ((:) x xs) = x -- このパターンマッチングでデータ構築子で作ったデータから元のデータを取り出せる

main = putStrLn (show (get xs)) -- => 1

データ構築子はただの関数じゃないのか？

α変換 β変換

いやー。名前だけ聞いたらものすごい難しそうで避けて通ってたけど勉強してみたら以外に当たり前のことだった。
Wikipedia でお勉強

α変換

束縛変数（引数になっている変数）の名前を別の名前に変えること

function(x){ return (function(x){ return x })(x) }
// ↓ α変換
function(y){ return (function(x){ return x })(y) }
// ↓ α変換
function(y){ return (function(z){ return z })(y) }
// ↓ α変換
function(z){ return (function(z){ return z })(z) }

こんな感じか。
条件があって

1. 変換後の名前が、自由変数（引数になっていない変数）の名前と被っちゃダメ。
2. その束縛変数を持つラムダに内包されたラムダが変換前の名前の束縛変数を持つ場合はその中の変数名は変換しない。

おk

β変換

ラムダを式に適用しているときに、そのラムダの束縛変数を、適用されている式に「置き換え」てラムダを消す。（言葉で説明できない＞＜
また、束縛変数が未使用な場合は η 変換というらしい。
ちょっとチャーチ数の succ(1) を 2 に β変換してみる

(function(n){ return (function(f){ return function(x){ return f(n(f)(x)) }}})(function(f){ return function(x){ return x }})　// succ(1)
// ↓ β変換
function(f){ return function(x){ return f((function(f){ return function(x){ return x }})(f)(x)) }}
// ↓ η変換
function(f){ return function(x){ return f((function(x){ return x })(x)) }}
// ↓ β変換
function(f){ return function(x){ return f(x) }} // 2

なるほどー。
条件は

1. 適用されている式の自由変数が束縛変数になっちゃダメ＞＜

ということらしい