Reale Anwendungen von zygohistomorphen Präpromorphismen

156

Ja, diese :

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

Ja, ich weiß, dass sie ein ( HHOS ) Witz sind. Ich suche ein reales Beispiel für einen einfachen Hack-Wert und nicht zuletzt, um es dem Wiki hinzuzufügen und zu sagen: "Dies ist die idiomatische Art, XYZ auszudrücken." Ich werde ein Kopfgeld dafür geben, falls Sie keine Lösung finden. Wenn Sie völlig verloren sind, worum es geht, hat Edward eine kurze Erklärung zu reddit veröffentlicht.

Geeignete Antworten müssen:

  1. Machen Sie etwas zumindest aus der Ferne und theoretisch rechnerisch nützlich. Das heißt, Antworten, die sich auf reduzieren, idsind aus.

  2. Verwenden Sie alle Funktionen des Schemas, ohne dass id, const oder ein gleichwertiges Element übergeben werden.

  3. nicht gleich gut durch eine einfache Vanillefalte oder dergleichen auszudrücken, also nicht nur productmäanderförmig umsetzen .

Bonuspunkte werden vergeben an:

  • Bekanntes Problem oder Algorithmus

  • auf ungewöhnliche Weise gelöst bzw. ausgedrückt, die gewinnt

  • Klarheit und / oder Leistung

  • und / oder Hackwert

  • und / oder lulz, in ungefähr dieser Reihenfolge, sowie

  • hochrangige Antworten (yay Demokratie)

Bitte beachte auch Edwards Antwort unten. Welche ZHPM-Implementierung Sie verwenden, ist Ihre Wahl.

Blockseife
quelle
5
Wenn Sie IOin Ihren Stapel aufgenommen hätten, hätten wir die berühmte launchMisslesFunktion von SimonPJ verwenden können. Aber ich denke, der Sinn all dieses superreinen abstrakten Unsinns ist es, die Möglichkeit solcher Dinge zu vermeiden.
Yitz
6
Nun, akann alles sein, also zögern Sie nicht, einen E / A-Wert zu konstruieren, der Raketen strategisch abfeuert, basierend auf einer Bewertung Ihrer Eingabedaten.
Barsoap
49
Ich habe auf diese Frage geklickt, weil ich keine Ahnung hatte, wovon zum Teufel du redest. +1 guter Herr, +1
Drew
7
Jemand, der alle Komponenten verwenden möchte, sollte gut manuell aufschreiben, auf was sich eine zygohistomorphe Präpromorphismus-Rekursion ausdehnt, und dann nach Problemen suchen, die alle diese Muster erfordern. Imperativschleifen neigen dazu, willkürlich kompliziertes Tracking durchzuführen, daher sind sie möglicherweise ein guter Ort, um nachzuschauen.
Edward Z. Yang
3
und wichtiger - Wird es mischen ?! (sehr leid, konnte nicht widerstehen)
n00b

Antworten:

52

Sharon Curtis und Shin-Cheng Mu haben eine funktionale Perle, die Zygomorphismen verwendet, um maximal dichte Segmente zu finden (eine Verallgemeinerung der maximalen Segmentsummen). Zygomorphismen eignen sich anscheinend gut für Schiebefensterprobleme, wenn Sie sich erst einmal daran gewöhnt haben.

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

Ich würde die Autoren für zusätzliche Anerkennung nominieren, da sie die Verwendung des Festkomma-Mu-Funktors vermieden haben.

Stephen Tetley
quelle
Beim Überfliegen sehe ich, wie sie Histo beim Verfolgen des DRSP verwenden (in dem Sinne, dass ein Einfacher foldrdie bereits erstellte Liste einsehen kann), aber das Prepro ist mir nicht sofort klar. Könnten Sie näher darauf eingehen? (Und wenn möglich, geben Sie einen kurzen + süßen Code, den wir auf der Wiki-Seite
anheften können
3
Der Code ist über einen Link unterhalb der Errata auf der Zielseite verfügbar. Die eigentliche Definition des Zygomorphismus befindet sich in der Datei Main.hs - sie unterscheidet sich von der Definition im Papier. Es ist "nur" ein Zygomorphismus, kein "zygohistomorpher Präpromorphismus" - ein Zygomorphismus ist das Nächste, was ich bei einer Verwendung in der realen Welt gesehen habe. Obwohl es Folien von Jevgeni Kabanov
gibt, die Histomorphismen
39

Beachten Sie, dass sich die Signatur dieser geändert hat, da sie nicht allgemein genug war und ich sie (als Scherz) in mein Rekursionsschema- Paket aufgenommen habe.

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

Die Implementierung wurde ebenfalls vereinfacht.

zygoHistoPrepro f = gprepro (distZygoT f distHisto)

Und aus der neuen Implementierung sollte es offensichtlich sein, wie ein verallgemeinerter zygohistomorpher Präpromorphismus implementiert werden kann, indem die Einschränkung, dass Sie einen (Base t)-BranchingStream haben, durch die Verwendung von distGHistostattdessen gelockert wird .

Edward KMETT
quelle
2
Ah ja ganz offensichtlich.
Ben Longo