Istomorfismi, Zigomorfismi e Futorforfismi specializzati nelle liste

Question

Nel mio tentativo di comprendere schemi di ricorsione generici (ad esempio, che utilizzano Fix), ho trovato utile scrivere versioni di sola lista dei vari schemi. Rende molto più facile comprendere gli schemi reali (senza il sovraccarico aggiuntivo del materiale Fix).

Tuttavia, non ho ancora capito come definire le versioni solo elenco di zygo e futu.

Ecco le mie definizioni specializzati finora:

cataL :: (a ->  b -> b) -> b -> [a] -> b 
cataL f b (a : as) = f a (cataL f b as) 
cataL _ b []  = b 

paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b 
paraL f b (a : as) = f a as (paraL f b as) 
paraL _ b []  = b 

-- TODO: histo 

-- DONE: zygo (see below) 

anaL :: (b ->  (a, b))    -> b -> [a] 
anaL f b = let (a, b') = f b in a : anaL f b' 

anaL' :: (b -> Maybe (a, b))    -> b -> [a] 
anaL' f b = case f b of 
    Just (a, b') -> a : anaL' f b' 
    Nothing  -> [] 

apoL :: ([b] -> Maybe (a, Either [b] [a])) -> [b] -> [a] 
apoL f b = case f b of 
    Nothing -> [] 
    Just (x, Left c) -> x : apoL f c 
    Just (x, Right e) -> x : e 

-- DONE: futu (see below) 

hyloL :: (a -> c -> c) -> c -> (b -> Maybe (a, b)) -> b -> c 
hyloL f z g = cataL f z . anaL' g 

hyloL' :: (a -> c -> c) -> c -> (c -> Maybe (a, c))  -> c 
hyloL' f z g = case g z of 
    Nothing  -> z 
    Just (x,z') -> f x (hyloL' f z' g) 

Come si fa a definire histo, zygo e futu per gli elenchi?

Answer 1

Zygomorphism è l'alta falutin' mathsy nome che diamo a pieghe costruito da due semi-reciprocamente funzioni ricorsive. Darò un esempio.

Immaginate una funzione pm :: [Int] -> Int (per più-meno), che alterna + e - alternativamente attraverso un elenco di numeri, in modo tale che pm [v,w,x,y,z] = v - (w + (x - (y + z))). È possibile scrivere fuori utilizzando la ricorsione primitiva:

lengthEven :: [a] -> Bool 
lengthEven = even . length 

pm0 [] = 0 
pm0 (x:xs) = if lengthEven xs 
      then x - pm0 xs 
      else x + pm0 xs 

Chiaramente pm0 non è compositional - è necessario controllare la lunghezza della lista completa in ogni posizione per determinare se si sta aggiungendo o sottraendo. Paramorphism modelli di ricorsione primitiva di questo tipo, quando la funzione di piegatura deve attraversare l'intera sottostruttura ad ogni iterazione della piega. Quindi possiamo almeno riscrivere il codice per conformarci a uno schema stabilito.

paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b 
paraL f z [] = z 
paraL f z (x:xs) = f x xs (paraL f z xs) 

pm1 = paraL (\x xs acc -> if lengthEven xs then x - acc else x + acc) 0 

Ma questo è inefficiente. lengthEven attraversa l'intera lista ad ogni iterazione del paramorfismo risultante in un algoritmo O (n).

---

Possiamo progredire osservando che sia lengthEven e para può essere espresso come una catamorphism con foldr ...

cataL = foldr 

lengthEven' = cataL (\_ p -> not p) True 
paraL' f z = snd . cataL (\x (xs, acc) -> (x:xs, f x xs acc)) ([], z) 

... che suggerisce che potremmo essere in grado di fondere le due operazioni in un unico passaggio sulla lista.

pm2 = snd . cataL (\x (isEven, total) -> (not isEven, if isEven 
                 then x - total 
                 else x + total)) (True, 0) 

Abbiamo avuto una piega che dipendeva dal risultato di un'altra piega, e siamo stati in grado di fonderli in un unico attraversamento della lista. Lo Zigomorfismo cattura esattamente questo schema.

zygoL :: (a -> b -> b) -> -- a folding function 
     (a -> b -> c -> c) -> -- a folding function which depends on the result of the other fold 
     b -> c -> -- zeroes for the two folds 
     [a] -> c 
zygoL f g z e = snd . cataL (\x (p, q) -> (f x p, g x p q)) (z, e) 

Su ogni iterazione della piega, f vede la sua risposta dalla ultima iterazione come in un catamorphism, ma g arriva a vedere le risposte entrambe le funzioni. g si impiglia con f.

Scriviamo pm come zigomorfismo utilizzando la prima funzione di piegatura per contare se l'elenco è pari o dispari in lunghezza e il secondo per calcolare il totale.

pm3 = zygoL (\_ p -> not p) (\x isEven total -> if isEven 
               then x - total 
               else x + total) True 0 

Questo è lo stile classico di programmazione funzionale. Abbiamo una funzione di ordine superiore che fa il grosso del consumare la lista; tutto ciò che dovevamo fare era collegare la logica per aggregare i risultati. La costruzione termina evidentemente (è necessario solo provare la terminazione per foldr) ed è più efficiente rispetto alla versione originale scritta a mano per l'avvio.

parte: @AlexR sottolinea nei commenti che zygomorphism ha una sorella maggiore chiamato mutumorphism, che cattura la ricorsione reciproca in tutta la sua gloria . mutu generalizza zygo in quello entrambe le funzioni di piegatura sono consentite per ispezionare il risultato dell'altro dall'ultima iterazione .

mutuL :: (a -> b -> c -> b) -> 
     (a -> b -> c -> c) -> 
     b -> c -> 
     [a] -> c 
mutuL f g z e = snd . cataL (\x (p, q) -> (f x p q, g x p q)) (z, e) 

a recuperare zygo da mutu semplicemente ignorando l'argomento in più. zygoL f = mutuL (\x p q -> f x p)

---

Naturalmente, tutti questi modelli pieghevoli generalizzare sulla base di liste al punto di rilevamento di un funtore arbitraria:

newtype Fix f = Fix { unFix :: f (Fix f) } 

cata :: Functor f => (f a -> a) -> Fix f -> a 
cata f = f . fmap (cata f) . unFix 

para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a 
para f = snd . cata (\x -> (Fix $ fmap fst x, f x)) 

zygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Fix f -> a 
zygo f g = snd . cata (\x -> (f $ fmap fst x, g x)) 

mutu :: Functor f => (f (b, a) -> b) -> (f (b, a) -> a) -> Fix f -> a 
mutu f g = snd . cata (\x -> (f x, g x)) 

Confrontare la definizione di zygo con quella di zygoL. Si noti inoltre che zygo Fix = para e che le ultime tre pieghe possono essere implementate in termini di cata. Nella foldologia tutto è collegato a tutto il resto.

È possibile recuperare la versione di elenco dalla versione generalizzata.

data ListF a r = Nil_ | Cons_ a r deriving Functor 
type List a = Fix (ListF a) 

zygoL' :: (a -> b -> b) -> (a -> b -> c -> c) -> b -> c -> List a -> c 
zygoL' f g z e = zygo k l 
    where k Nil_ = z 
      k (Cons_ x y) = f x y 
      l Nil_ = e 
      l (Cons_ x (y, z)) = g x y z 

pm4 = zygoL' (\_ p -> not p) (\x isEven total -> if isEven 
               then x - total 
               else x + total) True 0 

Answer 2

dato che nessun altro ha risposto per futu ancora, cercherò di inciampare la mia strada attraverso. Userò ListF a b = Base [a] = ConsF a b | NilF

Riprendendo il tipo in recursion-schemes: futu :: Unfoldable t => (a -> Base t (Free (Base t) a)) -> a -> t.

Ho intenzione di ignorare il vincolo e sostituire [b] per t.

(a -> Base [b] (Free (Base [b]) a)) -> a -> [b] 
(a -> ListF b (Free (ListF b) a)) -> a -> [b] 

Free (ListF b) a) è un elenco, possibilmente con un foro -typed a alla fine. Ciò significa che è isomorfo a ([b], Maybe a).Così ora abbiamo:

(a -> ListF b ([b], Maybe a)) -> a -> [b] 

Eliminando l'ultimo ListF, notando che ListF a b è isomorfo a Maybe (a, b):

(a -> Maybe (b, ([b], Maybe a))) -> a -> [b] 

Ora, sono abbastanza sicuro che giocare cavi di tipo-tetris per l'unica implementazione sensibile :

futuL f x = case f x of 
    Nothing -> [] 
    Just (y, (ys, mz)) -> y : (ys ++ fz) 
    where fz = case mz of 
     Nothing -> [] 
     Just z -> futuL f z 

Riassumendo la funzione risultante, futuL assume un valore di inizializzazione e una funzione che può produrre almeno un risultato e possibilmente un nuovo valore seme se ha prodotto un risultato.

In un primo momento ho pensato che questo era equivalente a

notFutuL :: (a -> ([b], Maybe a)) -> a -> [b] 
notFutuL f x = case f x of 
    (ys, mx) -> ys ++ case mx of 
    Nothing -> [] 
    Just x' -> notFutuL f x' 

E in pratica, forse è, più o meno, ma l'unica differenza significativa è che la produttività reale futu garanzie (cioè se f ritorna sempre, non sarai mai bloccato aspettando per sempre il prossimo elemento dell'elenco).

