recursion-2.2.5.0: A recursion schemes library for Haskell.
Safe HaskellNone
LanguageHaskell2010

Control.Recursion

Synopsis

Typeclasses

type family Base t :: Type -> Type Source #

Instances

Instances details
type Base Natural Source # 
Instance details

Defined in Control.Recursion

type Base [a] Source # 
Instance details

Defined in Control.Recursion

type Base [a] = ListF a
type Base (NonEmpty a) Source # 
Instance details

Defined in Control.Recursion

type Base (NonEmpty a) = NonEmptyF a
type Base (Mu f) Source # 
Instance details

Defined in Control.Recursion

type Base (Mu f) = f
type Base (Nu f) Source # 
Instance details

Defined in Control.Recursion

type Base (Nu f) = f
type Base (Fix f) Source # 
Instance details

Defined in Control.Recursion

type Base (Fix f) = f
type Base (Fix f) Source # 
Instance details

Defined in Control.Recursion

type Base (Fix f) = f

class Functor (Base t) => Recursive t where Source #

Minimal complete definition

Nothing

Methods

project :: t -> Base t t Source #

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

Instances

Instances details
Recursive Natural Source # 
Instance details

Defined in Control.Recursion

Recursive [a] Source # 
Instance details

Defined in Control.Recursion

Methods

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

Recursive (NonEmpty a) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Recursive (Mu f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Recursive (Nu f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Recursive (Fix f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

class Functor (Base t) => Corecursive t where Source #

Minimal complete definition

Nothing

Methods

embed :: Base t t -> t Source #

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

Instances

Instances details
Corecursive Natural Source # 
Instance details

Defined in Control.Recursion

Corecursive [a] Source # 
Instance details

Defined in Control.Recursion

Methods

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

Corecursive (NonEmpty a) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Corecursive (Mu f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Corecursive (Nu f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Corecursive (Fix f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Types

newtype Fix f Source #

Constructors

Fix 

Fields

Instances

Instances details
Functor f => Corecursive (Fix f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Recursive (Fix f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

type Base (Fix f) Source # 
Instance details

Defined in Control.Recursion

type Base (Fix f) = f
type Base (Fix f) Source # 
Instance details

Defined in Control.Recursion

type Base (Fix f) = f

newtype Mu f Source #

Constructors

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

Instances

Instances details
Functor f => Corecursive (Mu f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Recursive (Mu f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

type Base (Mu f) Source # 
Instance details

Defined in Control.Recursion

type Base (Mu f) = f

data Nu f Source #

Constructors

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

Instances

Instances details
Functor f => Corecursive (Nu f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

Functor f => Recursive (Nu f) Source # 
Instance details

Defined in Control.Recursion

Methods

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

type Base (Nu f) Source # 
Instance details

Defined in Control.Recursion

type Base (Nu f) = f

data ListF a b Source #

Base functor for a list of type [a].

Constructors

Cons a b 
Nil 

Instances

Instances details
Functor (ListF a) Source # 
Instance details

Defined in Control.Recursion

Methods

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

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

Foldable (ListF a) Source # 
Instance details

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) Source # 
Instance details

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 Source #

Constructors

NonEmptyF a (Maybe b) 

Instances

Instances details
Functor (NonEmptyF a) Source # 
Instance details

Defined in Control.Recursion

Methods

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

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

Foldable (NonEmptyF a) Source # 
Instance details

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) Source # 
Instance details

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

Hypomorphism.

Since: 2.2.3.0

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

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 Source #

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 Source #

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' Source #

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 Source #

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 Source #

Catamorphism collapsing along two data types simultaneously.

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

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 Source #

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 Source #

Mendler's histomorphism

See here for an example

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

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 Source #

Since: 2.2.5.0

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

Since: 2.2.5.0

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

Since: 2.2.5.0

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

Since: 2.2.5.0

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

Since: 2.2.5.0

Monadic recursion schemes

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

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

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

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

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

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 Source #

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

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

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

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

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

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

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

Helper functions

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

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

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