Реальные применения зигогистоморфных препроморфизмов в реальном мире - PullRequest
Новая
       21

Реальные применения зигогистоморфных препроморфизмов в реальном мире

154 голосов
/ 20 февраля 2011

Да, эти : 

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

Да, я знаю, что это ( ХХОС ) шутка.Я ищу реальный пример простого значения хака и, наконец, что не менее важно, чтобы добавить его в вики, говоря: «Это идиоматический способ выразить XYZ».Я получу вознаграждение за это, если вам не удастся найти решение.Если вы совершенно не понимаете, о чем они, Эдвард опубликовал краткое объяснение на reddit.

Правомочные ответы должны:

  1. сделатьчто-то хотя бы отдаленно и теоретически полезное в вычислительном отношении.То есть ответы, которые уменьшаются до id, отсутствуют.

  2. используют все функции схемы, без ввода идентификатора, или константы, или эквивалента.

  3. не в равной степени может быть выражен простой, ванильной складкой или чем-то подобным, так что не просто реализуйте product извилистым способом.

Бонусные баллы будутдано:

  • Хорошо известная проблема или алгоритм

  • решено, соответственно выражено, необычным образом, получая

  • ясность и / или производительность

  • и / или значение хака

  • и / или lulz, примерно в таком порядке, а также

  • высокопоставленные ответы (ура демократия)

Обратите также внимание ответ Эдварда ниже.Какую реализацию ZHPM вы используете - ваш выбор.

Ответы [ 2 ]

51 голосов
/ 20 февраля 2011

Шарон Кертис и Шин-Ченг Му имеют Функциональную Жемчужину, использующую зигоморфизмы для нахождения максимально плотных сегментов (обобщение максимальных сумм сегментов). Зигоморфизмы, по-видимому, хорошо подходят для задач с раздвижными окнами, когда вы к ним привыкли.

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

Я бы назначил авторов за дополнительную оценку, поскольку они избегали использования функтора Му с фиксированной точкой.

38 голосов
/ 20 февраля 2011

Обратите внимание, что их подпись изменилась, потому что она была недостаточно общей, и я включил ее (в шутку) в мой пакет recursion-схемы . 

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

реализация также была упрощена. 

zygoHistoPrepro f = gprepro (distZygoT f distHisto)

И из новой реализации должно быть очевидно, как реализовать обобщенный скулово-гистоморфный препроморфизм, ослабив ограничение на наличие потока (Base t)-Branchingвместо использования distGHisto.

...