OCaml : 正格評価 : 高階関数とリストによる抽象化

プログラミング

Concurrent Cleanでは、次のようなプログラムは普通ですが、

Start = sum $ map (\x = x*x) $ filter isOdd [0..100]

遅延評価では効率的なこういうプログラムは、正格評価では非効率になるのですが、今日、これを逆にしたら、正格評価でも効率的なプログラムになるのではないかと思いました。

Start = [0..100] $ filter isOdd $ map (\x = x*x) sum

直感的に、これは正格評価で効率的だと思ったのですが、これが具体的にどういう実装になっているのかがしばらく分からなくて、悩むこと小一時間（本当は十数分くらいだと思う）
よくよく見たら、これって、オブジェクト指向ですよ。というか、メッセージパッシングという方が正しいか。
つまり、リストが高階関数だと考えるのです。具体的な実装が次のような感じ。（一見Lisp風ですが、何語かわからんですね）

(define list
  (let ((ls))
    (lambda (msg)
      (dolist (i ls)
        (apply msg i)))))

[0..100]が関数を受け取る高階関数で、(filter isOdd)という関数を受け取ります。
その返値もリスト、つまり高階関数で、(map (\x = x*x))という関数を受け取ります。
さらにその返値もリストで、最後に(sum)関数を受け取って、要素の合計を計算します。

      • -

あ、ちょっと違う。上のだと、やはり効率が悪くなるという問題が解決していない。

Start = [0..100] (filter isOdd (map (\x = x*x) (sum)))

という風になるわけだから・・・
[0..100]が受け取る関数は、(filter isOdd (map (\x = x*x) (sum)))という関数で、
filter isOddが受け取る関数が、(map (\x = x*x) (sum))という関数で、
map (\x = x*x)が受け取る関数が、(sum)という関数だということです。

      • -

あとで、何かで実装してみよう。

      • -

ということで、OCamlで適当に書いてみた。Cleanで書いても書けるのだけれど、せっかくだから、正格な言語でやってみようということで。

# let rec ls l f b =
  match l with
  [] -> b
  | a :: ar -> ls ar f (f a b);;

# let filter f g a b =
  if f a then g a b else b;;

# let map f g a b = g (f a) b;;

# let fold f a b = f a b;;

# let foldlist a b = a::b;;

# ls [1;2;3;4;5;6;7;8;9;10]
  (filter (fun a -> 1 == a mod 2)
  (map (fun a -> a*a)
  (fold (+)))) 0;;
- : int = 165

# ls [1;2;3;4;5;6;7;8;9;10]
  (filter (fun a -> 1 == a mod 2)
  (map (fun a -> a*a)
  foldlist)) [];;
- : int list = [81; 49; 25; 9; 1]

とりあえず書いてみたが、副作用ではなくって、返値で返したい。あと、sumも書けるように。
（追記）改良した。返値で返すように。あとsumも書いた。最後の例が、reverseになってしまっているのが微妙。

      • -

ついでに、atも作ってみた。

# let at a (b,c) =
   if b > 0 then (b-1,c) else if b == 0 then (b-1,a) else (b,c);;

# snd (ls [1;2;3;4;5;6;7;8;9;10] at (3,-1));;
- : int = 4

やっぱり、もういまいちか・・・

      • -

ところで、OCamlって[1..10]みたいな書き方はどうすればいいんだろう？