160

是的，这些：

{-#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))

是的，我知道他们是一个（HHOS）笑话。我正在寻找一个简单的黑客价值的真实示例，最后但并非最不重要的是，将其添加到 wiki 中说“这是表达 XYZ 的惯用方式”。如果您未能提出解决方案，我将为此提供赏金。如果你完全不知道他们在说什么，爱德华在 reddit 上发布了一个简短的解释。

合格的答案必须：

  1. 至少做一些远程和理论上计算上有用的事情。也就是说，减少到的答案id已经出来了。

  2. 使用方案的所有功能，不传入 id、const 或等效项。

  3. 不能通过简单的香草折叠等来表达，所以不要仅仅product以曲折的方式实现。

奖励积分将给予：

  • 众所周知的问题或算法

  • 以一种不同寻常的方式解决，分别表达，获得

  • 清晰度和/或性能

  • 和/或黑客价值

  • 和/或 lulz，大致按照这个顺序，以及

  • 高级答案（耶民主）

另请注意爱德华在下面的回答。您使用什么 ZHPM 实现是您的选择。

4

2 回答 2

55

Sharon Curtis 和 Shin-Cheng Mu 有一个使用 zygomorphisms 来找到最大密集段（最大段总和的概括）的功能珍珠。一旦您习惯了 Zygomorphism，它们似乎很适合解决滑动窗口问题。

http://www.iis.sinica.edu.tw/~scm/2010/functional-pearl-maximally-dense-segments/

我会提名作者以获得额外的荣誉，因为他们避免使用定点 Mu 函子。

于 2011-02-20T20:11:05.490 回答
39

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.

于 2011-02-20T17:35:27.157 回答