Generalizzazione schemi di ricorsione di `code '

Question

Ho una struttura in stile schema di ricorsione e vorrei ottenere un elenco di tutte le sottostrutture inclusa la struttura completa, ovvero l'equivalente di ciò che fa la funzione tails su un List . Penso che sarebbe possibile implementarlo chiamando lo para, mappando di nuovo alla struttura originale ad ogni passaggio, e poi attaccando separatamente la struttura originale sul davanti, ma ciò sembra molto ingombrante: (non verificato, scuse se Haskell non è corretto; scritta in termini di Mu come non ho davvero capito l'ancora Base costrutto)

gtails :: Functor f => Mu f -> [Mu f] 
gtails = para (\a -> (fmap fst a) : (foldMap snd a)) 

(vale a dire nel caso f=Prim questo è tails, per altri f è una generalizzazione)

c'è un modo più bello ? Mi rendo conto che questo non è poi così male, ma il fmap fst a per recuperare la struttura "originale" in quel passaggio è piuttosto ingombrante e lo foldMap snd a è qualcosa che trovo ripetuto molto quando uso para (allo stesso modo che si sente di nuovo come dovrebbe essere inutile).

Answer 1

Non vedo alcun problema con para. Basta Contro indietro la testa e la coda ad ogni passo Cons:

import Data.Functor.Foldable 

tails :: [a] -> [[a]] 
tails = para (\case Nil -> [[]]; Cons a (as, res) -> (a : as) : res) 

Per chiarezza, specializzato per le liste e senza recursion-schemes:

para :: (a -> [a] -> b -> b) -> b -> [a] -> b 
para f z []  = z 
para f z (a:as) = f a as (para f z as) 

tails :: [a] -> [[a]] 
tails = para (\a as res -> (a : as) : res) [[]] 

Tuttavia, se si desidera essere più generale, la meno bello para formulazione viene portata di mano:

import qualified Data.Functor.Foldable as Rec (Foldable) 

tails :: (Rec.Foldable t, Base t ~ Prim [a]) => t -> [t] 
tails as = as : para (\case Nil -> []; Cons a (as, res) -> as : res) as 

Questo funziona per gli elenchi come al solito, ma si può anche dare type instance Base t = Prim [a] per altri t -s, insieme all'istanza Foldable, e usarli pure.

In alternativa, possiamo mantenere il primo tails definizione a costo di introdurre un vincolo :

tails' :: (Unfoldable t, Rec.Foldable t, Base t ~ Prim [a]) => t -> [t] 
tails' = para (\case Nil -> [embed Nil]; Cons a (as, res) -> embed (Cons a as) : res) 

Questo non è troppo male, dal momento che per ogni project ci dovrebbe essere un inverso embed per punti fissi di funtori in ogni caso, quindi le istanze Foldable e vengono naturalmente in coppia.

Answer 2

para è davvero la funzione giusta da utilizzare qui. Ho messo tutto in un self-contained gist con esempi se vuoi giocare con esso.

Iniziamo con la definizione del punto di fissazione Mu e il solito fold e para.

module Tails where 

import Data.Function 

newtype Mu f = In { out :: f (Mu f) } 

fold :: Functor f => (f a -> a) -> Mu f -> a 
fold alg = alg . fmap (fold alg) . out 

para :: Functor f => (f (a, Mu f) -> a) -> Mu f -> a 
para alg = alg . fmap (\m -> (para alg m, m)). out 

Possiamo quindi implementare tails utilizzando para e un ulteriore Foldable vincolo che permetta di usare foldMap per raccogliere il risultato intermedio nella lista monoide:

tails :: (Functor f, Foldable f) => Mu f -> [Mu f] 
tails m = m : para (foldMap $ uncurry $ flip (:)) m