孤独のHaskell
孤独のHaskellに行ってきた.ので,感想とそのフォローアップになりそうなことを書く.
とてもいい会だったように思う.
遅刻して現場に付いたらRLEしてみようという例題("AABBCCC"を"A2B2C3"にする関数を書こう)をやっていて, id:khibino0 さんがおもむろに
import Data.List ( group ) import Control.Arrow rle = concatMap (uncurry (:) . (head &&& show . length)) . group
のような解をブッパしてたりするなど.で,各自自前実装してる人たちのコードとか見ると「細かい操作でボトムアップにやりたいことを実現しようとしてるなー」と感じることが多かった.Haskellの場合(なのかは知らないが)もっと大域的な変換からトップダウンに考えていったほうがシンプルでソレっぽいコードになるのになーと.頭から文字をひとつひとつ見ていって,次の文字と同じかどうかとか,いま何文字連長しているかとか,そういったメンドクサイ感あふれるものを一生懸命やっちゃうのはよろしくない.俺は手続きを捨てるぞォーージョジョォーッ!
というわけで,このRLEをサンプルに, hoogle と hlint に身を任せて同化することで,ほとんどトップダウンの型設計・型情報だけからかなり Haskell 的な実装にもっていく作業にトライしてみよう.
まず,欲しいものは明らかに以下のような型のrleだ,
rle :: String -> String rle = undefined
まぁ,これだけだと何もしない関数とかも満たしちゃうから途中にあるべき状況の型を挟もう(=という設計行為をしよう).たぶん,多くの人が「「文字とその連長数」のリスト」が中間の構造として欲しいと思うんじゃないだろうか?なので,この中間構造ヘの関数toIntermediate(名前がイケてないが一時的なので)と,中間構造を解にもっていくfromIntermediateが欲しいねというハナシになる,
rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = undefined toIntermediate :: String -> [(Char, Int)] toIntermediate = undefined
fromIntermediateは,さらに中間構造として「文字列(=文字と連長のペアを文字列に変換したもの)のリスト」が欲しいだろう,
rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = cat . rl2strs rl2strs :: [(Char, Int)] -> [String] -- この文字列は文字と連長のペアを文字列に変換したもの rl2strs = undefined cat :: [String] -> String -- 全部結合できればいい cat = undefined toIntermediate :: String -> [(Char, Int)] toIntermediate = undefined
さて,ここまで分解して来て cat を見たらコイツは「文字列を結合する」というもう十分小さくてシンプル(と,我々には思える)処理になっている.つまり,「ライブラリのどっかにもうこれをやってくれるヤツがいるんじゃないの?」という気分になる.で, hoogle の出番だ.こいつは型で検索できる(=設計から実装を検索できる)ので,検索窓に"[String] -> String"入れて検索するといくつか出てくるが,それっぽいものを探すと上から何番目かに concat ってやつが出てきている.型は"a -> [a]"となっているが,そもそもStringが[Char]なので型は合っている.リンクを飛んでこの関数の説明を見ると"Concatenate a list of lists."と書いてあるのでビンゴだ.つまり cat は concat でいい.
rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . rl2strs rl2strs :: [(Char, Int)] -> [String] rl2strs = undefined toIntermediate :: String -> [(Char, Int)] toIntermediate = undefined
次に rl2strs はリストの各要素をそれぞれ変換しているので,各要素に何かをやる foreach と,その何かである rl2str にさらに分解しよう.
rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . rl2strs rl2strs :: [(Char, Int)] -> [String] rl2strs = foreach rl2str foreach :: (a -> b) -> [a] -> [b] foreach = undefined rl2str :: (Char, Int) -> String rl2str = undefined toIntermediate :: String -> [(Char, Int)] toIntermediate = undefined
同様に foreach の型について hoogle で検索すると,コイツは実には map だとわかる.
rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . map rl2str rl2str :: (Char, Int) -> String rl2str = undefined toIntermediate :: String -> [(Char, Int)] toIntermediate = undefined
rl2str も十分シンプルだが,コイツは hoogle してもソレっぽいものが無いので,これはこの問題特有の事情を多分に含んだ処理であり,自分で実装を与えてあげる必要があるということがわかる.まぁ,このくらいはやろう,単純だし.
rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . map rl2str rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n -- n を文字列にして文字 c を先頭に付ければいいよねと toIntermediate :: String -> [(Char, Int)] toIntermediate = undefined
fromIntermediate 側については大体できた,次に toIntermediate 側について考えよう.やはり中間構造として「「連続した同じ文字による文字列」のリスト」が欲しいかなぁと思える.
rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . map rl2str rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toIntermediate :: String -> [(Char, Int)] toIntermediate = toPairs . toRLs toRLs :: String -> [String] toRLs = undefined toPairs :: [String] -> [(Char, Int)] toPairs = undefined
toRLs の型で hoogle したい,が,その前に,この処理の本質を考える.すると,これって別に文字列じゃなくてもいいよね?という話になる.つまり「「連続した同じ文字による文字列」のリスト」にする処理じゃなくて「「連続した同じ何かによる何かの列」のリスト」にできる処理があれば「何か」が「文字」のときにも適用できるよねということだ. Haskell の関数は可能な限り(そのほうが便利だから)汎用的な型を与えているので "[a] -> a" で検索したほうが一層ヨサゲなものがヒットしそうだ.すると, group というピッタリなものが見付かる.コイツの検索結果の型は "Eq a => [a] -> a"だ,つまり「同じ何かによる」ということが判別できるという条件が,Eqの型クラス制約として表れている.ここまで付けて hoogle 検索するべきだったね(=設計段階で考えが及ばなかった)と反省することになる.ちなみに group は Prelude に入っておらず, Data.List モジュールの関数なので,コイツを import してやる必要があるな…と,これもドキュメントや検索結果からわかる.
import Data.List ( group ) rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . map rl2str rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toIntermediate :: String -> [(Char, Int)] toIntermediate = toPairs . group toPairs :: [String] -> [(Char, Int)] toPairs = undefined
toPairs も「連続した同じ文字による文字列」を「「その文字」と「長さ」の組」にする関数をリストの各要素に適用すればよさそうだ,リストの各要素に適用する関数はもう検索した. map だったね.
import Data.List ( group ) rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . map rl2str rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toIntermediate :: String -> [(Char, Int)] toIntermediate = map toPair . group toPair :: String -> (Char, Int) toPair = undefined
では,この toPair も分解してみよう.「「その文字」と「長さ」の組」を作るわけだが,「連続した同じ文字による文字列」なので「その文字」は文字列の中のどこを取っても同じなハズだ.「長さ」は単に文字列の長さがわかればいい.
import Data.List ( group ) rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . map rl2str rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toIntermediate :: String -> [(Char, Int)] toIntermediate = map toPair . group toPair :: String -> (Char, Int) toPair str = (anyElem str, len str) anyElem :: String -> Char anyElem = undefined -- 文字列の中のどれを取ってもいいハズ len :: String -> Int len = undefined
anyElem もまた文字列に限らずリスト型のどこの要素を取ってもかまわないハズなので,"[a] -> a"で hoogle 検索するといくつか候補が出る. head と last だ.どっちでもいいが,リストは先頭取るほうがラクなので head を使っておこう.
import Data.List ( group ) rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . map rl2str rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toIntermediate :: String -> [(Char, Int)] toIntermediate = map toPair . group toPair :: String -> (Char, Int) toPair str = (head str, len str) len :: String -> Int len = undefined
len もまた文字列に限らずリスト型の長さがわかればいいハズなので,"[a] -> Int"で hoogle 検索するとこれはもう length 確定.
import Data.List ( group ) rle :: String -> String rle = fromIntermediate . toIntermediate fromIntermediate :: [(Char, Int)] -> String fromIntermediate = concat . map rl2str rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toIntermediate :: String -> [(Char, Int)] toIntermediate = map toPair . group toPair :: String -> (Char, Int) toPair str = (head str, length str)
お,undefinedが無くなった.from/toIntermediate もそろそろいなくなってもらって.
import Data.List ( group ) rle :: String -> String rle = concat . map rl2str . map toPair . group rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toPair :: String -> (Char, Int) toPair str = (head str, length str)
では,これでghci上で実行してみよう.
$ ghci RLE.hs GHCi, version 7.4.2: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Main ( RLE.hs, interpreted ) Ok, modules loaded: Main. *Main> rle "AABBCCC" "A2B2C3" *Main> rle "AABBBCCCC" "A2B3C4" *Main> rle "AABBBCCCCC "A2B3C5" *Main> :q
うん,OKぽい.さらに Haskell っぽいコードになるために仕上げに hlint を使っておこう.
$ hlint RLE.hs RLE.hs:4:7: Error: Use concatMap Found: concat . map rl2str . map toPair . group Why not: concatMap rl2str . map toPair . group RLE.hs:4:16: Warning: Use map once Found: map rl2str . map toPair . group Why not: map (rl2str . toPair) . group 2 suggestions
指摘が2件あった.どっちでもいいけど,まず2個目の指摘事項から修正しよう(ちょい恣意的)."map f . map g" を "map (f . g)" にしろと言われている.自然言語で言えば「「各要素にgを適用」してから,「各要素にfを適用」する」のを「各要素に「gを適用してからfを適用」する」に変換しろと言われている.要は「ループ2回書いてるのを1回で両方やるようにしたほうがいい」と言われている.
import Data.List ( group ) rle :: String -> String rle = concat . map (rl2str . toPair) . group rl2str :: (Char, Int) -> String rl2str (c,n) = c:show n toPair :: String -> (Char, Int) toPair str = (head str, length str)
では,改めて hlint をもういっかい.
$ hlint RLE.hs RLE.hs:4:7: Error: Use concatMap Found: concat . map (rl2str . toPair) . group Why not: concatMap (rl2str . toPair) . group 1 suggestion
さっき残した 1件目の指摘だが, concatMap とやらを使えと言われている.さてこれは何かという話なのでまた hoogle だ.今度は型ではなく関数名で検索しよう. すると concatMap は名前の通り map してから concat するような処理を一度にやる関数のようだ.へぇ,と思いながら修正修正…
import Data.List ( group ) rle :: String -> String rle = concatMap (rl2str . toPair) . group rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toPair :: String -> (Char, Int) toPair str = (head str, length str)
で,トドメの hlint と.
$ hlint RLE.hs No suggestions
指摘が無くなった.まぁ,ここまででももう十分ではある.だけど,まだまだ簡単にできる変換いってみよう.ヤリコンデルー.今 (rl2str . toPair) と関数合成されている.こいつを次のようにひとつの関数rle'にしてみよう.
import Data.List ( group ) rle :: String -> String rle = concatMap rle' . group where rle' :: String -> String rle' = rl2str . toPair rl2str :: (Char, Int) -> String rl2str (c,n) = c : show n toPair :: String -> (Char, Int) toPair str = (head str, length str)
ポイントフリーになっているrle'に引数を与えてみよう.
import Data.List ( group ) rle :: String -> String rle = concatMap rle' . group where rle' :: String -> String rle' str = rl2str (toPair str) rl2str :: (Char, Int) -> String rl2str (c,n) = c:show n toPair :: String -> (Char, Int) toPair str = (head str, length str)
toPair を定義通りに展開できる状態になっているのでそのまま展開.
import Data.List ( group ) rle :: String -> String rle = concatMap rle' . group where rle' :: String -> String rle' str = rl2str (head str, length str) rl2str :: (Char, Int) -> String rl2str (c,n) = c:show n
今度は rl2str が定義通りに展開できる状態になっているのでそのまま展開.
import Data.List ( group ) rle :: String -> String rle = concatMap rle' . group where rle' :: String -> String rle' str = head str : show (length str)
rle'をラムダ式にしてー
import Data.List ( group ) rle :: String -> String rle = concatMap rle' . group where rle' :: String -> String rle' = \str -> head str : show (length str)
その場に展開…と.
import Data.List ( group ) rle :: String -> String rle = concatMap (\str -> head str : show (length str)) . group
よし,念のためもう一度ghciで動作をみておこう.
$ ghci RLE.hs GHCi, version 7.4.2: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Main ( RLE.hs, interpreted ) Ok, modules loaded: Main. *Main> rle "AAAABCCC" "A4B1C3" *Main> :q
hlintも.
$ hlint RLE.hs No suggestions
問題無さそう.というわけで,最終的なコードとしては,以下のようになったわけだ.
import Data.List ( group ) rle :: String -> String rle = concatMap (\str -> head str : show (length str)) . group
この記事最上部の日比野さんの解と比べても(&&&)を使っていないだけで殆んど同じとこまで来ているハズだ.大体このくらいの例題だったら hoogle と hlint にイロイロなアレコレを任せてしまって,自分は欲しい関数の型を考えて決めていくだけでなんとなくイイカンジに仕上がりそうかなという雰囲気を感じてもらえるだろうか.
といっても,当然だが,毎度毎度こういう設計・実装の仕方をしているわけでは無い.よく使うPreludeやその近辺の関数は普通覚えてしまっているので今回hoogleしたようなmapやconcatのような関数をhoogleすることは無い,が,これらの関数を使える機会は小さなところからボトムアップに手続き的に思考していこうとするとあんまり出てきてくれなかったりする.それよりも,hoogle(や,あるいは hayoo)等で出てきそうかなと思えるまで問題を型で分割していくように考えたほうがシアワセになり易い.と思う.