Sat Jul 6 23:11:34 JST 2013

/scheme/amb-final.scm.txt

昨日くらい書いた.どんな状態でもちゃんと動く自信がない

それはともかく

Haskellでよくある

case list of
 []   -> a 
 x:xs -> f x xs

こういうリストのパターンマッチ もちろん実際には更に複雑なパターンマッチもあるけど、 たいていはこの[]かどうかだけの二通りに分岐させるだけで済む

パターンマッチの無い言語で相当のことをさせるには if を 書くのであって、if は普通、遅延評価になるのだけど、 上のコードでいう a が少なくともその文脈で定数で、(x:xs)の パターンの時は(x,xs)を受け取るラムダ式とすれば、これは ifでなくてもいいことになる.

function match(ls, u, f) {
  return ls.length==0 ? u : f(ls[0], ls.slice(1));
}

敢えて再発明する必要もない length, filter を書いてみると以下のように

function len(ls) {
  return match(ls, 0, function(x,xs){ return 1+len(xs) });
}
console.log(len([1,2,3]))

function cons(x,xs) {
  return [x].concat(xs);
}
function filter(ls, pred) {
  return match(ls,[]
    , function(x,xs){
        var ys = filter(xs,pred);
        return pred(x) ? cons(x, ys) : ys;
    });
}
function oddp(x) { return x%2 != 0 }
console.log(filter([1,2,3,4,5], oddp))

Array#slice ってどのくらいコスト掛かるんだろうか