$\newcommand{\defeq}{\mathrel{\mathop:}=}$

## 2008/04/03

### Unfold Fusion

map f . iterate f = iterate f . f        (*)


-- constructor
-- Maybe (A, B) is isomorphic to 1 + A * B
alpha :: Maybe (a, [a]) -> [a]
alpha Nothing       = []
alpha (Just (a, t)) = a : t

-- deconstructor
ahpla :: [a] -> Maybe (a, [a])
ahpla []       = Nothing
ahpla (x : xs) = Just (x, xs)

-- products
split f g a = (f a, g a)
cross f g   = split (f . fst) (g . snd)

-- base functor
listrF f g Nothing       = Nothing
listrF f g (Just (a, t)) = Just (cross f g (a, t))


unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f = alpha . listrF id (unfoldr f) . f

-- type functor
mapana :: (a -> b) -> [a] -> [b]
mapana f = unfoldr (listrF f id . ahpla)

iterate :: (a -> a) -> a -> [a]
iterate f = unfoldr (Just . split id f)


foldr :: (Maybe (a, b) -> b) -> [a] -> b
foldr f = f . listrF id (foldr f) . ahpla

mapcata :: (a -> b) -> [a] -> [b]
mapcata f = foldr (alpha . listrF f id)


Inductive lists 有 fusion law

h . foldr f = foldr g    <=    h . f = g . listrF id h


foldr f . mapcata g = foldr (f . listrF g id)


unfoldr f . h = unfoldr g    <=    f . h = listrF id h . g

mapana g . unfoldr f = unfoldr (listrF g id . f)


  map f . iterate f
=   { definition of iterate }
map f . unfoldr (Just . split id f)
=   { type functor fusion }
unfoldr (listrF f id . Just . split id f)
=   { definition of listF }
unfoldr (Just . cross f id . split id f)
=   { product functor }
unfoldr (Just . split f f)


  (Just . split id f) . f
=   { split fusion }
Just . split f (f . f)
=   { product functor }
Just . cross id f . split f f
=   { definition of listrF }
listrF id f . Just . split f f
=   { let g = Just . split f f }
listrF id f . g


iterate f . f = unfoldr (Just . split f f)


--

Labels: ,