spanの小ネタ（変奏編）
もあわせてどうぞ．
かなり前にランレングス変換runLength :: Eq a => [a] -> [(a,Int)]について書いたことがあります．
これを再度考えてみましょう．単純に考えると以下のように実装できますね．
code:haskell
runLength = map runlen . group
where
runlen = head &&& length
ここで，map runlenとgroupの間の「中間リストを除去すること」（デフォレステーション）を考えます．
groupはanamorphismの具体例でした．
code:haskell
runLength
= {- 上述の定義 -}
map runlen . group
where
runlen = head &&& length
= {- group = unfoldr psi -}
map runlen . unfoldr psi
where
psi [] = Nothing
psi (x:xs) = case span (x ==) xs of
(ys, zs) -> Just (x : ys, zs)
runlen = head &&& length
= {- map-unfoldr 融合 -}
unfoldr phi
where
phi = (first runlen <$>) . psi
runlen = head &&& length
この運算で中間リストの除去はできましたが，一箇所だけ，気になりますね．それはphiにおいて，せっかくpsi(の中のspan)で組み上げたx:ysをrunlen(の中のheadやlengthで畳み込んでしまっているところです．この無駄パターンは，lengthを使うときにすこし注意すると，思いの外，頻発するパターンであることが判ります．
phiの部分を展開すると
code:haskell
phi [] = Nothing
phi (x:xs) = first runlen <$> psi (x:xs)
=> Just $ first runlen (x:ys, zs)
=> Just (runlen (x:ys), zs)
=> Just ((x,length (x:ys)), zs)
=> Just ((x,succ (length ys)), zs)
where
(ys,zs) = span (x ==) xs
spanは条件を満す要素が連続する先頭部分と残りの部分に分けるのですが，先頭部分はリストではなく，長さとするような変奏を採用をすると，lengthを呼び出さなくてもすみます．
code:haskell
span :: (a -> Bool) -> a -> (a,a) span p = para phi ([],[])
where
phi x (xs,(ys,zs))
| p x = (x:ys, zs)
| otherwise = ([], x:xs)
spanCount :: (a -> Bool) -> a -> (Int, a) spanCount p = para psi (0,[])
where
psi x (xs, mzs)
| p x = first succ mzs
| otherwise = (0,x:xs)
これを良く観察すると，自然数とリストの類似性が見えます．すなわち，
[] :: [a] と 0 :: Int の対応
(_ :) :: [a] -> [a]とsucc :: Int -> Intの対応
多相関数length :: [a] -> Int
runLength の最終版は，
code:haskell
runLength = unfoldr phi
where
phi [] = Nothing
phi (x:xs) = case spanCount (x ==) xs of
(m, zs) -> Just ((x, succ m) , zs)