Real-world applications of zygohistomorphic prepromorphisms

15.7k views Asked by At

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:

  1. do something at least remotely and theoretically computationally useful. That is, answers that reduce to id are out.

  2. use all the features of the scheme, no passing in of id, or const, or equivalent.

  3. 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.

2

There are 2 answers

2
stephen tetley On

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.

1
Edward Kmett On

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.