2008/09/26

Scheme どう書く?的 - ひげぽん OSとか作っちゃうかMona-
http://d.hatena.ne.jp/higepon/20080925/1222326246

こんなことをしていられる状況ではないんだけど、mapAccumLを使いたい衝動を抑えられなかった。
compactNumberList :: [Int] -> [[Int]]
compactNumberList = snd . partition ([]==) . tail . snd . mapAccumL collect [-1] . (++[-1])
where collect xx@(x:xs) y | y - x == 1 = (y:xx, [])
| xs ==[] = ([y], [x])
| otherwise = ([y], [last xx, head xx])

2008/09/12

IO型は、使うだけなら簡単に思える。たとえば String -> IO () という型の putStr に文字列を渡せば、それが画面に印字される。
Main >putStr "abcdef\n"
abcdef
putStr の出力は IO () 型なので、結果として印字された「abcdef」は文字列ではない。じゃあ、IO () 型の出力はどこにいったんだろう? Show クラスのインスタンスがないということ? でも、だとしたらGHCがエラーを出力するんじゃなかったっけ?

とにかく絶対に IO () な何かが関数の結果として返ってきているはずなので、IO () -> String な関数を定義してそれに putStr をつないでみた。
vacant :: IO () -> String
vacant o = "munashii"
Main >vacant $ putStr "subarashii\n"
"munashii"
どうして「subarashii」が印字されないん?

結局、これはやっぱり副作用じゃないってことなんだろうな。Scheme でも同じことをすると、
gosh> (define (vacant o) "munashii")
vacant
gosh> (vacant (print "subarashii"))
subarashii
"munashii"
これが本物の副作用ということなのか!

2008/09/11

Haskellでプログラムを書くときは、まず関数の型を妄想してHoogleしろ

Haskellでは、型を「利用して」プログラミングができるという。つまり、「あーなんかこんな型の関数ねえかな」というところからプログラムを書き始めるものらしい。だから haskell.org では型からAPIを検索することができる。その名も Hoogle。Gauche のリファレンスマニュアルさえあれば誰にでも Scheme のプログラムが書けてしまうように、Hoogle があれば誰にでも Haskell のプログラムが書ける。気がする。ところで、Yahooみたいな名前の APIサーチエンジンもあるそうなのですが、見つかりません。
(追記)Hayooでした。ありがとうございます > nobsun(ここまで追記)

たとえば、10進の整数を各桁からなるリストだと思って map したい。
*Main> intMap (*2) 12345
[2,4,6,8,10]
*Main> foldr (+) 0 $ intMap id 123456789
45
こういうintMapをどうやって作っていくか。(以下、とりあえず正の整数の場合だけを考える。)

Scheme脳の正攻法は、各桁の再帰だろう。1の位を head、それより大きな位を tail にして再帰的にリストを作り、reverse すればよさそうだ。10進数の 1の位の数は (mod 10) だし、10で割って floor を取れば 1の位より前にある数字を並べた数になるので、型を考えずにこんなナイーブな定義が書ける。
intMap p n | n < 10 = [p n]
| otherwise = reverse (p last : reverse front)
where
last = mod n 10
front = intMap p (floor (n/10))
ちなみにこれはコンパイルに通らない。floor とか (/) とかは、そのままでは Int型に対して使えないので。コンパイルするには最後の front を次のようにする必要がある。
front = intMap p $ fromEnum $ floor $ toEnum n/10
(追記)整数の割り算がありました。front = intMap p (div n 10) でOK。(ここまで追記)

本来なら順番が逆だけど、ここで初めて intMap の型について考える。intMap は、ふつうの map のように、1引数関数とリスト代わりの整数をとってリストを返すようにしたい。つまり、こういう型だ。
intMap :: (Int -> a) -> Int -> [a]
自分が求めている型が分かったので、これをキーワードにして Hoogle で検索してみる。結果はいっぱい出るけど、その先頭には iterate という関数がひっかかるはずだ。リンクをクリックすると、GHCのドキュメントの iterate の項目にジャンプする。その説明によれば、iterate はこんな関数らしい。
iterate :: (a -> a) -> a -> [a]

iterate f x returns an infinite list of repeated applications of f to x:

iterate f x == [x, f x, f (f x), ...]
見るからに intMap の定義に使えそうだ。f として先ほどの定義の front に相当するものを与えてやれば、iterate f 1234 -> [1234, 123, 12, 1, 0, ...] といった具合にリストが得られるので、あとは各要素から mod 10 で 1の位を抜き出せばいい。
(追記)f の定義を fromEnum $ floor $ toEnum m/10 から div m 10 に修正(ここまで追記)
intMap :: (Int -> a) -> Int -> [a]
intMap p n = map (p . lastDigit) $ reverse $ takeWhile (> 0) $ iterate f n
where
f m = div m 10
lastDigit m = mod m 10
再帰がなくなり、標準関数をごにょごにょするだけで求める関数を作ることができた。

まとめ
「Haskellでプログラムを書くときは、まず関数の型を妄想して Hoogle しろ」

おまけ
ナベアツ問題とか。
nabeatsu = [p i | i <- [1..]]
where has3 n = or $ intMap (== 3) n
p i | has3 i || mod i 3 == 0 = "aho"
| otherwise = intMap intToDigit i