Answer 3

Histomorphism modelli programmazione dinamica, la tecnica di tabulazione risultati delle subcomputations precedenti. (Talvolta viene chiamato course-of-value induction.) In un istomorfismo, la funzione di piegatura ha accesso a una tabella dei risultati di iterazioni precedenti della piega. Confronta questo con il catamorfismo, in cui la funzione di piegatura può solo vedere il risultato dell'ultima iterazione. L'istomorfismo ha il vantaggio del senno di poi: puoi vedere tutta la storia.

Ecco l'idea. Mentre consumiamo la lista di input, l'algebra di ripiegamento emetterà una sequenza di b s. histo annoterà ogni b come appare, collegandolo alla tabella dei risultati. Il numero di elementi nella cronologia è uguale al numero di livelli di elenco che hai elaborato: nel momento in cui hai distrutto l'intero elenco, la cronologia della tua operazione avrà una lunghezza uguale a quella della lista.

Questo è ciò che la storia di iterazione un elenco (ORY) assomiglia:

data History a b = Ancient b | Age a b (History a b) 

History è una lista di coppie di cose e dei risultati, con un risultato extra alla fine corrispondente al [] -thing . Accoppiamo ogni livello della lista di input con il risultato corrispondente.

Dopo aver piegato l'intero elenco da destra a sinistra, il risultato finale sarà in cima alla pila.

