Haskell Monoid faltbar Rosenstock

Question

Ich brauche eine faltbare Beispiel für eine Rose Baumdatenstruktur zu machen:

data Rose a = a :> [Rose a] 
    deriving (Eq, Show) 

Mit dem folgenden Monoid und Klasse/Instanzen-Rose bezogen werden:

instance Functor Rose where 
    fmap f (a :> bs) = (f a) :> (map (fmap f) bs) 

class Monoid a where 
    mempty ::   a 
    (<>) :: a -> a -> a 

instance Monoid [a] where 
    mempty = [] 
    (<>) = (++) 

Was ich versucht:

instance Foldable Rose where 
    fold (a:>b) = a <> (foldMap fold b) 

dies ist jedoch nicht richtig, für die Systemprüfung arbeitete ich den Fehler:

*** Failed! Exception: 'Prelude.undefined': 
[] :> [] 

Aber ich bin mir nicht sicher, warum es nicht funktioniert, könnte mir jemand helfen?

Vielen Dank im Voraus!

Mit freundlichen Grüßen, Skyfe.

Answer 1

Es scheint, als ob ich die Antwort auf meine eigene Frage gefunden habe.

Lösung:

instance Foldable Rose where 
    fold (a:>b) = a <> (foldr (<>) mempty (map fold b)) 

mußte erst mit dem Kopfelement jedes der Elemente in der Liste angehängt (und das gleiche für jede der gebundenen Elemente, die die Bäume stiegen), so klappt die Liste zusammen mit einem nicht-einstellenden Element mempty.

Answer 2

Ihre Implementierung von fold war korrekt, es gibt keinen Grund, es zu ändern.

Das Problem ist, dass fold nicht ausreicht, um Foldable zu definieren. Von the documentation:

class Foldable t where Source

Data structures that can be folded.

Minimal complete definition: foldMap or foldr .

So müssen Sie definieren entweder foldMap oder foldr (oder beides). Definieren foldMap ist einfacher und natürlicher (und in vielen Fällen auch effektiver). Sie sollten also so etwas wie schreiben:

import Data.Foldable 
import Data.Monoid 

data Rose a = a :> [Rose a] 
    deriving (Eq, Show) 

instance Foldable Rose where 
    foldMap f (x :> xs) = f x <> foldMap (foldMap f) xs 

Answer 3

Dies ist nur tangential verwandte, aber wenn man bedenkt, dass Rose Bäume sind die gleichen wie Cofree [] von Control.Comonad.Cofree, dann können Sie eine Foldable Instanz „kostenlos“ aus dem faltbaren Instanz erhalten von [] wie so:

import Control.Comonad.Cofree 
import Data.Foldable as F 

type RoseTree = Cofree [] 

laden Sie es in GHCi up:

λ> let tree = 1 :< [1 :< [], 2 :< [], 3 :< []] :: RoseTree Int 
λ> :t F.foldr (+) 0 tree 
F.foldr (+) 0 tree :: Int 
λ> F.foldr (+) 0 tree 
7 

Sie können auch ju St leiten Foldable, oder schreiben Sie Ihre eigene Implementierung (wie Sie getan haben).

Answer 4

Obwohl OP sagt er/sie die Antwort gefunden hat, fehlt die Lösung die Basisfall:

instance Foldable Rose where 
    fold (a:>[]) = a <> mempty 
    fold (a:>b) = a <> (foldr (<>) mempty (map fold b)) 

Andernfalls wird ein expection über nicht erschöpfende Muster in Funktion Falte wird geworfen werden.