-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A recursion schemes library for Haskell.
--
-- A performant recursion schemes library for Haskell with minimal
-- dependencies
@package recursion
@version 2.2.4.3
module Control.Recursion
type family Base t :: Type -> Type
class (Functor (Base t)) => Recursive t
project :: Recursive t => t -> Base t t
project :: (Recursive t, Generic t, Generic (Base t t), HCoerce (Rep t) (Rep (Base t t))) => t -> Base t t
class (Functor (Base t)) => Corecursive t
embed :: Corecursive t => Base t t -> t
embed :: (Corecursive t, Generic t, Generic (Base t t), HCoerce (Rep (Base t t)) (Rep t)) => Base t t -> t
newtype Fix f
Fix :: f (Fix f) -> Fix f
[unFix] :: Fix f -> f (Fix f)
newtype Mu f
Mu :: (forall a. (f a -> a) -> a) -> Mu f
data Nu f
Nu :: (a -> f a) -> a -> Nu f
-- | Base functor for a list of type [a].
data ListF a b
Cons :: a -> b -> ListF a b
Nil :: ListF a b
data NonEmptyF a b
NonEmptyF :: a -> Maybe b -> NonEmptyF a b
-- | Hylomorphism; fold a structure while building it up.
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
-- | Prepromorphism. Fold a structure while applying a natural
-- transformation at each step.
prepro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (Base t a -> a) -> t -> a
-- | Postpromorphism. Build up a structure, applying a natural
-- transformation along the way.
postpro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (a -> Base t a) -> a -> t
-- | 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
--
mutu :: Recursive t => (Base t (a, a) -> a) -> (Base t (a, 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]
--
zygo :: Recursive t => (Base t b -> b) -> (Base t (b, 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]
--
para :: (Recursive t, Corecursive t) => (Base t (t, a) -> a) -> t -> a
-- | 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]
--
apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t
-- | Hypomorphism.
hypo :: (Recursive t, Corecursive t) => (a -> Base t (Either t a)) -> (Base t (t, b) -> b) -> a -> b
-- | 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
--
elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a
-- | 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]
--
coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b
-- | 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]
--
micro :: Corecursive a => (b -> Either a (Base a b)) -> b -> a
-- | Gibbons' metamorphism. Tear down a structure, transform it, and then
-- build up a new structure
meta :: (Corecursive t', Recursive t) => (a -> Base t' a) -> (b -> a) -> (Base t b -> b) -> t -> t'
-- | Erwig's metamorphism. Essentially a hylomorphism with a natural
-- transformation in between. This allows us to use more than one functor
-- in a hylomorphism.
meta' :: Functor g => (f a -> a) -> (forall c. g c -> f c) -> (b -> g b) -> b -> a
-- | Catamorphism collapsing along two data types simultaneously.
scolio :: Recursive t => (Base t (a, t) -> a) -> (Base t (a, t) -> t) -> 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
--
cata :: Recursive t => (Base t a -> a) -> t -> a
-- | Anamorphism, meant to build up a structure recursively.
ana :: Corecursive t => (a -> Base t a) -> a -> t
-- | Mendler's histomorphism
--
-- See here for an example
mhisto :: (forall y. (y -> c) -> (y -> f y) -> 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
--
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
-- | See here for an example
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
instance Data.Traversable.Traversable (Control.Recursion.ListF a)
instance Data.Foldable.Foldable (Control.Recursion.ListF a)
instance GHC.Base.Functor (Control.Recursion.ListF a)
instance Data.Traversable.Traversable (Control.Recursion.NonEmptyF a)
instance Data.Foldable.Foldable (Control.Recursion.NonEmptyF a)
instance GHC.Base.Functor (Control.Recursion.NonEmptyF a)
instance Control.Recursion.Recursive GHC.Num.Natural.Natural
instance GHC.Base.Functor f => Control.Recursion.Recursive (Control.Recursion.Nu f)
instance GHC.Base.Functor f => Control.Recursion.Recursive (Control.Recursion.Mu f)
instance Control.Recursion.Recursive [a]
instance Control.Recursion.Recursive (GHC.Base.NonEmpty a)
instance GHC.Base.Functor f => Control.Recursion.Recursive (Control.Recursion.Fix f)
instance Control.Recursion.Corecursive GHC.Num.Natural.Natural
instance GHC.Base.Functor f => Control.Recursion.Corecursive (Control.Recursion.Nu f)
instance GHC.Base.Functor f => Control.Recursion.Corecursive (Control.Recursion.Mu f)
instance Control.Recursion.Corecursive [a]
instance Control.Recursion.Corecursive (GHC.Base.NonEmpty a)
instance GHC.Base.Functor f => Control.Recursion.Corecursive (Control.Recursion.Fix f)
instance Control.Recursion.HCoerce f g => Control.Recursion.HCoerce (GHC.Generics.M1 i c f) (GHC.Generics.M1 i c' g)
instance Control.Recursion.HCoerce (GHC.Generics.K1 i c) (GHC.Generics.K1 j c)
instance Control.Recursion.HCoerce GHC.Generics.U1 GHC.Generics.U1
instance Control.Recursion.HCoerce GHC.Generics.V1 GHC.Generics.V1
instance (Control.Recursion.HCoerce f g, Control.Recursion.HCoerce f' g') => Control.Recursion.HCoerce (f GHC.Generics.:*: f') (g GHC.Generics.:*: g')
instance (Control.Recursion.HCoerce f g, Control.Recursion.HCoerce f' g') => Control.Recursion.HCoerce (f GHC.Generics.:+: f') (g GHC.Generics.:+: g')
-- | This module contains GHC-specific functions
module Control.Recursion.GHC
-- | Should satisfy:
--
--
-- transverse sequenceA = pure
--
transverse :: (Recursive s, Corecursive t, Functor f) => (forall a. Base s (f a) -> f (Base t a)) -> s -> f t
cotransverse :: (Recursive s, Corecursive t, Functor f) => (forall a. f (Base s a) -> Base t (f a)) -> f s -> t
hoist :: (Recursive s, Corecursive t) => (forall a. Base s a -> Base t a) -> s -> t