Haskell のリストと遅延評価が少し分かった

いろいろ試行錯誤をしていて

JavaScript の関数を作って呼び出すのと Haskell のそれとの決定的な違いを見つけた。
それは、たぶんものすっごい単純で当たり前なことだけど、これが分かったとたんに僕の周りのピースが一気に繋がったので、恥をしのんで書く。

僕は以下のように脳内変換していて

a = 1
iszero i = if (i == 0) then True else False

Javascript

a = function() { return 1 }
iszero = function(i) { return i()/*評価は関数呼出し*/ == 0 ? True : False }

// True False はこう
True = function() { return true }
False = function() { return false }

実は、これは全然間違っていて

その間違いが JavaScript の関数と Haskell の関数の違いだということが分かった

例えば、以下で

a = 1
b = a

c = if b = 1 then True else False

c を呼び出すと当然 True になる。
しかし、これを JavaScript でやると

a = function() { return 1 }
b = function() { return a }

c = function() { if (b()/*評価したつもり*/ = 1) then True else False }

b() は function() { return 1 } を返すので、 Haskell における評価とは違う。

で、 Haskell の遅延評価をするとは JS 的にはどう表現すればいいか

/** すべての JS のオブジェクトで e という「値の評価」メソッドを使えるようにする。 **/

// 関数じゃない場合はそのまま返す
// （this.valueOf() の返す値はキホンは this と同じ）
// （valueOf を使ったのは、プリミティブ値のオブジェクト化対策）
Object.prototype.e = function() { return this.valueOf() };

// 引数が 0 個じゃない関数の場合はそのまま返す
// 引数が 0 個の関数の場合は呼び出して、更にそれを評価する。
Function.prototype.e = function() { return this.length != 0 ? this : this().e() };

a = function() { return 1 }
b = function() { return a }

c = function() { return b.e()/*評価！*/ == 1 ? True : False }

// True False はこう
True = function() { return true }
False = function() { return false }

c を評価してみる。

alert(c.e()); // => true

キタコレ

そして、もう一個見つけたこと

Haskell の遅延評価は、「必要なときにだけ行われる」という風に言われているが、必要なときというのは「パターンマッチング」と「if 式などの分岐」のときだけだと分かった。
流れが変わるときに具体的な値が必要になる。うんうんうん！そうだ。分かってきた！

さらに、もう一個見つけたこと

Haskell の関数適用

a b c

は
JavaScript の

a (b) (c);

ではなく

a (function() { return b }) (function(c) { return c });

だ

さらに、もう一個見つけたこと

引数を付けて呼び出した時は、その上に被っている「何にもしない引数なしの関数」は無視されなければならない＞＜
JavaScript の関数適用では乗り越えられない＞＜

var a = function() {
  return function(x) { 
    return x;
  }
};

a(1) // Haskell での関数だと、ここで 1 が直接 x に渡るような感じ

これをやる方法は JavaScript の関数適用をまったく使わないという感じになるんだろう。
このエントリーではめんどいのでやらない。
（引数の型が関数の場合に引数を function() { return ... } で囲まないことにして逃げる＞＜）

もう一回このエントリーの Haskell のリストを全部 JavaScript にしてやるぜ！

あのときのオラとは違うぜ

これを

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

JavaScript に直すお＞＜

// 最初のほうに書いたやつ
Object.prototype.e = function() { return this.valueOf() };
Function.prototype.e = function() { return this.length != 0 ? this : this().e() };

// log 用
log = function(e) { 
  console.log(e.e()); // *評価* して表示
}


/** 型を作る **/

// data [] a = [] | (:) a ([] a)
EndOfList = function() { return [] };
List = function(x) { return function(xs) { return [x, xs] } };


/** 演算子を定義 **/

// (==) :: Integer -> Integer -> Boolean
eq = function(a) { return function(b) { return a.e() == b.e() } };

// (-) :: Integer -> Integer -> Integer
sub = function(a) { return function(b) { return a.e() - b.e() } };

// (+) :: Integer -> Integer -> Integer
add = function(a) { return function(b) { return a.e() + b.e() } };

// (*) :: Integer -> Integer -> Integer
mul = function(a) { return function(b) { return a.e() * b.e() } };


/** リスト操作関数を定義 **/

// (!!)              :: [] a -> Integer -> a
// (!!) ((:) x xs) i = if i == 0 then x else (!!) xs ((-) i 1)
get = function(xs) { return function(i) {

  /* ここからパターンマッチ */
  xs = xs.e(); // パターンマッチ時に *評価* される(head と tail の分割する部分の評価だけ。リストの中身の値の評価はない)
  if (xs.length == 0) throw Error('index too large'); 
  var x = xs[0]; xs = xs[1]; 
  /* ここまでパターンマッチ */

  return eq(function() { return i })(function() { return 0 }).e() ? x : get(function() { return xs })(function() { return sub(function() { return i })(function() { return 1 }) }); // if の条件部は *評価* される
} };

