Control.Recursion

Typeclasses

type family Base t :: Type -> Type

Instances

type Base Natural

Defined in Control.Recursion

type Base Natural = Maybe

type Base [a]

Defined in Control.Recursion

type Base [a] = ListF a

type Base (NonEmpty a)

Defined in Control.Recursion

type Base (NonEmpty a) = NonEmptyF a

type Base (Mu f)

Defined in Control.Recursion

type Base (Mu f) = f

type Base (Nu f)

Defined in Control.Recursion

type Base (Nu f) = f

type Base (Fix f)

Defined in Control.Recursion

type Base (Fix f) = f

type Base (Fix f)

Defined in Control.Recursion

type Base (Fix f) = f

class Functor (Base t) => Recursive t where

Minimal complete definition

Nothing

Methods

project :: t -> Base t t

default project :: (Generic t, Generic (Base t t), HCoerce (Rep t) (Rep (Base t t))) => t -> Base t t

Instances

Recursive Natural

Defined in Control.Recursion

Methods

project :: Natural -> Base Natural Natural

Recursive [a]

Defined in Control.Recursion

Methods

project :: [a] -> Base [a] [a]

Recursive (NonEmpty a)

Defined in Control.Recursion

Methods

project :: NonEmpty a -> Base (NonEmpty a) (NonEmpty a)

Functor f => Recursive (Mu f)

Defined in Control.Recursion

Methods

project :: Mu f -> Base (Mu f) (Mu f)

Functor f => Recursive (Nu f)

Defined in Control.Recursion

Methods

project :: Nu f -> Base (Nu f) (Nu f)

Functor f => Recursive (Fix f)

Defined in Control.Recursion

Methods

project :: Fix f -> Base (Fix f) (Fix f)

class Functor (Base t) => Corecursive t where

Minimal complete definition

Nothing

Methods

embed :: Base t t -> t

default embed :: (Generic t, Generic (Base t t), HCoerce (Rep (Base t t)) (Rep t)) => Base t t -> t

Instances

Corecursive Natural

Defined in Control.Recursion

Methods

embed :: Base Natural Natural -> Natural

Corecursive [a]

Defined in Control.Recursion

Methods

embed :: Base [a] [a] -> [a]

Corecursive (NonEmpty a)

Defined in Control.Recursion

Methods

embed :: Base (NonEmpty a) (NonEmpty a) -> NonEmpty a

Functor f => Corecursive (Mu f)

Defined in Control.Recursion

Methods

embed :: Base (Mu f) (Mu f) -> Mu f

Functor f => Corecursive (Nu f)

Defined in Control.Recursion

Methods

embed :: Base (Nu f) (Nu f) -> Nu f

Functor f => Corecursive (Fix f)

Defined in Control.Recursion

Methods

embed :: Base (Fix f) (Fix f) -> Fix f

Types

newtype Fix f

Constructors

Fix

Fields

• unFix :: f (Fix f)

Instances

Functor f => Corecursive (Fix f)

Defined in Control.Recursion

Methods

embed :: Base (Fix f) (Fix f) -> Fix f

Functor f => Recursive (Fix f)

Defined in Control.Recursion

Methods

project :: Fix f -> Base (Fix f) (Fix f)

type Base (Fix f)

Defined in Control.Recursion

type Base (Fix f) = f

type Base (Fix f)

Defined in Control.Recursion

type Base (Fix f) = f

newtype Mu f

Constructors

Mu (forall a. (f a -> a) -> a)

Instances

Functor f => Corecursive (Mu f)

Defined in Control.Recursion

Methods

embed :: Base (Mu f) (Mu f) -> Mu f

Functor f => Recursive (Mu f)

Defined in Control.Recursion

Methods

project :: Mu f -> Base (Mu f) (Mu f)

type Base (Mu f)

Defined in Control.Recursion

type Base (Mu f) = f

data Nu f

Constructors

forall a. Nu (a -> f a) a

Instances

Functor f => Corecursive (Nu f)

Defined in Control.Recursion

Methods

embed :: Base (Nu f) (Nu f) -> Nu f

Functor f => Recursive (Nu f)

Defined in Control.Recursion

Methods

project :: Nu f -> Base (Nu f) (Nu f)

type Base (Nu f)

Defined in Control.Recursion

type Base (Nu f) = f

data ListF a b

Base functor for a list of type [a].

Constructors

Cons a b

Nil

Instances

Functor (ListF a)

Defined in Control.Recursion

Methods

fmap :: (a0 -> b) -> ListF a a0 -> ListF a b

(<$) :: a0 -> ListF a b -> ListF a a0

Foldable (ListF a)

