Safe Haskell | None |
---|---|
Language | Haskell2010 |
Control.Recursion
Contents
Synopsis
- type family Base t :: * -> *
- class Functor (Base t) => Recursive t where
- class Functor (Base t) => Corecursive t where
- newtype Fix f = Fix {}
- newtype Mu f = Mu (forall a. (f a -> a) -> a)
- data Nu f = Nu (a -> f a) a
- data ListF a b
- data NonEmptyF a b = NonEmptyF a (Maybe b)
- hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
- prepro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (Base t a -> a) -> t -> a
- postpro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (a -> Base t a) -> a -> t
- mutu :: Recursive t => (Base t (a, a) -> a) -> (Base t (a, a) -> a) -> t -> a
- zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a
- para :: (Recursive t, Corecursive t) => (Base t (t, a) -> a) -> t -> a
- apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t
- hypo :: (Recursive t, Corecursive t) => (a -> Base t (Either t a)) -> (Base t (t, b) -> b) -> a -> b
- elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a
- coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b
- micro :: Corecursive a => (b -> Either a (Base a b)) -> b -> a
- meta :: (Corecursive t', Recursive t) => (a -> Base t' a) -> (b -> a) -> (Base t b -> b) -> t -> t'
- meta' :: Functor g => (f a -> a) -> (forall c. g c -> f c) -> (b -> g b) -> b -> a
- scolio :: Recursive t => (Base t (a, t) -> a) -> (Base t (a, t) -> t) -> t -> a
- cata :: Recursive t => (Base t a -> a) -> t -> a
- ana :: Corecursive t => (a -> Base t a) -> a -> t
- mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c
- mcata :: (forall y. (y -> c) -> f y -> c) -> Fix f -> c
- 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
- 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
- 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
Typeclasses
type family Base t :: * -> * Source #
Instances
type Base Natural Source # | |
Defined in Control.Recursion | |
type Base [a] Source # | |
Defined in Control.Recursion | |
type Base (NonEmpty a) Source # | |
Defined in Control.Recursion | |
type Base (Mu f) Source # | |
Defined in Control.Recursion | |
type Base (Nu f) Source # | |
Defined in Control.Recursion | |
type Base (Fix f) Source # | |
Defined in Control.Recursion | |
type Base (Fix f) Source # | |
Defined in Control.Recursion |
class Functor (Base t) => Recursive t where Source #
Minimal complete definition
Nothing
Methods
project :: t -> Base t t Source #
project :: (Generic t, Generic (Base t t), HCoerce (Rep t) (Rep (Base t t))) => t -> Base t t Source #
class Functor (Base t) => Corecursive t where Source #
Minimal complete definition
Nothing
Methods
embed :: Base t t -> t Source #
embed :: (Generic t, Generic (Base t t), HCoerce (Rep (Base t t)) (Rep t)) => Base t t -> t Source #
Instances
Corecursive Natural Source # | |
Corecursive [a] Source # | |
Defined in Control.Recursion | |
Corecursive (NonEmpty a) Source # | |
Functor f => Corecursive (Mu f) Source # | |
Functor f => Corecursive (Nu f) Source # | |
Functor f => Corecursive (Fix f) Source # | |
Types
Constructors
Mu (forall a. (f a -> a) -> a) |
Constructors
Nu (a -> f a) a |
Base functor for a list of type [a]
.
Instances
Functor (ListF a) Source # | |
Foldable (ListF a) Source # | |
Defined in Control.Recursion Methods fold :: Monoid m => ListF a m -> 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] # elem :: Eq a0 => a0 -> ListF a a0 -> Bool # maximum :: Ord a0 => ListF a a0 -> a0 # minimum :: Ord a0 => ListF a a0 -> a0 # | |
Traversable (ListF a) Source # | |
Instances
Functor (NonEmptyF a) Source # | |
Foldable (NonEmptyF a) Source # | |
Defined in Control.Recursion Methods fold :: Monoid m => NonEmptyF a m -> 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 # | |
Traversable (NonEmptyF a) Source # | |
Defined in Control.Recursion |
Recursion schemes
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b Source #
Hylomorphism; fold a structure while buildiung 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"
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
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
Monadic recursion schemes
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 #