implementazione principianti di Catamorphism per gli alberi non binari rispetto al composite design

Question

Per il momento, il sogno continua ancora, ad ogni concetto di Haskell imparo io sono più allettati. Eppure io ho mai completamente soddisfatta a lavorare su questa preziosa risposta @ di luqui a mio precedente domanda circa catamorphism , e sto andando a tornare fino a quando non è OK. Fu in questo codice di esempio su Wikipedia, si tratta di catamorphism sul BINARIO alberi .

Tuttavia, ho cercato attuazione catamorphism per NON BINARIO alberi, ma ho affrontare alcuni problemi:

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                                 , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y] 

- che l'ultima linea pretende molto piacere ghc sulla "mappa g [y]"

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

maxInList :: [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = (+) } 

- e questo lattest sumTree è sbagliato troppo per GHC

Vedo> e +, proprio come il C ++ operatori> e +. Quindi non capisco GHC è arrabbiata con me senza che io dare ad esso attuazione Objets opertor> / + o meno.

In secondo luogo devo ammettere che sono completamente confusa sul senso di => (diverso da -> ???). E @ che sembra essere come una guida per pattern matching

Come vorresti correggere questo codice?

E un ultima domanda, Sto anche cercando facendo questo perché il composite è sembrato essere il più importante per me in C ++. E ovviamente lo vedo può essere quasi descritta in una sola riga / due in Haskell (che è davvero incredibile per me).

Ma come è possibile Haskell persone esprimere il fatto che Leaf e costruttore Composito della composizione può avere un qualche tipo della stessa interfaccia? (Lo so che non è la parola buona in quanto i dati non sono mutabili, ma spero che si può intuire, capire la mia preoccupazione / obiettivo)

Questo è l'errore totale di compilazione;

src\Main.hs:27:79:
    Couldn't match expected type `[r]'
           against inferred type `Composition a'
    In the expression: y
    In the second argument of `map', namely `[y]'
    In the expression: map g [y]

src\Main.hs:30:20:
    Could not deduce (Ord a) from the context ()
      arising from a use of `>' at src\Main.hs:30:20-24
    Possible fix:
      add (Ord a) to the context of the type signature for `maxOfPair'
    In the expression: (x > y)
    In the expression: if (x > y) then (x) else (y)
    In the definition of `maxOfPair':
        maxOfPair x y = if (x > y) then (x) else (y)

src\Main.hs:41:0:
    Occurs check: cannot construct the infinite type: a = [a] -> [a]
    When generalising the type(s) for `sumTree'

Modifica Quindi questa è la versione definitiva per catamorphism non binaria

data Composant a = Leaf a
                 | Composite [Composant a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                             , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composant a →  r
foldComposition a@(CompositionAlgebra {leaf = f}) (Leaf x) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) =  g(map(foldComposition a) ys)

maxOfPair :: Ord a ⇒ a →  a →  a
maxOfPair x y = if( x > y) 
                then (x) 
                else (y)

maxInList :: Ord a => [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

addList :: Num a ⇒ [a] → a
addList (x:xs) = x + addList xs 

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = addList } 

E secondo la risposta valida sotto:. Quello che mi è stato chiesto per Haskell equivalente di contratti di C ++ Interfacce sembra essere typeclasses vincoli

Quindi, il modello di progettazione Composite potrebbe essere raggiunto mediante l'applicazione di vincoli typeclass quando si costruisce la composizione a. Forse un nuovo data specializzata deve essere definire. Ma dovrei imparare typeclasses prima di farlo: -)

Answer 1

Ci sono alcuni errori diversi, quindi non sono sicuro che il modo migliore per trattare con esso su SO, ma che diamine.

In futuro, cercare di comprendere più degli errori che GHC fornisce.

A:

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y]

Il foldCompose funzione ha due errori che posso vedere, uno solo dei quali sarà preso dal tipo checker.

1. Non Sei pattern matching su (Composite [y]), che corrisponderà solo per gli elenchi di un elemento. È probabile che vuole (Composite ys), che si lega alla ys l'intero elenco.

2. map g [y] non passerà il tipo di controllo, perché hai già definito g come prendere un elenco di r, ma si sta dando un elenco di a.

   Al fine di convertire un a a un r è necessario applicare la vostra CompositionAlgebra ad esso: g (map (foldComposition a) ys)

Quindi vorrei scrivere questo come:

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) = g (map (foldComposition a) ys)

Per la vostra prossima errore:

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

In Haskell, una variabile di tipo (come a qui) tutto dalla sua solitaria può essere compilato con qualsiasi tipo affatto dal chiamante, a scelta del chiamante.

Ciò significa, in tua firma tipo che stai sostenendo che la funzione maxPair lavorerà per tutti tipo di ingresso. GHC si lamenta (a suo modo) che l'> operatore non funziona per tutti tipo, e per questo si rifiuta di compilare il programma.

È necessario utilizzare typeclasses per risolvere questo problema. In Haskell, typeclasses lasciare che il chiamante scegliere i tipi di utilizzo, ma con alcune limitazioni. Mi raccomando di leggere un Haskell tutorial su typeclasses .

La firma tipo corretto sarebbe:

maxOfPair :: Ord a => a →  a →  a

che si applica il vincolo Ord al tipo a.

Inoltre, si dovrebbe utilizzare la funzione standard max .

Answer 2

In secondo luogo devo ammettere che sono completamente velato sul senso di => (diverso da -> ???) e @, che sembra essere come una guida per pattern matching.

elem funzione, che verifica se un elenco contiene un certo valore. Si potrebbe definire come

elem _ [] = False
elem x (y:ys) | x == y = True
              | otherwise = elem x ys

Quali firma ha questa funzione? Assomiglia elem :: a -> [a] -> Bool. Ma il compilatore si lamenterà perché hai scritto x == y, e non per ogni a viene definita la funzione di ==, solo per coloro che sono a nel Eq tipo di classe . Quindi è necessario specificare qualcosa come "per tutti gli a che sono in Eq ...". E proprio per questo è necessario =>. Quindi la firma corretta per elem è elem :: Eq a => a -> [a] -> Bool.

Il @ ti dà la possibilità di dare una intera struttura di un nome e di pattern match su di esso allo stesso tempo. Per esempio. se avete la a@(x:xs) modello e si chiama quella funzione con [1,2,3,4], poi a è [1,2,3,4], xis 1 e xs è [2,3,4].