Defined in Control.Recursion

Methods

fold :: Monoid m => ListF a m -> m

foldMap :: Monoid m => (a0 -> m) -> ListF a a0 -> m

foldMap' :: Monoid m => (a0 -> m) -> ListF a a0 -> m

foldr :: (a0 -> b -> b) -> b -> ListF a a0 -> b

foldr' :: (a0 -> b -> b) -> b -> ListF a a0 -> b

foldl :: (b -> a0 -> b) -> b -> ListF a a0 -> b

foldl' :: (b -> a0 -> b) -> b -> ListF a a0 -> b

foldr1 :: (a0 -> a0 -> a0) -> ListF a a0 -> a0

foldl1 :: (a0 -> a0 -> a0) -> ListF a a0 -> a0

toList :: ListF a a0 -> [a0]

null :: ListF a a0 -> Bool

length :: ListF a a0 -> Int

elem :: Eq a0 => a0 -> ListF a a0 -> Bool

maximum :: Ord a0 => ListF a a0 -> a0

minimum :: Ord a0 => ListF a a0 -> a0

sum :: Num a0 => ListF a a0 -> a0

product :: Num a0 => ListF a a0 -> a0

Traversable (ListF a)

Defined in Control.Recursion

Methods

traverse :: Applicative f => (a0 -> f b) -> ListF a a0 -> f (ListF a b)

sequenceA :: Applicative f => ListF a (f a0) -> f (ListF a a0)

mapM :: Monad m => (a0 -> m b) -> ListF a a0 -> m (ListF a b)

sequence :: Monad m => ListF a (m a0) -> m (ListF a a0)

data NonEmptyF a b

Constructors

NonEmptyF a (Maybe b)

Instances

Functor (NonEmptyF a)

Defined in Control.Recursion

Methods

fmap :: (a0 -> b) -> NonEmptyF a a0 -> NonEmptyF a b

(<$) :: a0 -> NonEmptyF a b -> NonEmptyF a a0

Foldable (NonEmptyF a)

Defined in Control.Recursion

Methods

fold :: Monoid m => NonEmptyF a m -> m

foldMap :: Monoid m => (a0 -> m) -> NonEmptyF a a0 -> m

foldMap' :: Monoid m => (a0 -> m) -> NonEmptyF a a0 -> m

foldr :: (a0 -> b -> b) -> b -> NonEmptyF a a0 -> b

foldr' :: (a0 -> b -> b) -> b -> NonEmptyF a a0 -> b

foldl :: (b -> a0 -> b) -> b -> NonEmptyF a a0 -> b

foldl' :: (b -> a0 -> b) -> b -> NonEmptyF a a0 -> b

foldr1 :: (a0 -> a0 -> a0) -> NonEmptyF a a0 -> a0

foldl1 :: (a0 -> a0 -> a0) -> NonEmptyF a a0 -> a0

toList :: NonEmptyF a a0 -> [a0]

null :: NonEmptyF a a0 -> Bool

length :: NonEmptyF a a0 -> Int

elem :: Eq a0 => a0 -> NonEmptyF a a0 -> Bool

maximum :: Ord a0 => NonEmptyF a a0 -> a0

minimum :: Ord a0 => NonEmptyF a a0 -> a0

sum :: Num a0 => NonEmptyF a a0 -> a0

product :: Num a0 => NonEmptyF a a0 -> a0

Traversable (NonEmptyF a)

Defined in Control.Recursion

Methods

traverse :: Applicative f => (a0 -> f b) -> NonEmptyF a a0 -> f (NonEmptyF a b)

sequenceA :: Applicative f => NonEmptyF a (f a0) -> f (NonEmptyF a a0)

mapM :: Monad m => (a0 -> m b) -> NonEmptyF a a0 -> m (NonEmptyF a b)

sequence :: Monad m => NonEmptyF a (m a0) -> m (NonEmptyF a a0)

Recursion schemes

hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b

Hylomorphism; fold a structure while building it up.

prepro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (Base t a -> a) -> t -> a

Prepromorphism. Fold a structure while applying a natural transformation at each step.

postpro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (a -> Base t a) -> a -> t

Postpromorphism. Build up a structure, applying a natural transformation along the way.

mutu :: Recursive t => (Base t (a, a) -> a) -> (Base t (a, a) -> a) -> t -> a

A mutumorphism.

>>> :{
let {
  even' :: Natural -> Bool ;
  even' = mutu o e
    where
      o :: Maybe (Bool, Bool) -> Bool
      o Nothing = False
      o (Just (_, b)) = b
      e :: Maybe (Bool, Bool) -> Bool
      e Nothing = True
      e (Just (_, b)) = b
}
:}

