達成すべきもの
あるリストが与えられたとき、リストの中の要素 a と a がリスト内に何個含まれているかカウントして返す関数を作る
elemCount : [a] -> [(a, Int)]
アプローチ1 : ソートしてグルーピングする
-- | for empty list
--
-- >>> elemCountOrd []
-- []
--
-- | count the same element
--
-- >>> elemCountOrd [1,1,1,2,2,3,1,2,3]
-- [(1,4),(2,3),(3,2)]
--
-- | target list is sorted before counting
--
-- >>> elemCountOrd [1,1,1,3,1,2,3]
-- [(1,4),(2,1),(3,2)]
--
elemCountOrd :: (Ord a) => [a] -> [(a, Int)]
elemCountOrd = map (\l -> (head l, length l) ) . group . sort
sort : [a] -> [a] でソートを実行して、 group : [a] -> [[a]] で同じ要素だけの配列にまとめてしまう方法。至って普通のアプローチだと思える。
[1,1,1,2,2,3,1,2,3]
-(sort)-> [1,1,1,1,2,2,2,3,3]
-(group)-> [[1,1,1,1],[2,2,2],[3,3]]
でも、ここでふと気づく。この関数が Ord a （大小比較可能）を要求していることに。
本当は「同じ要素を」カウントするのであって、要素同士の大小比較は関係ないはずである。実際、この関数は [[a]] に対して適用できない。
アプローチ2: Eq a で書き直してみる
Eq a で実行できるように書き直してみた。
-- | for empty list
--
-- >>> elemCountEq []
-- []
--
-- | count the same element
--
-- >>> elemCountEq [1,1,1,2,2,3,1,2,3]
-- [(1,4),(2,3),(3,2)]
--
-- | target list not sorted, so result is order of appearance.
--
-- >>> elemCountEq [1,1,1,3,1,2,3]
-- [(1,4),(3,2),(2,1)]
--
elemCountEq :: (Eq a) => [a] -> [(a, Int)]
elemCountEq = map (\l -> (head l, length l) ) . groupSameElement
-- | group the same element on list
--
-- >>> groupSameElement [1,3,4,5,2,2,1,2,4]
-- [[1,1],[3],[4,4],[5],[2,2,2]]
--
groupSameElement :: (Eq a) => [a] -> [[a]]
groupSameElement [] = []
groupSameElement (x:xs) = [x:(filter (== x) xs)] ++ groupSameElement (filter (/= x) xs)
リストの先頭要素 x を取り出し、「 x に一致するリスト」と「 x に一致しないリスト」に分ける方法。
確かに Eq a のみで書けているのだが、 head : [a] -> a を使っているのが気に食わない。
アプローチ3: unique な要素のみのリストを作ってみる
-- | get uniq list
--
-- >>> uniq [1,2,2,3,1]
-- [1,2,3]
--
-- | result is order of appearance
--
-- >>> uniq [2,3,2,1,1,1,5,3,4]
-- [2,3,1,5,4]
--
uniq :: (Eq a) => [a] -> [a]
uniq [] = []
uniq (x:xs) = x:(uniq (filter (/= x) xs))
-- | count same element
--
-- >>> countSameElement 1 [1,1,2]
-- 2
-- >>> countSameElement 0 [1,1,2]
-- 0
--
countSameElement :: (Eq a) => a -> [a] -> Int
countSameElement x = length . filter (== x)
-- | for empty list
--
-- >>> elemCountUniq []
-- []
--
-- | count the same element
--
-- >>> elemCountUniq [1,1,1,2,2,3,1,2,3]
-- [(1,4),(2,3),(3,2)]
--
-- | target list not sorted, so result is order of appearance.
--
-- >>> elemCountUniq [1,1,1,3,1,2,3]
-- [(1,4),(3,2),(2,1)]
--
elemCountUniq :: (Eq a) => [a] -> [(a,Int)]
elemCountUniq xs = fmap (\x -> (x, countSameElement x xs)) $ uniq xs
uniq xs でリスト内の一意な要素のみ取り出してみて、それぞれの要素が何個含まれているかカウントする。
一つ一つはシンプルでうまく分解できた気がするのだが、なんか冗長…。
アプローチ4: 一発でできるんじゃね？
-- | for empty list
--
-- >>> elemCountOnce []
-- []
--
-- | count the same element
--
-- >>> elemCountOnce [1,1,1,2,2,3,1,2,3]
-- [(1,4),(2,3),(3,2)]
--
-- | target list not sorted, so result is order of appearance.
--
-- >>> elemCountOnce [1,1,1,3,1,2,3]
-- [(1,4),(3,2),(2,1)]
--
elemCountOnce :: Eq a => [a] -> [(a, Int)]
elemCountOnce [] = []
elemCountOnce (x:xs) = (x, (length $ filter (== x) xs) + 1) : elemCountOnce (filter (/= x) xs)
とりあえず現状最終版。アプローチ2と基本的に同じなのだが、 head は使っていない。
また、一旦リストを整理してからタプルにするのではなく、走査しながらどんどんタプルにしていく。
(length $ filter (== x) xs) + 1 はいまいちかな～と思っている。
気をつけたいこと
Ord と Eq で条件を変えたように、Haskellでは必要最小の条件で関数を構成したほうが適用できる範囲は広がる。つまり抽象化される。
これは数学の定理にも同じことが言える。ピタゴラスの定理より余弦定理のほうが「直角三角形」という条件が緩和されて任意の三角形に適用できるわけである。
一方であまり下手に「適用範囲を大きくする」を意識し過ぎても良くない。適用範囲が広くなるということは、場合によってはパラメータ数が増えるということになる。これはモンスター関数を生み出しかねない。
一貫して言えるのは「目的を的確に表現するシンプルな前提条件である」こと。
Aの場合もBの場合も似たような処理をする必要があるときに、まずは重複を恐れずAとBの処理関数を別個に書いてみればいい。
どちらの場合も表現できるようなシンプルな前提条件が得られるなら、それを入力データとするシンプルな関数を作るべきであって、関数内部でAの場合とBの場合を分岐させていては複雑度が増すばかりである。