Haskell H99 Question 10

http://www.haskell.org/haskellwiki/99_questions/1_to_10
10問目

9問目をまねて自分で作ってみた。

encode :: (Eq a, Num b) => [a] -> [(b, a)]
encode [] = []
encode (x:xs) = (number, x) : encode rest
	where
		getSeqNum (x:[]) = (1, [])
		getSeqNum (x:y:xs) 
			| x==y = let (n,r) = getSeqNum (y:xs) in (1+n, r)
			| otherwise = (1, y:xs)
		(number, rest) = getSeqNum (x:xs)

基本的な考え方は同じで、大きい再帰で一つの文字列の続くブロックを、小さい再帰でここの文字の評価を行い大きい再帰に返す、という形。

模範解答（ずいぶん簡単な書き方があるようです。。）

import Data.List

encode' xs = map (\x -> (length x,head x)) (group xs)

mapは(a->b) -> [a] -> [b]なので、"a型を取ってb型を返す関数"と、"a型のリスト"を取って、"b型のリスト"を返します。
簡単に想像できる通り、内部では、引数のリストの要素一つ一つに引数の関数を当てた結果をリストとして返します。

ここではmapに、xを取ってxの長さとxの頭文字のtupleを返す関数が入っているので、たとえば、"aaa"にこの関数を使うと、こうなります。

Prelude> (\x -> (length x, head x) )("aaa")
(3,'a')

そしてmapの第２引数に使われているgroupは、どうも問題９とまったく同じ動きをするようですね。
※groupはData.Listにいるようなのでimportします。

Prelude> :m Data.List
Prelude Data.List> group "aaasssdddfff"
["aaa","sss","ddd","fff"]

合わせると、あらかじめ同じ文字に分割しておいた"文字列のリスト"に上述の関数をあてることによって正解が得られるようになっています。