Haskell - Como criar uma função mapTree baseada em uma pasta de uma BinaryTree?

Question

Esta é uma pergunta do Capítulo 11, Tipos de dados algébricos de "Programação Haskell a partir dos primeiros princípios":

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

Na verdade, não inserimos um valor em uma árvore existente; cada vez que queremos inserir um valor na estrutura de dados, construímos uma árvore totalmente nova:

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)

Esta é uma função de mapa para a estrutura de dados de 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)

Escreva pasta para BinaryTree

Dada a definição de BinaryTree que fornecemos, escreva um catamorfismo para as árvores binárias.

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

O tipo acima é uma dica para quem não converte a árvore em uma lista antes de aplicar a função de dobra.

Reescrever mapa para BinaryTree

Usando o foldTree que você acabou de escrever, reescreva mapTree usando foldTree. A ausência de uma restrição Ord é intencional, você não precisa usar a função insert.

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

Consegui obter uma resposta que funciona para a primeira pergunta sobre foldr com muita ajuda de:https://github.com/johnchandlerburnham/hpfp/blob/master/11/BinaryTree.hs

Minha resposta:

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

No entanto, para a segunda pergunta sobre como escrever um novo mapTree para BinaryTree, não consegui encontrar uma resposta para isso. O mapTree original é fornecido acima. Mesmo a resposta no link johnchandlerburnham usa um foldtree diferente.

Alguém poderia, por favor, ajudar a obter uma resposta viável para a segunda pergunta com base na minha resposta à primeira pergunta? Ou é necessária outra resposta para a primeira pergunta?

Uma árvore para teste poderia ser:

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

Answer 1

Você não pode escrever mapTreeusando a foldTreecom essa assinatura. (Como observa @chi, o problema técnico é que foldTreetem a assinatura errada para ser um verdadeiro catamorfismo para BinaryTree.) Na verdade, se você carregar esse arquivo Haskell vinculado BinaryTree.hs, verá que mapTree'não funciona corretamente:

λ> :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

Ele fornece os valores de nó corretos, mas a estrutura da árvore está errada.

Não tenho uma cópia desse livro, então não posso ver exatamente o que você está vendo, mas talvez essas notas sejam úteis. No final da seção 11.15, o autor fala sobre as versões de 2 e 3 parâmetros de foldTree, e mostra que apenas mapTree'escrito para usar a versão de 3 parâmetros funcionará corretamente.