Haskell H99 Question 12

http://www.haskell.org/haskellwiki/99_questions/11_to_20

問題１２
問題の日本語訳

連長圧縮のリストを復号しなさい。
問題１１で明示された通りに作られた連長圧縮コードが与えられる。その展開した版を作成しなさい。

data ListItem a = Single a | Multiple Int a deriving (Show)

decodeModified :: [ListItem a] -> [a]
decodeModified [] = []	-- (1)
decodeModified ((Single x):xs) 		= x : decodeModified xs  --(2)
decodeModified ((Multiple 1 x):xs) 	= x : decodeModified xs  --(3)
decodeModified ((Multiple n x):xs) 	= x : decodeModified ((Multiple (n-1) x):xs)  --(4)

まあまあよくできたと思うけどやっぱり模範解答は全然違うことが書いてありました。（後述）
パターンマッチングというやつはここまでできるんですねー、関心。

(1) 空だったら空のリストを返す。終点
(2) もし先頭要素がSingleだったら、先頭に文字をくっつけて後続に対して再帰
(3) もし先頭要素がMultipleで長さが1だったら(2)と同じ処理
(4) もし先頭要素がMultipleで長さが1以外だったら、先頭に文字をくっつけて長さを減らしてもう一回

模範解答

http://www.haskell.org/haskellwiki/99_questions/Solutions/12

concatMapを使っていますね。確かに結構きれい。
concatMapは、こんなのです。

concatMap :: (a -> [b]) -> [a] -> [b]   -- Defined in `GHC.List'

aのリストに第一引数の関数を当てるけど、そのままだと[[b],[b],[b]]みたいになっちゃうから中のかっこを外して[b]にするってやつだな。
ちょっと試しに使ってみる。
まず非リストな何かを取ってリストを返す関数を適当に作ってみて、

naturalNumberTill n = naturalNumberTill' 1 n
	where 
		naturalNumberTill' x n
			| x > n 	= []
			| otherwise	= x : naturalNumberTill' (x+1) n 

それを使って実行してみる。

*Main> :t naturalNumberTill
naturalNumberTill :: (Num a, Ord a) => a -> [a]

*Main> map naturalNumberTill [3,4,5]
[[1,2,3],[1,2,3,4],[1,2,3,4,5]]

*Main> concatMap naturalNumberTill [3,4,5]
[1,2,3,1,2,3,4,1,2,3,4,5]

なるほど。