{-# LANGUAGE RankNTypes #-}
import Data.Monoid

class Buildable f where
  build :: (forall m. Monoid m => (a -> m) -> m) -> f a

-- foldMap f (build g) = g f
-- build (\f -> foldMap f x) = x

instance Buildable [] where
  build f = appEndo (f (Endo . (:))) []
-- instance Buildable FMList where
--   build = FM

transform :: (Foldable f1, Buildable f2) => (forall m. Monoid m => (b -> m) -> (a -> m)) -> f1 a -> f2 b
transform f as = build (\g -> foldMap (f g) as)

fromFoldable :: (Foldable f, Buildable t) => f a -> t a
fromFoldable = transform id
fmapDefault f = transform (. f)
singleton a = build (\f -> f a)
memptyDefault :: Buildable f => f a
memptyDefault = build (const mempty) -- == build mempty
mappendDefault l r = build (\f -> foldMap f l <> foldMap f r)
cons a as = build (\f -> f a <> foldMap f as)
snoc as a = build (\f -> foldMap f as <> f a)
rev as = build (\f -> getDual $ foldMap (Dual . f) as)
flatten :: (Foldable f, Buildable f, Foldable g) => f (g a) -> f a
flatten = transform foldMap
filter p = transform (\f a -> if p a then f a else mempty)
unfold :: (Foldable f, Buildable t) => (b -> f (Either b a)) -> b -> t a
unfold g b = build (\f -> let go = foldMap (either go f) . g in go b)