「ふつうのHaskellプログラミング」読みます(4)

haskell

5章、はほとんど読むところだな。

if.hs

myIf True t e = t
myIf False t e = e
main = do myIf True (putStrLn "then") (putStrLn "else")

% ghc if.hs -o if
% ./if
then

遅延評価なのでthen-partのしか実行されてませんねー、という。

最外簡約って言葉はとてもわかりやすかったけど、参照透明性ってのはよくわからんな。参照はともかく、透明て。
透明性、透明性。透明性って元々transparencyの訳語じゃね？ 知らないけどさ。たぶん俺が元々透明性って言葉に違和感ありまくりなだけ。

この章を読んで、

main = do cs <- getContents
          putStr cs

が行ごとにputStrされるわけがわかった、ような気もする。わかんないっちゃわかんないけど。一文字読めばその時点でputStrできんじゃね？ とかいう疑問もあるし。端末からの入力だと一行ごとに入力されるからそうなってるんだろか。だったらリダイレクトとかだと、やっぱり全部読んでから全部書いてんの？ とか。
runghcから上のコード実行すると一文字入力するごとに文字を出力してしまうのは、なんか端末モードの違いとかだろうか。不明。

tarai.hs

たらいまわしする。

main = print (tarai 20 10 5)

tarai x y z = if x <= y
                then y
                else tarai
                  (tarai (x - 1) y z)
                  (tarai (y - 1) z x)
                  (tarai (z - 1) x y)

% ghc tarai.hs -o tarai
% time ./tarai
20
0.000 user 0.004 system 0.005 total

はえー。まあきっとこういうことだよね。メモ化。

#include <stdio.h>
#define hash(x,y,z) ((x)<<10)|((y)<<5)|(x)
int tarai(int x, int y, int z) {
  static table[1000000];
  int hkey = hash(x, y, z);
  int tval = table[hkey];
  if(tval!=0){
    return tval;
  }
  if(x <= y) {
    table[hkey] = y;
  } else {
    table[hkey] = tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y));
  }
  return table[hkey];
}
int main() {
  printf("%d\n", tarai(20, 10, 5));
}

% gcc -O3 tarai.c
% time ./a.out
20
0.000 user 0.000 system 0.003 total

こうやって頑張ればもちろん、原理的にC言語のが速い。でもまあこんなんやるのしんどいよね。Haskellだと「参照透明性」があるので、全部が全部メモ化をほどこすことができます。っていうか勝手にやってるってことだったよなきっと。

test