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

6 件のコメント:

  1. Yahoo! ならぬ Hayoo!
    http://holumbus.fh-wedel.de/hayoo/hayoo.html

    返信削除
  2. fromEnum $ floor $ toEnum n/10
    というのは単に
    n `div` 10
    でいいですよね

    返信削除
  3. Int を n 進の各桁のリストにするにはたとえば
    Data.List.mapAccumR を使って

    rep :: Int -> Int -> [Int]
    rep n i = snd $ mapAccumR divMod i
    $ zipWith const (repeat n) (show i)

    とか。

    返信削除
  4. ありがとうございます。 > Hayoo!

    整数型の除算がちゃんとあったんですよね。
    (/) と mod が商と剰余だと思い込んでました。

    それにつけても mapAccumR 最強 :)
    「商と剰余をタプルで返してくれないかな」→「Int -> Int -> (Int, Int) あたりを検索」でうまく divMod を見つけられると、自力でmapAccumR を発動できたのかなあ。

    返信削除
  5. nabeatu :: Int -> String
    nabeatu n | n `mod` 3 == 0 = "aho"
         | elem '3' str = "aho"
         | otherwise = str
    where str = show n

    main = putStr $ unlines $ map nabeatu [1..40]

    返信削除
  6. show!
    どうりでx->string的なものがないのか!

    返信削除