Aplicaciones del mundo real de prepromorfismos zygohistomorfos

156

Si, estos :

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

Sí, sé que son una broma ( HHOS ). Estoy buscando un ejemplo del mundo real para el valor de pirateo simple y, por último, pero no menos importante, agregarlo a la wiki diciendo "Esta es la forma idiomática de expresar XYZ". Me voy a poner una recompensa en este caso de que no llegar a una solución. Si estás completamente perdido en lo que se trata, Edward publicó una breve explicación en reddit.

Las respuestas elegibles deben:

  1. hacer algo al menos remota y teóricamente computacionalmente útil. Es decir, las respuestas que se reducen a idestán fuera.

  2. use todas las características del esquema, sin pasar de id, o const, o equivalente.

  3. no se puede expresar de la misma manera con un simple pliegue de vainilla o algo así, así que no lo implemente simplemente de productmanera serpenteante.

Se otorgarán puntos de bonificación a:

  • Problema o algoritmo bien conocido

  • resuelto, respectivamente expresado, de una manera inusual que gana

  • claridad y / o rendimiento

  • y / o piratear el valor

  • y / o lulz, más o menos en ese orden, así como

  • respuestas de alto rango (yay democracia)

Tenga en cuenta también la respuesta de Edward a continuación. La implementación de ZHPM que use es su elección.

haskell functional-programming category-theory barra de jabón
fuente
55
Si hubiera incluido IOen su pila, podríamos haber utilizado la famosa launchMisslesfunción de SimonPJ . Pero supongo que el punto de todas esas tonterías abstractas súper puras es evitar la posibilidad de tales cosas.
Yitz
66
Bueno, apuede ser cualquier cosa, así que siéntase libre de construir un valor IO que lance estratégicamente misiles en función de una evaluación de sus datos de entrada.
barsoap
49
Hice clic en esta pregunta porque no tenía idea de qué demonios estás hablando. +1 buen señor, +1
Dibujó
77
Alguien que quiera usar todos los componentes haría bien en escribir manualmente a qué se expande una recursividad prepromorfismo zygohistomorfo, y luego buscar problemas que necesiten todos estos patrones; los bucles imperativos tienden a realizar un seguimiento arbitrariamente complicado, por lo que podrían ser un buen lugar para buscar.
Edward Z. Yang
3
y más importante: ¿se mezclará? (lo siento, no pude resistir)
n00b

Respuestas:

52

Sharon Curtis y Shin-Cheng Mu tienen una Perla Funcional que usa cigomorfismos para encontrar segmentos de máxima densidad (una generalización de sumas de segmentos máximos). Aparentemente, los cigomorfismos son una buena opción para los problemas de ventanas deslizantes una vez que esté acostumbrado a ellos.

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

Nominaría a los autores para obtener crédito adicional ya que han evitado el uso del functor Mu de punto fijo.

Stephen tetley
fuente
Desde el descremado, creo que veo cómo usan histo al rastrear el DRSP (en el mismo sentido que un simple foldrpuede ver la lista que ya construyó), pero el prepro no es inmediatamente aparente para mí. ¿Podrías dar más detalles? (y, si es posible, dar un código corto + dulce que podamos agregar a la página wiki?)
barsoap
3
El código está disponible en un enlace debajo de las erratas en la página de destino. La definición real del cigomorfismo está en el archivo Main.hs, es diferente a la definición en el documento. Es "simplemente" un cigomorfismo, no un "prepromorfismo cigomhistomórfico": un cigomorfismo es lo más parecido que he visto con un uso en el mundo real. Aunque hay diapositivas de Jevgeni Kabanov usando histomorfismos para programación dinámica: cs.ioc.ee/~tarmo/tday-viinistu/kabanov-slides.pdf
stephen tetley
39

Tenga en cuenta que la firma de estos ha cambiado, porque era insuficientemente general, y lo incluí (como una broma) en mi paquete de esquemas de recursión .

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

La implementación también se simplificó.

zygoHistoPrepro f = gprepro (distZygoT f distHisto)

Y a partir de la nueva implementación, debería ser obvio cómo implementar un prepromorfismo zygohistomorfo generalizado , relajando la restricción de que tiene una (Base t)-Branchingsecuencia, mediante el uso de distGHisto.

Edward KMETT
fuente
2
Ah si bastante obvio.
Ben Longo