Ninety-Nine Haskell Problems 9
1to10 11to20 21to30 31to40 51to60 61to70 71to80 81to90 91to99 all Ninety-Nine Haskell Problems
九問目．
9 Problem 9 (**) Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists. Example: * (pack '(a a a a b c c a a d e e e e)) ((A A A A) (B) (C C) (A A) (D) (E E E E)) <example in lisp> Example in Haskell: *Main> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e'] ["aaaa","b","cc","aa","d","eeee"]http://www.haskell.org/haskellwiki/99_questions/1_to_10#Problem_9
さて，実は一日考えてもわからなかったので，即座に解答．
Solution:
pack (x:xs) = let (first,rest) = span (==x) xs
in (x:first) : pack rest
pack [] = []
A more verbose solution is
pack :: Eq a => [a] -> [[a]]
pack [] = []
pack (x:xs) = (x:first) : pack rest
where
getReps [] = ([], [])
getReps (y:ys)
| y == x = let (f,r) = getReps ys in (y:f, r)
| otherwise = ([], (y:ys))
(first,rest) = getReps xs
This is implemented as group in Data.List.
うーん，悔しいけど仕方ない．解読解読．
えー，まずletってなんだ？
どうやら，whereみたいに関数内で関数を定義するみたいだけど，それだけじゃよくわからんので，先にspan．
-- | 'span', applied to a predicate @p@ and a list @xs@, returns a tuple where
-- first element is longest prefix (possibly empty) of @xs@ of elements that
-- satisfy @p@ and second element is the remainder of the list:
--
-- > span (< 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4])
-- > span (< 9) [1,2,3] == ([1,2,3],[])
-- > span (< 0) [1,2,3] == ([],[1,2,3])
--
-- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
span :: (a -> Bool) -> [a] -> ([a],[a])
span _ xs@[] = (xs, xs)
span p xs@(x:xs')
| p x = let (ys,zs) = span p xs' in (x:ys,zs)
| otherwise = ([],xs)
http://haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/GHC-List.html#span
とのこと．ってlet使われてるじゃねーか！
説明には，listの先頭からpを満たすものを集めてリストにし，残りもリストにして，二つのリストをtupleで返すっぽいことが書いてある．なんだよtupleって．まぁよくわからないけども，()で定義される構造っぽい．
で，このことをふまえて，ソースにあたる．
あんましよくわからないながら，じーっとみてるとなんとかわかってきた．
| p x = let (ys,zs) = span p xs' in (x:ys,zs)
とりあえず，この行はxがpを満たせば実行(？)される．つまり，
let (ys,zs) = span p xs' in (x:ys,zs)
となるんだけど，右辺の(ys,zs)には，span p xs'の結果が入ると（spanの戻り値は([a],[a])だからね！）．で，もともとのspanにはinのあとの，(x:ys,zs)が返される．
それはひとまず置いて，xがpを満たさなかった場合，([],xs)が返される．
さぁ，僕は頭の中で再生するのは無理だぜ！
ということで，手動実行．
span (< 3) [1,2,3,4,1,2,3,4] = let (ys1,zs1) = span (< 3) [2,3,4,1,2,3,4] in (1:ys1,zs1) = let (ys1,zs1) = let (ys2,zs2) = span (< 3) [3,4,1,2,3,4] in (2:ys2, zs) in (1:ys1,zs1) = let (ys1,zs1) = let (ys2,zs2) = ([], [3,4,1,2,3,4]) in (2:ys2, zs) in (1:ys1,zs1) = let (ys1,zs1) =(2:[], [3,4,1,2,3,4]) in (1:ys1,zs1) = let (ys1,zs1) =([2], [3,4,1,2,3,4]) in (1:ys1,zs1) = (1:[2], [3,4,1,2,3,4]) = ([1,2], [3,4,1,2,3,4])
おお……．無理矢理やってみたけど，結構むずいぜ……．
ま，まぁとにかく，どんな挙動をするかはわかったからよし！次！
で，spanがわかったところで（ついでにletも若干わかった），packを再掲．
pack (x:xs) = let (first,rest) = span (==x) xs
in (x:first) : pack rest
pack [] = []ほうほう，なかなかわかってきたぜぇ！
spanの第一引数で(==x)，で第二引数が，xs．つまり，xsの先頭にある，xと同じ値を持つものを，firstにぶち込む！restには残り！そして，元のpackには，firstの先頭にxを付け加え，さらに残りをpackしたものを結合が返される！((x:first)はそれ自体がリストの要素．(:)で結合されるからね)．
うーん，こうみてみると，素晴らしい．こんな風にかけるのはHaskellの(ていうか，関数型言語の，か？)威力だなって感じがする．
はいはい，こういうことねって感じがしてきた．でも，自分でこういう風に書けるかっていうと，まだまだ無理だなぁ．いつかさらっとかけるといい．再帰が自然にでてくるから，こういう感覚を身に付けるためだけでも，Haskellの勉強には意味があるんじゃないかって気がしてきた．
1to10 11to20 21to30 31to40 51to60 61to70 71to80 81to90 91to99 all Ninety-Nine Haskell Problems