>>> even' 10
True

zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a

Zygomorphism (see here for a neat example)

>>> :set -XTypeFamilies
>>> import Data.Char (toUpper, toLower)
>>> :{
let {
  spongebobZygo :: String -> String ;
  spongebobZygo = zygo a pa
    where
      a :: ListF Char Bool -> Bool
      a Nil          = False
      a (Cons ' ' b) = b
      a (Cons ',' b) = b
      a (Cons _ b)   = not b
      pa :: ListF Char (Bool, String) -> String
      pa Nil                 = ""
      pa (Cons c (True, s))  = toUpper c : s
      pa (Cons c (False, s)) = toLower c : s
}
:}

>>> spongebobZygo "Hello, World"
"HeLlO, wOrLd"

>>> :set -XFlexibleContexts
>>> :{
let {
  succDiff :: Integral a => [a] -> [a] ;
  succDiff = zygo a pa
      where a Nil = Nothing
            a (Cons i _) = Just i
            pa Nil = []
            pa (Cons x (Nothing, xs)) = []
            pa (Cons x (Just y, xs)) = (y - x) : xs
}
:}

>>> succDiff [ i^2 | i <- [1..10] ]
[3,5,7,9,11,13,15,17,19]

para :: (Recursive t, Corecursive t) => (Base t (t, a) -> a) -> t -> a

Paramorphism

>>> :{
let {
  dedup :: Eq a => [a] -> [a] ;
  dedup = para pa
    where
      pa :: Eq a => ListF a ([a], [a]) -> [a]
      pa Nil = []
      pa (Cons x (past, xs)) = if x `elem` past then xs else x:xs
}
:}

>>> dedup [1,1,2]
[1,2]

apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t

Apomorphism. Compare micro.

>>> :{
let {
  isInteger :: (RealFrac a) => a -> Bool ;
  isInteger = idem (realToFrac . floor)
    where
      idem f x = x == f x
}
:}

>>> :{
let {
  continuedFraction :: (RealFrac a, Integral b) => a -> [b] ;
  continuedFraction = apo pc
    where
      pc x
        | isInteger x = go $ Left []
        | otherwise   = go $ Right alpha
          where
            alpha = 1 / (x - realToFrac (floor x))
            go    = Cons (floor x)
}
:}

>>> take 13 $ continuedFraction pi
[3,7,15,1,292,1,1,1,2,1,3,1,14]

>>> :{
let {
  integerToWordList :: Integral a => a -> a -> [a] ;
  integerToWordList base = apo pc
    where
      pc i | i < base  = Cons (fromIntegral i) (Left [])
           | otherwise = Cons (fromIntegral (i `mod` base)) (Right (i `div` base))
}
:}

>>> integerToWordList 2 5
[1,0,1]

hypo :: (Recursive t, Corecursive t) => (a -> Base t (Either t a)) -> (Base t (t, b) -> b) -> a -> b

Hypomorphism.

Since: 2.2.3.0

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

Elgot algebra (see this paper)

>>> :{
let {
  collatzLength :: Integer -> Integer ;
  collatzLength = elgot a pc
    where
      pc :: Integer -> Either Integer (ListF Integer Integer)
      pc 1 = Left 1
      pc n
        | n `mod` 2 == 0 = Right $ Cons n (div n 2)
        | otherwise = Right $ Cons n (3 * n + 1)
      a :: ListF Integer Integer -> Integer
      a Nil        = 0
      a (Cons _ x) = x + 1
}
:}

>>> collatzLength 2223
183

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

Co-(Elgot algebra)

>>> import Data.Word (Word64)
>>> let base = (2 ^ (64 :: Int)) :: Integer
>>> :{
let {
  integerToWordList :: Integer -> [Word64] ;
  integerToWordList = coelgot pa c
    where
      c i = Cons (fromIntegral (i `mod` (2 ^ (64 :: Int)))) (i `div` (2 ^ (64 :: Int)))
      pa (i, ws) | i < 2 ^ (64 :: Int) = [fromIntegral i]
                 | otherwise = embed ws
}
:}

>>> integerToWordList 340282366920938463463374607431768211457
[1,0,1]

micro :: Corecursive a => (b -> Either a (Base a b)) -> b -> a

Anamorphism allowing shortcuts. Compare apo

>>> :{
let {
  collatzSequence :: Integer -> [Integer] ;
  collatzSequence = micro pc
    where
      pc :: Integer -> Either [Integer] (ListF Integer Integer)
      pc 1 = Left [1]
      pc n
        | n `mod` 2 == 0 = Right $ Cons n (div n 2)
        | otherwise = Right $ Cons n (3 * n + 1)
}
:}

