Rzeczywiste zastosowania prepromorfizmów zygohistomorficznych

156

Tak, te :

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

Tak, wiem, że to żart ( HHOS ). Szukam rzeczywistego przykładu dla prostej wartości hackowania i na koniec, ale nie mniej ważny, aby dodać go do wiki, mówiąc „To jest idiomatyczny sposób wyrażenia XYZ”. I będzie umieścić bounty na to nie powinieneś wymyślić rozwiązanie. Jeśli całkowicie zgubiłeś się w tym, o co im chodzi, Edward opublikował krótkie wyjaśnienie na reddicie.

Kwalifikujące się odpowiedzi muszą:

  1. zrobić coś przynajmniej zdalnie i teoretycznie użytecznego obliczeniowo. Oznacza to, że odpowiedzi, które redukują się do, idsą wykluczone.

  2. używać wszystkich funkcji schematu, bez przekazywania id, const lub równoważnych.

  3. nie da się równie dobrze wyrazić prostym, waniliowym fałdem lub czymś podobnym, więc nie wdrażaj po prostu productmeandrując.

Punkty bonusowe zostaną przyznane:

  • Dobrze znany problem lub algorytm

  • rozwiązane, odpowiednio wyrażone, w niecodzienny sposób, który zyskuje

  • przejrzystość i / lub wydajność

  • i / lub wartość hackowania

  • i / lub lulz, mniej więcej w tej kolejności, jak również

  • wysokiej rangi odpowiedzi (yay demokracja)

Zwróć także uwagę na odpowiedź Edwarda poniżej. To, z jakiej implementacji ZHPM korzystasz, zależy od Ciebie.

haskell functional-programming category-theory kostka mydła
źródło
5
Gdybyś zawarł IOw swoim stosie, moglibyśmy użyć słynnej launchMisslesfunkcji SimonPJ . Ale wydaje mi się, że celem całego tego super-czystego abstrakcyjnego nonsensu jest uniknięcie możliwości takich rzeczy.
Yitz,
6
Cóż, amoże to być wszystko, więc nie krępuj się skonstruować wartości IO, która strategicznie wyrzuca pociski na podstawie oceny danych wejściowych.
Barsoap
49
Kliknąłem na to pytanie, ponieważ nie miałem pojęcia, o czym do diabła mówisz. +1 dobry panie, +1
Drew
7
Ktoś, kto chce użyć wszystkich komponentów, dobrze by zrobił, gdyby ręcznie napisał, do czego rozszerza się rekurencja zygohistomorficzna prepromorfizmu, a następnie poszukałby problemów, które wymagają wszystkich tych wzorców; imperatywne pętle zwykle wykonują dowolnie skomplikowane śledzenie, więc mogą być dobrym miejscem do wyszukiwania.
Edward Z. Yang
3
i co ważniejsze - czy się połączy ?! (bardzo przepraszam, nie mogłem się oprzeć)
n00b

Odpowiedzi:

52

Sharon Curtis i Shin-Cheng Mu mają Perłę Funkcjonalną wykorzystującą zygomorfizmy do znajdowania segmentów o maksymalnej gęstości (uogólnienie maksymalnych sum segmentów). Zygomorfizmy pozornie dobrze sprawdzają się w przypadku problemów z przesuwanymi oknami, gdy już się do nich przyzwyczaisz.

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

Nominowałbym autorów do dodatkowego uznania, ponieważ uniknęli stosowania funktora Mu stałopunktowego.

Stephen Tetley
źródło
Od skimmingu myślę, że widzę, jak używają histo podczas śledzenia DRSP (w tym samym sensie, w jakim zwykły foldrmoże spojrzeć na listę, którą już utworzył), ale prepro nie jest dla mnie od razu widoczne. Czy mógłbyś to rozwinąć? (i jeśli to możliwe, podaj krótki + słodki kod, który możemy umieścić na stronie wiki?)
barsoap
3
Kod jest dostępny pod linkiem pod erratą na stronie docelowej. Właściwa definicja zygomorfizmu znajduje się w pliku Main.hs - różni się od definicji w artykule. To jest „tylko” zygomorfizm, a nie „zygohistomorficzne prepromorfizmy” - zygomorfizm jest najbliższą rzeczą, jaką widziałem w prawdziwym świecie. Chociaż są slajdy Jevgeni Kabanov wykorzystujące histomorfizmy do programowania dynamicznego: cs.ioc.ee/~tarmo/tday-viinistu/kabanov-slides.pdf
stephen tetley
39

Zauważ, że ich sygnatura uległa zmianie, ponieważ była niewystarczająco ogólna i włączyłem ją (jako żart) do pakietu schematów rekurencji .

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

Wdrożenie również zostało uproszczone.

zygoHistoPrepro f = gprepro (distZygoT f distHisto)

A od nowej implementacji powinno być oczywiste, jak zaimplementować uogólniony prepromorfizm zygohistomorficzny, poprzez złagodzenie ograniczenia, jakim jest (Base t)-Branchingstrumień, poprzez użycie distGHistozamiast.

Edward KMETT
źródło
2
Ach tak, całkiem oczywiste.
Ben Longo