{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RankNTypes #-}
module RecursionSchemes.Extra where
import Control.Monad ((>=>))
import Data.Bifunctor
import Control.Comonad
import Control.Comonad.Cofree
import Control.Foldl
import Data.Functor.Foldable
Here is a collection of implementations of recursion schemes that are not implemented in recursion-schemes.
Dynamorphism is the recursion schemes proposed by Kabanov and Vene to realize dynamic programming[^1]. Simply put, it is represented as a refold of Anamorphism and Histomorphism.However, here we implement Dynamorphism as an extension of Hylomorphism in order not to lose generality.
dyna :: Functor f => (f (Cofree f x) -> x) -> (y -> f y) -> (y -> x)
dyna phi psi = extract . hylo ap psi
where ap f = phi f :< f
Multimorphism is a recursion schemes that deals with the two recursive type at the same time[^2].
mmulti :: (Recursive f, Recursive g) => (forall a b. (a -> b -> c) -> Base f a -> Base g b -> c) -> f -> g -> c
mmulti psi f g = psi (mmulti psi) (project f) (project g)
mmulti can also be implemented using Day convolution as type (Day (Base f) (Base g) c -> c) -> f -> g -> c[^3].
Since Co f is the right adjoint of Day f, we can rewrite mmulti using transpose[^4].
mmulti' :: (Recursive f, Recursive g) => (forall r. Base g c -> Base f (c -> r) -> r) -> f -> g -> c
This idea was introduced by Bartosz Milewski as an extension of Foldl to RecursionSchemes[^5]. Here we use endomorphsm instead of monoids to match the implementation in the Foldl library.
type FoldAlgebra f = forall x. f (x -> x) (x -> x) -> (x -> x)
cat :: (Bifunctor f, Functor (f a)) => FoldAlgebra f -> Fold a b -> Fix (f a) -> b
cat falg (Fold step begin done) = done . ($ begin) . cata (falg . bimap (flip step) id)
Monadic catamorphism[^6] can be implemented as a special case of ordinary catamorphism[^7].
cataM :: (Traversable (Base t), Monad m, Recursive t)
=> (Base t c -> m c) -> t -> m c
cataM = cata . (sequence >=>)
You can also implement monadic paramorphism in a similar way.
paraM :: (Recursive t, Monad m, Traversable (Base t))
=> (Base t (t, c) -> m c) -> t -> m c
paraM = para . (sequence . fmap sequence >=>)
[1] Kabanov, Jevgeni, and Varmo Vene. “Recursion schemes for dynamic programming.” International Conference on Mathematics of Program Construction. Springer, Berlin, Heidelberg, 2006.
[2] Uustalu, Tarmo, and Varmo Vene. “Coding recursion a la Mendler.” Department of Computer Science, Utrecht University. 2000.
[3] sellout/yaya - Yaya.Fold#cata2
[4] kan-extensions - Control.Monad.Co
[5] Monoidal Catamorphisms | Bartosz Milewski’s Programming Cafe
[6] Fokkinga, Maarten Maria. Monadic maps and folds for arbitrary datatypes. University of Twente, Department of Computer Science, 1994.
[7] Suggestion: Add monadic variants of various …morphism functions. · Issue #3 · ekmett/recursion-schemes