Rekursionschemata Generalisierung von `tails`

Question

Ich habe eine Rekursionschemas Stil Struktur und ich möchte eine Liste aller Unterstrukturen einschließlich der vollständigen Struktur erhalten - dh das Äquivalent von dem, was die tails Funktion auf einem List tut . Ich denke, es wäre möglich, dies zu implementieren, indem man para aufruft, in jedem Schritt auf die ursprüngliche Struktur zurückverwandelt und dann die ursprüngliche Struktur auf der Vorderseite separat klebt, aber das scheint sehr beschwerlich: (ungetestet, Entschuldigung, wenn der Haskell falsch ist; geschrieben in Bezug auf Mu, da ich nicht wirklich das Base Konstrukt noch) nicht verstanden haben

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

(dh im Falle f=Prim dies tails, ist es für andere f ist eine Verallgemeinerung)

gibt es eine schönere Art und Weise ? Ich weiß, das ist nicht so schlimm, aber die fmap fst a, um die "ursprüngliche" Struktur bei diesem Schritt wiederherzustellen fühlt sich ziemlich umständlich, und die foldMap snd a ist etwas, das ich mich wiederhole viel bei der Verwendung para (ebenfalls fold a bei der Verwendung cata, die wieder wie fühlt es sollte unnötig sein).

Answer 1

Ich sehe kein Problem mit para. Nur cons den Kopf und den Schwanz an jedem Cons Schritt zurück:

import Data.Functor.Foldable 

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

Aus Gründen der Klarheit spezialisiert auf Listen und ohne 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) [[]] 

Wenn Sie jedoch allgemeinere sein mögen, die weniger schön para Formulierung kommt praktisch:

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 

Diese für Listen wie gewohnt funktioniert, aber Sie können auch type instance Base t = Prim [a] geben für andere t -s, zusammen mit der Foldable Instanz, und verwenden Sie sie auch.

Alternativ können wir die erste tails Definition auf Kosten halten eine Einschränkung der Einführung:

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) 

Das ist nicht so schlimm, da für jeden project sollte es eine inverse embed für Fixpunkte functors sein Wie auch immer, so kommen die und Instanzen natürlich paarweise.

Answer 2

para ist in der Tat die richtige Funktion hier zu verwenden. Ich habe alles in eine self-contained gist mit Beispielen ergänzt, wenn Sie damit spielen wollen.

Wir beginnen mit der Definition des Fixpunkts Mu und der üblichen fold und 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 

Wir können dann implementieren tailspara und eine zusätzliche Foldable Einschränkung mit uns ermöglicht foldMap zu verwenden, um das Zwischenergebnis in der Liste Monoid zu sammeln:

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