Safe Haskell	None
Language	Haskell2010

Haskus.Utils.Functor

Contents

Simple API
Recursion schemes
Higher-order recursion schemes

Description

Functor and recursion schemes

Simple API is intended to be easier to understand (e.g. they don't use xxmorphism and xxxalgebra jargon but tree-traversal-like terms).

Synopsis

type BottomUpT a f = f a -> a
bottomUp :: Recursive t => (Base t a -> a) -> t -> a
type BottomUpOrigT t a f = f (t, a) -> a
bottomUpOrig :: Recursive t => (Base t (t, a) -> a) -> t -> a
type TopDownStopT a f = f a -> Either (f a) a
topDownStop :: (Recursive t, Corecursive t) => (Base t t -> Either (Base t t) t) -> t -> t
module Data.Functor.Classes
cotransverse :: (Recursive s, Corecursive t, Functor f) => (forall a. f (Base s a) -> Base t (f a)) -> f s -> t
transverse :: (Recursive s, Corecursive t, Functor f) => (forall a. Base s (f a) -> f (Base t a)) -> s -> f t
cataA :: Recursive t => (Base t (f a) -> f a) -> t -> f a
zygoHistoPrepro :: (Corecursive t, Recursive t) => (Base t b -> b) -> (forall c. Base t c -> Base t c) -> (Base t (EnvT b (Cofree (Base t)) a) -> a) -> t -> a
coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b
elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a
mfutu :: (forall y. (f y -> y) -> (x -> y) -> x -> f y) -> x -> Fix f
mapo :: (forall y. (Fix f -> y) -> (x -> y) -> x -> f y) -> x -> Fix f
mana :: (forall y. (x -> y) -> x -> f y) -> x -> Fix f
mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c
mzygo :: (forall y. (y -> b) -> f y -> b) -> (forall y. (y -> c) -> (y -> b) -> f y -> c) -> Fix f -> c
mpara :: (forall y. (y -> c) -> (y -> Fix f) -> f y -> c) -> Fix f -> c
mcata :: (forall y. (y -> c) -> f y -> c) -> Fix f -> c
gchrono :: (Functor f, Functor w, Functor m, Comonad w, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall c. m (f c) -> f (m c)) -> (f (CofreeT f w b) -> b) -> (a -> f (FreeT f m a)) -> a -> b
chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b
distGHisto :: (Functor f, Functor h) => (forall b. f (h b) -> h (f b)) -> f (CofreeT f h a) -> CofreeT f h (f a)
distHisto :: Functor f => f (Cofree f a) -> Cofree f (f a)
ghisto :: (Recursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (CofreeT (Base t) w a) -> a) -> t -> a
histo :: Recursive t => (Base t (Cofree (Base t) a) -> a) -> t -> a
distGApoT :: (Functor f, Functor m) => (b -> f b) -> (forall c. m (f c) -> f (m c)) -> ExceptT b m (f a) -> f (ExceptT b m a)
distGApo :: Functor f => (b -> f b) -> Either b (f a) -> f (Either b a)
distApo :: Recursive t => Either t (Base t a) -> Base t (Either t a)
gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t (Either b a)) -> a -> t
distZygoT :: (Functor f, Comonad w) => (f b -> b) -> (forall c. f (w c) -> w (f c)) -> f (EnvT b w a) -> EnvT b w (f a)
gzygo :: (Recursive t, Comonad w) => (Base t b -> b) -> (forall c. Base t (w c) -> w (Base t c)) -> (Base t (EnvT b w a) -> a) -> t -> a
distZygo :: Functor f => (f b -> b) -> f (b, a) -> (b, f a)
zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a
refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t
hoist :: (Recursive s, Corecursive t) => (forall a. Base s a -> Base t a) -> s -> t
distGFutu :: (Functor f, Functor h) => (forall b. h (f b) -> f (h b)) -> FreeT f h (f a) -> f (FreeT f h a)
distFutu :: Functor f => Free f (f a) -> f (Free f a)
gfutu :: (Corecursive t, Functor m, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (a -> Base t (FreeT (Base t) m a)) -> a -> t
futu :: Corecursive t => (a -> Base t (Free (Base t) a)) -> a -> t
grefold :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b
ghylo :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b
distAna :: Functor f => Identity (f a) -> f (Identity a)
gunfold :: (Corecursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (a -> Base t (m a)) -> a -> t
gana :: (Corecursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (a -> Base t (m a)) -> a -> t
distCata :: Functor f => f (Identity a) -> Identity (f a)
gfold :: (Recursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (w a) -> a) -> t -> a
gcata :: (Recursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (w a) -> a) -> t -> a
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
unfold :: Corecursive t => (a -> Base t a) -> a -> t
fold :: Recursive t => (Base t a -> a) -> t -> a
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
distParaT :: (Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> Base t (EnvT t w a) -> EnvT t w (Base t a)
distPara :: Corecursive t => Base t (t, a) -> (t, Base t a)
type family Base t :: Type -> Type
class Functor (Base t) => Recursive t where
- project :: t -> Base t t
- cata :: (Base t a -> a) -> t -> a
- para :: (Base t (t, a) -> a) -> t -> a
- gpara :: (Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (EnvT t w a) -> a) -> t -> a
- prepro :: Corecursive t => (forall b. Base t b -> Base t b) -> (Base t a -> a) -> t -> a
- gprepro :: (Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (forall c. Base t c -> Base t c) -> (Base t (w a) -> a) -> t -> a
class Functor (Base t) => Corecursive t where
- embed :: Base t t -> t
- ana :: (a -> Base t a) -> a -> t
- apo :: (a -> Base t (Either t a)) -> a -> t
- postpro :: Recursive t => (forall b. Base t b -> Base t b) -> (a -> Base t a) -> a -> t
- gpostpro :: (Recursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (forall c. Base t c -> Base t c) -> (a -> Base t (m a)) -> a -> t
type Algebra f a = f a -> a
type CoAlgebra f a = a -> f a
type RAlgebra f t a = f (t, a) -> a
type RCoAlgebra f t a = a -> f (Either t a)
type (~>) f g = forall a. f a -> g a
type NatM m f g = forall a. f a -> m (g a)
type family HBase (h :: k -> Type) :: (k -> Type) -> k -> Type
type HAlgebra h f = h f ~> f
type HAlgebraM m h f = NatM m (h f) f
type HGAlgebra w h a = h (w a) ~> a
type HGAlgebraM w m h a = NatM m (h (w a)) a
type HCoalgebra h f = f ~> h f
type HCoalgebraM m h f = NatM m f (h f)
type HGCoalgebra m h a = a ~> h (m a)
type HGCoalgebraM n m h a = NatM m a (h (n a))
class HFunctor (h :: (k -> Type) -> k -> Type) where
- hfmap :: (f ~> g) -> h f ~> h g
class HFunctor h => HFoldable (h :: (k -> Type) -> k -> Type) where
- hfoldMap :: Monoid m => (forall b. f b -> m) -> h f a -> m
class HFoldable h => HTraversable (h :: (k -> Type) -> k -> Type) where
- htraverse :: Applicative e => NatM e f g -> NatM e (h f) (h g)
class HFunctor (HBase h) => HRecursive (h :: k -> Type) where
- hproject :: HCoalgebra (HBase h) h
- hcata :: HAlgebra (HBase h) f -> h ~> f
class HFunctor (HBase h) => HCorecursive (h :: k -> Type) where
- hembed :: HAlgebra (HBase h) h
- hana :: HCoalgebra (HBase h) f -> f ~> h
hhylo :: HFunctor f => HAlgebra f b -> HCoalgebra f a -> a ~> b
hcataM :: (Monad m, HTraversable (HBase h), HRecursive h) => HAlgebraM m (HBase h) f -> h a -> m (f a)
hlambek :: (HRecursive h, HCorecursive h) => HCoalgebra (HBase h) h
hpara :: (HFunctor (HBase h), HRecursive h) => HGAlgebra (Product h) (HBase h) a -> h ~> a
hparaM :: (HTraversable (HBase h), HRecursive h, Monad m) => HGAlgebraM (Product h) m (HBase h) a -> NatM m h a
hanaM :: (Monad m, HTraversable (HBase h), HCorecursive h) => HCoalgebraM m (HBase h) f -> f a -> m (h a)
hcolambek :: HRecursive h => HCorecursive h => HAlgebra (HBase h) h
hapo :: HCorecursive h => HGCoalgebra (Sum h) (HBase h) a -> a ~> h
hapoM :: (HCorecursive h, HTraversable (HBase h), Monad m) => HGCoalgebraM (Sum h) m (HBase h) a -> NatM m a h
hhyloM :: (HTraversable t, Monad m) => HAlgebraM m t h -> HCoalgebraM m t f -> f a -> m (h a)

Simple API

type BottomUpT a f = f a -> a Source #

bottomUp :: Recursive t => (Base t a -> a) -> t -> a Source #

Bottom-up traversal (catamorphism)

type BottomUpOrigT t a f = f (t, a) -> a Source #

bottomUpOrig :: Recursive t => (Base t (t, a) -> a) -> t -> a Source #

Bottom-up traversal with original value (paramorphism)

type TopDownStopT a f = f a -> Either (f a) a Source #

topDownStop :: (Recursive t, Corecursive t) => (Base t t -> Either (Base t t) t) -> t -> t Source #

Perform a top-down traversal

Right: stop the traversal ("right" value obtained) Left: continue the traversal recursively on the new value

Recursion schemes

module Data.Functor.Classes

cotransverse :: (Recursive s, Corecursive t, Functor f) => (forall a. f (Base s a) -> Base t (f a)) -> f s -> t #

A coeffectful version of hoist.

Properties:

cotransverse distAna = runIdentity

Examples:

Stateful transformations:

>>> :{
cotransverse
  (\(u, b) -> case b of
    Nil -> Nil
    Cons x a -> Cons (if u then toUpper x else x) (not u, a))
  (True, "foobar") :: String
:}
"FoObAr"

We can implement a variant of zipWith

>>> data Pair a = Pair a a deriving Functor

>>> :{
let zipWith' :: forall a b. (a -> a -> b) -> [a] -> [a] -> [b]
    zipWith' f xs ys = cotransverse g (Pair xs ys) where
      g :: Pair (ListF a c) -> ListF b (Pair c)
      g (Pair Nil        _)          = Nil
      g (Pair _          Nil)        = Nil
      g (Pair (Cons x a) (Cons y b)) = Cons (f x y) (Pair a b)
    :}

>>> zipWith' (*) [1,2,3] [4,5,6]
[4,10,18]

>>> zipWith' (*) [1,2,3] [4,5,6,8]
[4,10,18]

>>> zipWith' (*) [1,2,3,3] [4,5,6]
[4,10,18]

transverse :: (Recursive s, Corecursive t, Functor f) => (forall a. Base s (f a) -> f (Base t a)) -> s -> f t #

An effectful version of hoist.

Properties:

transverse sequenceA = pure

Examples:

The weird type of first argument allows user to decide an order of sequencing:

>>> transverse (\x -> print (void x) *> sequence x) "foo" :: IO String
Cons 'f' ()
Cons 'o' ()
Cons 'o' ()
Nil
"foo"

>>> transverse (\x -> sequence x <* print (void x)) "foo" :: IO String
Nil
Cons 'o' ()
Cons 'o' ()
Cons 'f' ()
"foo"

cataA :: Recursive t => (Base t (f a) -> f a) -> t -> f a #

A specialization of cata for effectful folds.

cataA is the same as cata, but with a more specialized type. The only reason it exists is to make it easier to discover how to use this library with effects.

For our running example, let's improve the output format of our pretty-printer by using indentation. To do so, we will need to keep track of the current indentation level. We will do so using a Reader Int effect. Our recursive positions will thus contain Reader Int String actions, not Strings. This means we need to run those actions in order to get the results.

>>> :{
let pprint2 :: Tree Int -> String
    pprint2 = flip runReader 0 . cataA go
      where
        go :: TreeF Int (Reader Int String)
           -> Reader Int String
        go (NodeF i rss) = do
          -- rss :: [Reader Int String]
          -- ss  :: [String]
          ss <- local (+ 2) $ sequence rss
          indent <- ask
          let s = replicate indent ' ' ++ "* " ++ show i
          pure $ intercalate "\n" (s : ss)
:}

>>> putStrLn $ pprint2 myTree
* 0
  * 1
  * 2
  * 3
    * 31
      * 311
        * 3111
        * 3112

The fact that the recursive positions contain Reader actions instead of Strings gives us some flexibility. Here, we are able to increase the indentation by running those actions inside a local block. More generally, we can control the order of their side-effects, interleave them with other effects, etc.

A similar technique is to specialize cata so that the result is a function. This makes it possible for data to flow down in addition to up. In this modified version of our running example, the indentation level flows down from the root to the leaves, while the resulting strings flow up from the leaves to the root.

>>> :{
let pprint3 :: Tree Int -> String
    pprint3 t = cataA go t 0
      where
        go :: TreeF Int (Int -> String)
           -> Int -> String
        go (NodeF i fs) indent =
          -- fs :: [Int -> String]
          let indent' = indent + 2
              ss = map (\f -> f indent') fs
              s = replicate indent ' ' ++ "* " ++ show i
          in intercalate "\n" (s : ss)
:}

>>> putStrLn $ pprint3 myTree
* 0
  * 1
  * 2
  * 3
    * 31
      * 311
        * 3111
        * 3112

zygoHistoPrepro :: (Corecursive t, Recursive t) => (Base t b -> b) -> (forall c. Base t c -> Base t c) -> (Base t (EnvT b (Cofree (Base t)) a) -> a) -> t -> a #

Zygohistomorphic prepromorphisms:

A corrected and modernized version of http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms

coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b #

Elgot coalgebras: http://comonad.com/reader/2008/elgot-coalgebras/

elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a #

Elgot algebras

mfutu :: (forall y. (f y -> y) -> (x -> y) -> x -> f y) -> x -> Fix f #

Mendler-style course-of-values coiteration