読者です 読者をやめる 読者になる 読者になる

孤独のHaskell

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 検索するといくつか候補が出る. headlast だ.どっちでもいいが,リストは先頭取るほうがラクなので 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)等で出てきそうかなと思えるまで問題を型で分割していくように考えたほうがシアワセになり易い.と思う.