すごいHaskell六章（後半 6.2まで）

プログラミング Haskell

　この章、五章以上にヘビーなんですが。（だが我々はこの時気づいていなかった…六章をさらに上回る強大な章の存在に。）
　六章が急激に難しくなった気がするのは、五章までは文法中心だったからかな。あと、ここから型引数とかMapとかHaskellが本気出し始めた気がする。

tailsの実装

　tails関数はこれまでに出てきた気がしたしたけど出てなかった。出てたのはtailだった。

ghci> tail "Curry Rice"
"urry Rice"
ghci> tails "Curry Rice"
["Curry Rice","urry Rice","rry Rice","ry Rice","y Rice"," Rice","Rice","ice","ce","e",""]

　tailは先頭要素を取り除いたリストを返すけど、tailsはそれを繰り返して、空リストになるまでのリスト全てをリストにして返す。


　tailsの実装はこんな感じかな。

tails' :: [a] -> [[a]]
tails' [] = []
tails' xs = (tail xs) : (tails' xs)

　と思ったら無限に再帰しちゃう……。

ghci> tails' "Curry"
["urry","urry","urry","urry", …

　そりゃそうだ、tails' xs で受けてるところで、もう一回 tails' xsを呼んでるんだから。tailしてから呼ばないと。あと、標準のtailsだと、返り値リストの先頭の要素は、引数をそのまま返すっぽいからそこも直す。

tails' :: [a] -> [[a]]
tails' [] = []
tails' xs = xs : tails' (tail xs)

ghci> tails' "Curry"
["Curry","urry","rry","ry","y"]

　リストの最後に空リストがない…。パターンマッチで、空リストに対して空リストのリストを返さなきゃいけない。

tails' :: [a] -> [[a]]
tails' [] = [[]]
tails' xs = xs : tails' (tail xs) 

ghci> tails' "Curry"
["Curry","urry","rry","ry","y",""]

　できた。


　いかにもscanを使ったらうまくいきそうな形なんだけど…。

ghci> scanr (:) [] "Curry"
["Curry","urry","rry","ry","y",""]

　マジかよ。
　じゃあ、最終的な形は、

tails' :: [a] -> [[a]]
tails' = scanr (:) []

ghci> tails''' "Curry"
["Curry","urry","rry","ry","y",""]

　これは82pの" scanl (flip (:)) "を使ってる例を見て思いついたんだけど…。scanは最初のアキュムレータも途中経過に残すのな。

scanrを使ったtailsの実装の動作

　まず、foldrを使ってみる。

ghci> foldr (:) [] "Curry"
"Curry"

　[]をアキュムレータの初期値として、引数のリストの各要素に対して、(:)を適用していく。
　ちなみに、(:)は右結合だからfoldlだとエラーになる。
foldrを展開するとこんな感じになってるはず

ghci> 'C' : ('u' : ('r' : ('r' : ('y' : []))))
"Curry"

　こうしてみるとfoldlでエラーになる理由がよく分かる。

ghci> (((('C' : []) : 'u') : 'r' ) : 'r' ) : 'y'

<interactive>:58:17:
    Couldn't match expected type `[[Char]]' with actual type `Char'
    In the second argument of `(:)', namely 'u'
    In the first argument of `(:)', namely `(('C' : []) : 'u')'
    In the first argument of `(:)', namely `((('C' : []) : 'u') : 'r')'

　(:)の右側はリストじゃなければいけない。


　scanrはfoldrの各段階をリストに収めながら適用していくから、さっきのfoldrの展開を順に見ていったそのままになる。

ghci> scanr (:) [] "Curry"
["Curry","urry","rry","ry","y",""]

　未だにfoldを使う発想がすぐ出てこない…
　というか、公式ライブラリのソースコードは公開されてそうなんだけど。

isPrefixの実装

　うまいやり方が思いつかなかったけど、こんな感じかな。

isPrefixOf' :: (Eq a) => [a] -> [a] -> Bool
xs `isPrefixOf'` ys 
   | xs == [] = False
   | length xs > length ys = False
   | otherwise = and $ zipWith (\x y -> x == y) xs ys

　ちゃんと動いてるっぽい。

ghci> "haha" `isPrefixOf'` "ha"
False
ghci> "ha" `isPrefixOf'` "ha"
True
ghci> "ha" `isPrefixOf'` "hohehu"
False
ghci> "ha" `isPrefixOf'` ""
False
ghci> "" `isPrefixOf'` ""
False

　と思ったら、標準ライブラリのisPrefixOfだと、空リスト2つでもTrueになるっぽい。

ghci> "" `isPrefixOf` ""
True

　じゃあそこだけ場合分けするか…

isPrefixOf' :: (Eq a) => [a] -> [a] -> Bool
xs `isPrefixOf'` ys 
    | xs == ys = True
    | xs == [] = False
    | length xs > length ys = False
    | otherwise = and $ zipWith (\x y -> x == y) xs ys

ghci> "" `isPrefixOf'` ""
True
ghci> "" `isPrefixOf'` "aaa"
False

　＊おおっと＊標準ライブラリのisPrefixOfだと、一つ目の引数が空リストだとTrueになるらしい。

ghci> "" `isPrefixOf` "aaa"
True

　じゃあ、これでいいか。

isPrefixOf' :: (Eq a) => [a] -> [a] -> Bool
xs `isPrefixOf'` ys 
    | length xs > length ys = False
    | otherwise = and $ zipWith (\x y -> x == y) xs ys

　長さの条件分けがないと、"haha"が"ha"のプレフィックスとか解釈されちゃうので、これはいるはず。

ghci> "" `isPrefixOf'` ""
True
ghci> "" `isPrefixOf'` "aaa"
True
ghci> "h" `isPrefixOf'` "ha"
True
ghci> "haha" `isPrefixOf'` "ha"
False

anyの実装

　述語とリストを受け取って、リストのどれかが述語を満たすかを調べて返す。andとかの実装と似てる。

any' :: (Ord a) => (a -> Bool) -> [a] -> Bool
any' p = foldr (\a acc -> p a || acc) False

　これは一発で動いた。

ghci> any' (> 4) [1,2,3,4]
False
ghci> any' (== 1) [1,2,3,4]
True
ghci> any' (\x -> x > 5 && x < 10) [1,4,11]
False
ghci> any' (\x -> x > 5 && x < 10) [1,4,9]
True

　型クラス制約はOrdでいいのかな。述語の中には比較するものもあるからOrdにしたんだけど、Eqでも動くみたいなんだよね。それどころか、型クラス制約は無くしても動く…うーん。
　このあとのisInの実装見るとEqのインスタンスにしてるから、Eqっぽいな。いや違うか、あっちはisPrefixOfだからEqなのか。

シーザー暗号

　これ『プログラミングHaskell』でも題材になってたな。
　ord関数は文字をUnicodeテーブルの数字に変換。chr関数は数字（Int）を文字に変換。HaskellはUnicodeで統一してるんだっけ。
　decodeはencodeをnegateするというのは面白いと思った。

foldlの遅延評価とオーバーフロー

　式展開をスタックして保持するのかな。
　ちなみに、自分のマシン（Windows 7 32bit、メモリ4G、GHC7.4.1）だと1億個replicateしたらout of memoryになった。
　foldl'ないと思ったらData.Listにあるのね。Preludeにはない。
　1億個でfoldl'するとやっぱり結構時間が掛かる。
　foldl'みたいに遅延評価せずにすぐ評価する関数を「正格」な関数みたいに呼ぶらしい。

各桁の数字の合計のところ

　digitToIntの実装って単純なパターンマッチになってるのかな。

digitToInt' :: Char -> Int
digitToInt' '1' = 1
digitToInt' '2' = 2
digitToInt' '3' = 3
digitToInt' '4' = 4
digitToInt' '5' = 5
digitToInt' '6' = 6
digitToInt' '7' = 7
digitToInt' '8' = 8
digitToInt' '9' = 9
digitToInt' 'A' = 10
digitToInt' 'B' = 11
digitToInt' 'C' = 12
digitToInt' 'D' = 13
digitToInt' 'E' = 14
digitToInt' 'F' = 15
digitToInt' _   = error "uwaaaaa"

　まあ動くっぽい。

ghci> digitToInt' '9'
9
ghci> digitToInt' 'A'
10
ghci> digitToInt' 'F'
15
ghci> digitToInt' '10'

<interactive>:16:14: parse error on input `10'

　あと、showは基本的に文字列に変換するものなのかな。showってここまでではっきり出てきたっけ……
　でてた、二章のShow型クラスのところだ。

ある値は、その型がShow型クラスのインスタンスになっていれば、文字列として表現できます。
（略）
この型クラスのインスタンスに対する操作で一番良く使うのはshowで、これは指定した値を文字列として表示する関数です。（29p）

　
　dititToSumの実装はかっこいい。
　数字の各桁の数を扱うみたいな問題ってよく出てくる気がするけど、やっぱり文字列に変換するのが基本っぽいな。


　ここで初めてMaybeが出てくるんだよな。
　Justが付いた、Maybe a 型の値ってJustがついてないのと、そのままだと比較とかできないみたい。

ghci> "hay" == Just "hey"

<interactive>:25:10:
    Couldn't match expected type `[Char]' with actual type `Maybe a0'
    In the return type of a call of `Just'
    In the second argument of `(==)', namely `Just "hey"'
    In the expression: "hay" == Just "hey"
ghci> :t Just True
Just True :: Maybe Bool
ghci> Just True && True
<interactive>:29:1:
    Couldn't match expected type `Bool' with actual type `Maybe a0'
    In the return type of a call of `Just'
    In the first argument of `(&&)', namely `Just True'
    In the expression: Just True && True

　あーリストみたいなものだし、別物か。findの返り値にMaybeが使われてるのは自然に見える。


この章長いから分けよう。