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

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