headH :: History a b -> b 
headH (Ancient x) = x 
headH (Age _ x _) = x 

histoL :: (a -> History a b -> b) -> b -> [a] -> b 
histoL f z = headH . history f z 

(Succede che History a è un comonad, ma headH (nata extract) è tutto dobbiamo definire histoL.)

---

History etichette ogni strato della lista in ingresso con il corrispondente risultato . La combinazione di creeree acquisisce lo schema di etichettatura di ogni livello di una struttura arbitraria.

data Cofree f a = Cofree { headC :: a, tailC :: f (Cofree f a) } 

(mi si avvicinò con History collegando ListF in Cofree e la semplificazione.)

confronta questo con l'libera Monade,

data Free f a = Free (f (Free f a)) 
       | Return a 

Free è un tipo coprodotto; Cofree è un tipo di prodotto. Free strati su una lasagna di f s, con valori a nella parte inferiore delle lasagne. Cofree sovrappone le lasagne con i valori a a ciascun livello. Le monadi libere sono alberi generalizzati etichettati esternamente; le comree del cofree sono alberi generati internamente con etichetta.

Con Cofree in mano, possiamo generalizzare sulla base di liste al punto di rilevamento di un funtore arbitraria,

newtype Fix f = Fix { unFix :: f (Fix f) } 

cata :: Functor f => (f b -> b) -> Fix f -> b 
cata f = f . fmap (cata f) . unFix 

histo :: Functor f => (f (Cofree f b) -> b) -> Fix f -> b 
histo f = headC . cata (\x -> Cofree (f x) x) 

e ancora una volta recuperare la versione lista.

data ListF a r = Nil_ | Cons_ a r deriving Functor 
type List a = Fix (ListF a) 
type History' a b = Cofree (ListF a) b 

histoL' :: (a -> History' a b -> b) -> b -> List a -> b 
histoL' f z = histo g 
    where g Nil_ = z 
      g (Cons_ x h) = f x h 

parte: histo è il duale del futu. Guarda i loro tipi.

histo :: Functor f => (f (Cofree f a) -> a) -> (Fix f -> a) 
futu :: Functor f => (a -> f (Free f a)) -> (a -> Fix f) 

futu è histo con le frecce capovolto e con Free sostituito da Cofree. Gli istomorfismi vedono il passato; i futumorphisms predicono il futuro. E molto simile cata f . ana g può essere fuso in un ilemorfismo, histo f . futu g può essere fuso in un chronomorphism.

Anche se si salta le parti mathsy, this paper by Hinze and Wu dispone di una buona, ad esempio-driven tutorial su histomorphisms e il loro utilizzo.