>>> collatzSequence 13
[13,40,20,10,5,16,8,4,2,1]

meta :: (Corecursive t', Recursive t) => (a -> Base t' a) -> (b -> a) -> (Base t b -> b) -> t -> t'

Gibbons' metamorphism. Tear down a structure, transform it, and then build up a new structure

meta' :: Functor g => (f a -> a) -> (forall c. g c -> f c) -> (b -> g b) -> b -> a

Erwig's metamorphism. Essentially a hylomorphism with a natural transformation in between. This allows us to use more than one functor in a hylomorphism.

scolio :: Recursive t => (Base t (a, t) -> a) -> (Base t (a, t) -> t) -> t -> a

Catamorphism collapsing along two data types simultaneously.

cata :: Recursive t => (Base t a -> a) -> t -> a

Catamorphism. Folds a structure. (see here)

>>> :{
let {
  sum' :: (Num a) => [a] -> a ;
  sum' = cata a
    where
      a Nil         = 0
      a (Cons x xs) = x + xs
}
:}

>>> sum' [1..100]
5050

ana :: Corecursive t => (a -> Base t a) -> a -> t

Anamorphism, meant to build up a structure recursively.

Mendler-style recursion schemes

mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c

Mendler's histomorphism

See here for an example

mcata :: (forall y. (y -> c) -> f y -> c) -> Fix f -> c

Mendler's catamorphism

>>> import Data.Word (Word64)
>>> let asFix = cata Fix
>>> let base = (2 ^ (64 :: Int)) :: Integer
>>> :{
let {
  wordListToInteger :: [Word64] -> Integer ;
  wordListToInteger = mcata ma . asFix
    where
      ma f (Cons x xs) = fromIntegral x + base * f xs
      ma _ Nil         = 0
}
:}

>>> wordListToInteger [1,0,1]
340282366920938463463374607431768211457

mzygo :: (forall y. (y -> b) -> f y -> b) -> (forall y. (y -> c) -> (y -> b) -> f y -> c) -> Fix f -> c

Since: 2.2.5.0

mpara :: (forall y. (y -> c) -> (y -> Fix f) -> f y -> c) -> Fix f -> c

Since: 2.2.5.0

mana :: (forall y. (x -> y) -> x -> f y) -> x -> Fix f

Since: 2.2.5.0

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

Since: 2.2.5.0

mapo :: (forall y. (Fix f -> y) -> (x -> y) -> x -> f y) -> x -> Fix f

Since: 2.2.5.0

Monadic recursion schemes

cataM :: (Recursive t, Traversable (Base t), Monad m) => (Base t a -> m a) -> t -> m a

anaM :: (Corecursive t, Traversable (Base t), Monad m) => (a -> m (Base t a)) -> a -> m t

hyloM :: (Traversable f, Monad m) => (f b -> m b) -> (a -> m (f a)) -> a -> m b

zygoM :: (Recursive t, Traversable (Base t), Monad m) => (Base t b -> m b) -> (Base t (b, a) -> m a) -> t -> m a

zygoM' :: (Recursive t, Traversable (Base t), Monad m) => (Base t b -> m b) -> (Base t (b, a) -> m a) -> t -> m a

See here for an example

scolioM :: (Recursive t, Traversable (Base t), Monad m) => (Base t (t, a) -> m t) -> (Base t (t, a) -> m a) -> t -> m a

scolioM' :: (Recursive t, Traversable (Base t), Monad m) => (Base t (t, a) -> m t) -> (Base t (t, a) -> m a) -> t -> m a

coelgotM :: (Traversable f, Monad m) => ((a, f b) -> m b) -> (a -> m (f a)) -> a -> m b

elgotM :: (Traversable f, Monad m) => (f a -> m a) -> (b -> m (Either a (f b))) -> b -> m a

paraM :: (Recursive t, Corecursive t, Traversable (Base t), Monad m) => (Base t (t, a) -> m a) -> t -> m a

mutuM :: (Recursive t, Traversable (Base t), Monad m) => (Base t (a, a) -> m a) -> (Base t (a, a) -> m a) -> t -> m a

mutuM' :: (Recursive t, Traversable (Base t), Monad m) => (Base t (a, a) -> m a) -> (Base t (a, a) -> m a) -> t -> m a

microM :: (Corecursive a, Traversable (Base a), Monad m) => (b -> m (Either a (Base a b))) -> b -> m a

Helper functions

lambek :: (Recursive t, Corecursive t) => t -> Base t t

colambek :: (Recursive t, Corecursive t) => Base t t -> t

refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t