Haskell 中是否有标准的树映射函数？

Question

我需要编写一个非递归函数来转换我的树。但是我不能对树使用我自己的地图功能。 Haskell中是否有树的标准映射函数？

data BTree a = Tip a | Bin (BTree a) (BTree a)
exapmeTree = Bin (Bin (Tip [1,2,3,4,5]) (Tip [3,9,7])) (Bin (Tip [6,7,8,9]) (Tip [8,2,1]))
myReverse list = foldl (\acc x -> x : acc) [] list

reverseTree tree = map myReverse tree

Answer 1

由于您自己创建了 BTree 类型，不，它没有标准函数。不过，您可以很容易地自己编写一个 Functor 实例。

instance Functor BTree where
  fmap f (Tip a)   = Tip (f a)
  fmap f (Bin l r) = Bin (fmap f l) (fmap f r)

现在你可以写 reverseTree tree = fmap myReverse tree.

请注意 fmap 与列表上下文中的 map 完全相同，但它更通用，这意味着它适用于任何 Functor 实例。

Answer 2

您可以自己编写 fmap 函数，如 Rik 所演示的。

或者你可以使用自动生成的Functor实例提供的fmap函数

在ghci下测试：

$ ghci
GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :set -XDeriveFunctor
 λ> 
 λ> data BTree a = Tip a | Bin (BTree a) (BTree a)  deriving (Eq, Show, Functor)
 λ> 
 λ> exampleTree = Bin (Bin (Tip [1,2,3,4,5]) (Tip [3,9,7])) (Bin (Tip [6,7,8,9]) (Tip [8,2,1]))
 λ> 
 λ> reverseTree = fmap reverse exampleTree
 λ> 
 λ> reverseTree 
 Bin (Bin (Tip [5,4,3,2,1]) (Tip [7,9,3])) (Bin (Tip [9,8,7,6]) (Tip [1,2,8]))
 λ>

Haskell 中是否有标准的树映射函数？

Is there a standard map function for trees in Haskell?

tree

haskell

map-function