Real-world applications of zygohistomorphic prepromorphisms

160
votes

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
haskellfunctional-programmingcategory-theory
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. – Yitz
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. – barsoap
I clicked on this question because I had no idea what the hell you're talking about. +1 good sir, +1 – Drew
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. – Edward Z. Yang
and more important - Will it blend ?! (very sorry, couldnt resist) – n00b

2 Answers

55
votes

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.

39
votes

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.