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

Да, эти:

{-#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) шутка. Я ищу реальный пример простой хакерской ценности и, наконец, но не в последнюю очередь, чтобы добавить его в вики, говоря: «Это идиоматический способ выразить XYZ». Я назначу за это вознаграждение, если вы не найдете решения. Если вы совершенно не понимаете, о чем они говорят, Эдвард опубликовал короткий объяснение на Reddit.

Допустимые ответы должны:

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

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

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

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

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

  • решено, соответственно выражено, необычным способом, который

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

  • и / или взломать ценность

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

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

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


functional-programming haskell category-theory
person barsoap    schedule 20.02.2011    source источник
comment
Если бы вы включили IO в свой стек, мы могли бы использовать знаменитую функцию SimonPJ launchMissles. Но я полагаю, что весь смысл всей этой сверхчистой абстрактной чепухи состоит в том, чтобы избежать возможности таких вещей.   -  person Yitz    schedule 20.02.2011
comment
Что ж, a может быть любым, поэтому не стесняйтесь создавать значение IO, которое стратегически запускает ракеты, на основе оценки ваших входных данных.   -  person barsoap    schedule 20.02.2011
comment
Я нажал на этот вопрос, потому что понятия не имел, о чем вы, черт возьми, говорите. +1 хороший сэр, +1   -  person Drew    schedule 23.02.2011
comment
Кто-то, желающий использовать все компоненты, преуспел бы, если бы вручную выписал, до чего расширяется рекурсия зигогистоморфного препроморфизма, а затем поищите проблемы, для которых нужны все эти шаблоны; императивные циклы, как правило, выполняют произвольно сложное отслеживание, так что они могут быть хорошим местом для поиска.   -  person Edward Z. Yang    schedule 24.02.2011
comment
и что еще важнее - он смешается ?! (очень жаль, не удержался)   -  person n00b    schedule 02.03.2011
comment
Должен ли я чувствовать себя глупо из-за того, что не понимаю, о чем все это? : D   -  person Cosmin    schedule 08.03.2011

Ответы (2)


arrow_upward
53
arrow_downward

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

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

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

person stephen tetley    schedule 20.02.2011
comment
Из беглого просмотра я думаю, что вижу, как они используют гисто при отслеживании DRSP (в том же смысле, что простой foldr может смотреть на уже созданный список), но препро мне не сразу бросается в глаза. Не могли бы вы уточнить? (и, если возможно, дайте короткий + приятный код, который мы можем прикрепить к странице вики?) - person barsoap; 21.02.2011
comment
Код доступен по ссылке под ошибкой на целевой странице. Фактическое определение зигоморфизма находится в файле Main.hs - оно отличается от определения в документе. Это просто зигоморфизм, а не зигогистоморфные препроморфизмы - зигоморфизм - это самое близкое, что я видел в реальном мире. Хотя есть слайды Евгения Кабанова, использующие гистоморфизмы для динамического программирования: cs.ioc.ee/~tarmo/tday-viinistu/kabanov-slides.pdf - person stephen tetley; 22.02.2011

arrow_upward
39
arrow_downward

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

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.

person Edward KMETT    schedule 20.02.2011
comment
Ах да, совершенно очевидно. - person Ben Longo; 22.03.2020