Real-world applications of zygohistomorphic prepromorphisms
HaskellFunctional ProgrammingCategory TheoryHaskell Problem Overview
Yes, these ones:
{-#LANGUAGE TypeOperators, RankNTypes #-}
import Control.Morphism.Zygo
import Control.Morphism.Prepro
import Control.Morphism.Histo
import Control.Functor.Algebra
import Control.Functor.Extras
import Control.Functor.Fix
import Control.Comonad.Cofree
zygohistomorphic_prepromorphism
:: Functor f
=> Algebra f b
-> GAlgebra f (ZygoT (Cofree f) b) a
-> (f :~> f)
-> FixF f
-> a
zygohistomorphic_prepromorphism f
= g_prepro (distZygoT (liftAlgebra f) (distHisto id))
Yes, I know that they're a (HHOS) joke. I'm looking for a real-world example for simple hack value and last, but not least, to add it to the wiki saying "This is the idiomatic way to express XYZ". I will put a bounty on this should you fail to come up with a solution. If you're completely lost on what they're about, Edward posted a short explanation on reddit.
Eligible Answers must:
-
do something at least remotely and theoretically computationally useful. That is, answers that reduce to
id
are out. -
use all the features of the scheme, no passing in of id, or const, or equivalent.
-
not equally well be expressible by a simple, vanilla fold or such, so don't merely implement
product
in a meandering way.
Bonus points will be given to:
-
Well-known problem or algorithm
-
solved, respectively expressed, in an unusual way that gains
-
clarity and/or performance
-
and/or hack value
-
and/or lulz, in roughly that order, as well as
-
high-ranking answers (yay democracy)
Please also note Edward's answer below. What ZHPM implementation you use is your choice.
Haskell Solutions
Solution 1 - Haskell
Sharon Curtis and Shin-Cheng Mu have a Functional Pearl using zygomorphisms to find maximally dense segments (a generalization of maximum segment sums). Zygomorphisms are seemingly a good fit for sliding window problems once you are accustomed to them.
http://www.iis.sinica.edu.tw/~scm/2010/functional-pearl-maximally-dense-segments/
I'd nominate the authors for extra credit as they've avoided the use of the fixed-point Mu functor.
Solution 2 - Haskell
Note, the signature of these has changed, because it was insufficiently general, and I included it (as a joke) in my recursion-schemes package.
zygoHistoPrepro
:: (Unfoldable t, Foldable t)
=> (Base t b -> b)
-> (forall c. Base t c -> Base t c)
-> (Base t (EnvT b (Stream (Base t)) a) -> a)
-> t
-> a
The implementation was simplified as well.
zygoHistoPrepro f = gprepro (distZygoT f distHisto)
And from the new implementation it should be obvious how to implement a generalized zygohistomorphic prepromorphism, by relaxing the constraint that you have a (Base t)-Branching
stream, through the use of distGHisto
instead.