Real-world applications of zygohistomorphic prepromorphisms

Question

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.

Solution 1

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

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.

Comments

[Yitz]

If you had included IO in your stack, we could have used SimonPJ's famous launchMissles function. But I guess the whole point of all that super-pure abstract nonsense is to avoid the possibility of such things.

[barsoap]

Well, a can be anything, so feel free to construct an IO value that strategically launches missiles based on an assessment of your input data.

[Drew]

I clicked on this question because I had no idea what the hell you're talking about. +1 good sir, +1

[Edward Z. Yang]

Someone looking to use all of the components would do well to manually write out what a zygohistomorphic prepromorphism recursion expands to, and then look for problems that need all of these patterns; imperative loops tend to do arbitrarily complicated tracking, so they might be a good place to look.

[n00b]

and more important - Will it blend ?! (very sorry, couldnt resist)

[Cosmin]

Should I feel stupid for not understanding what all this is about? :D

[barsoap]

From skimming, I think I see how they use histo when tracking the DRSP (in the same sense that a simple foldr can look at the list it already constructed), but the prepro isn't immediately apparent to me. Could you elaborate? (and, if possible, give short+sweet code we can tack onto the wiki page?)

[stephen tetley]

The code is available from a link below the errata on the landing page. The actual definition of the zygomorphism is in the file Main.hs - its different to the definition in the paper. It is "just" a zygomorphism not a "zygohistomorphic prepromorphisms" - a zygomorphism is the closest thing I've seen with a real world use. Though there are slides by Jevgeni Kabanov using histomorphisms for dynamic programming: cs.ioc.ee/~tarmo/tday-viinistu/kabanov-slides.pdf

[Ben Longo]

Ah yes quite obvious.