Haskell - Come creare una funzione mapTree basata su una cartella di un BinaryTree?

Question

Questa è una domanda dal capitolo 11, Tipi di dati algebrici di "Programmazione Haskell dai primi principi":

data BinaryTree a =
  Leaf
  | Node (BinaryTree a) a (BinaryTree a)
  deriving (Eq, Ord, Show)

In realtà non inseriamo un valore in un albero esistente; ogni volta che vogliamo inserire un valore nella struttura dati, costruiamo un albero completamente nuovo:

insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
insert' b Leaf = Node Leaf b Leaf
insert' b (Node left a right)
  | b == a = Node left a right
  | b < a = Node (insert' b left) a right
  | b > a = Node left a (insert' b right)

Questa è una funzione mappa per la struttura dati di BinaryTree:

mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left a right) = 
  Node (mapTree f left) (f a) (mapTree f right)

Scrivi folder per BinaryTree

Data la definizione di BinaryTree che abbiamo fornito, scrivere un catamorfismo per gli alberi binari.

-- any traversal order is fine
foldTree :: (a -> b -> b) 
  -> b 
  -> BinaryTree a 
  -> b

Il tipo sopra è un suggerimento per coloro che non convertono l'albero in un elenco prima di applicare la funzione di piegatura.

Riscrivi mappa per BinaryTree

Usando il foldTree che hai appena scritto, riscrivi mapTree usando foldTree. L'assenza di un vincolo Ord è intenzionale, non è necessario utilizzare la funzione insert.

mapTree' :: (a -> b)
  -> BinaryTree a
  -> BinaryTree b
mapTree' f bt =
  foldTree undefined undefined undefined

Sono riuscito a ottenere una risposta che funzioni per la prima domanda su folder con molto aiuto da:https://github.com/johnchandlerburnham/hpfp/blob/master/11/BinaryTree.hs

La mia risposta:

foldTree f b Leaf = b
foldTree f b (Node left a right) 
  = (foldTree f tempb left) where
    tempb = (f a) tempright
    tempright = foldTree f b right

Tuttavia, per la seconda domanda sulla scrittura di un nuovo mapTree per BinaryTree, non sono riuscito a trovare una risposta. Il mapTree originale è fornito sopra. Anche la risposta al link johnchandlerburnham utilizza un diverso foldtree.

Qualcuno potrebbe aiutarmi a ottenere una risposta praticabile per la seconda domanda in base alla mia risposta alla prima domanda? O è necessaria un'altra risposta per la prima domanda?

Un albero per il test potrebbe essere:

testTree :: BinaryTree Integer
testTree =
  Node (Node Leaf 3 Leaf) 1 (Node Leaf 4 Leaf)

Answer 1

Non puoi scrivere mapTreeusando a foldTreecon quella firma. (Come osserva @chi, il problema tecnico è che foldTreeha la firma sbagliata per essere un vero catamorfismo per BinaryTree.) In effetti, se carichi quel file Haskell collegato BinaryTree.hs, vedrai che mapTree'lì non funziona correttamente:

λ> :l BinaryTree
λ> mapTree (+1) testTree
Node (Node Leaf 2 Leaf) 3 (Node Leaf 4 Leaf)
λ> mapTree' (+1) testTree
Node (Node (Node Leaf 3 Leaf) 2 Leaf) 4 Leaf

Fornisce i valori dei nodi corretti, ma la struttura dell'albero è sbagliata.

Non ho una copia di quel libro, quindi non posso vedere esattamente quello che stai vedendo, ma forse queste note saranno utili. Alla fine della sezione 11.15, l'autore parla delle versioni a 2 e 3 parametri di foldTree, e mostra che solo le versioni mapTree'scritte per usare la versione a 3 parametri funzioneranno correttamente.