// map              :: (a -> b) -> [] a -> [] b
// map f []         = []
// map f ((:) x xs) = (:) (f x) (map f xs) 
map = function(f) { return function(xs) {

  /* ここからパターンマッチ */
  xs = xs.e(); // パターンマッチ時にここだけ評価されるから
  if (xs.length == 0) return xs;
  var x = xs[0]; xs = xs[1];
  /* ここまでパターンマッチ */

  return List(function() { return f(function() { return x }) })(function() { return map(f)(function() { return xs }) })
} };



/** 各種リストを定義 **/


/*** 1 個目 ***/
// a = []
a = function() { return EndOfList };

// a[0] -- Error
try { log(get(function() { return a })(function() { return 0 })); } catch(e) { log(e) }


/*** 2 個目 ***/
// b = [1]
// b = (:) 1 []
b = function() { return List(function() { return 1 })(function() { return EndOfList }) };

// b[0] -- => 1
log(get(function() { return b })(function() { return 0 }))
// b[1] -- Error
try { log(get(function() { return b })(function() { return 1 })); } catch(e) { log(e) }


/*** 3 個目 ***/
// c = [1,2]
// c = (:) 1 ((:) 2 [])
c = function() { return List(function() { return 1 })(function() { return List(function() { return 2 })(function() { return EndOfList }) }) };

// c[0] -- => 1
log(get(function() { return c })(function() { return 0 }))
// c[1] -- => 2
log(get(function() { return c })(function() { return 1 }))
// c[2] -- Error
try { log(get(function() { return c })(function() { return 2 })) } catch(e) { log(e) }


/*** 4 個目 ***/
// d = [1..10]
// d = ff 10
//     where
//         ff 0 = []
//         ff i = (:) 1 (map (+1) (ff ((-) i 1)))
d = function() {
  var ff = function(i) { return eq(function() { return i })(function() { return 0 }).e() ? // ここで *評価* する
                                  EndOfList :
                                  List(function() { return 1 })(function() { return map(add(function() { return 1 }))(function() { return ff(function() { return sub(function() { return i })(function() { return 1 }) }) }) }) };
  return ff(10) };

// d[0] -- => 1
log(get(function() { return d })(function() { return 0 }))
// d[1] -- => 2
log(get(function() { return d })(function() { return 1 }))
// d[5] -- => 6
log(get(function() { return d })(function() { return 5 }))
// d[9] -- => 10
log(get(function() { return d })(function() { return 9 }))
// d[10] -- Error
try { log(get(function() { return d })(function() { return 10 })) } catch(e) { log(e) }


/*** 5 個目 ***/
// e = [1..]
// e = (:) 1 (map (+1) e)
e = function() { return List(function() { return 1 })(function() { return map(add(function() { return 1 }))(function() { return e }) }) }

// e[0] -- => 1
log(get(e)(0))
// e[99] -- => 100
log(get(e)(99))


/*** 6 個目 ***/
// f = [1,3..]
// f = (:) 1 (map ((+) ((-) 3 1) f)
f = function() { return List(function() { return 1 })(function() { return map(add(function() { return sub(function() { return 3 })(function() { return 1 }) }))(function() { return f }) }) }

// f[0] -- => 1
log(get(f)(0))
// f[1] -- => 3
log(get(f)(1))
// f[10] -- => 21
log(get(f)(10))


/*** 7 個目 ***/
// g = [ x * x | x <- f ]
// g = map (\x->x*x) f
g = function() { return map(function(x){ return mul(function() { return x })(function() { return x }) })(function() { return f }) }

// g[0] -- => 1
log(get(g)(0))
// g[1] -- => 9
log(get(g)(1))
// g[10] -- => 441
log(get(g)(10))

うおおおおお

やっとできたあああああああああ（涙）
無限リストも出来たし、遅延評価もできたー＞＜うれしすぎるーー＞＜＞＜

まとめ

遅延評価について

評価とは式が無引数関数の場合に呼出し続けること
遅延とは引数がそのまま値を返す無引数関数で囲まれること
関数適用が行われたときに外側にある「何にもしない引数なしの関数」は無視される

たぶん、間違ってるけど今の理解はこんな感じ。
未来の自分は理解しているのだろうか

IT戦記

プログラミング、起業などについて書いているプログラマーのブログです😚

Haskell のリストと遅延評価が少し分かった

いろいろ試行錯誤をしていて

僕は以下のように脳内変換していて

その間違いが JavaScript の関数と Haskell の関数の違いだということが分かった

で、 Haskell の遅延評価をするとは JS 的にはどう表現すればいいか

そして、もう一個見つけたこと

さらに、もう一個見つけたこと

さらに、もう一個見つけたこと

もう一回このエントリーの Haskell のリストを全部 JavaScript にしてやるぜ！

これを

つまりこれを

JavaScript に直すお＞＜

うおおおおお

まとめ