Haskell二叉树前序遍历函数类型签名疑问咨询

嘿，我来帮你拆解一下你看到的那个函数声明，顺便梳理下你自己的代码问题，很快就能搞明白啦！

首先先说说你自己的代码：你定义的Tree类型是这样的：

data Tree = Node Int Tree Tree | Leaf Int deriving (Eq,Show)

这个树的节点和叶子都只能存Int类型，所以你最初设想的preorder :: Tree -> [a]其实不太准确——因为你的树里只有Int，没法返回任意类型a的列表，正确的声明应该是preorder :: Tree -> [Int]才对。

接下来解释你看到的那个通用版函数声明：preorder :: (a -> c) -> (b -> c) -> Tree -> [c]。这个函数其实是针对更灵活的二叉树类型设计的，不是你现在用的这个只存Int的特定树。

拆解这个函数的参数与用途 #

这个函数确实接收三个输入：

• 第一个参数(a -> c)：这是一个转换函数，用来把树节点中存储的a类型值，转换成我们最终想要的c类型。
• 第二个参数(b -> c)：另一个转换函数，用来把树叶子中存储的b类型值，也转换成c类型。
• 第三个参数Tree：这里的Tree其实是一个通用二叉树类型，比如它的定义可能是这样的：

  data Tree a b = Node a (Tree a b) (Tree a b) | Leaf b deriving (Eq,Show)
  

  也就是说，这个树的节点可以存任意a类型，叶子可以存任意b类型（a和b可以是不同类型）。

函数的返回值[c]，就是把整个树里的所有节点、叶子，都通过前面两个转换函数统一成c类型后，按前序遍历顺序收集起来的列表。

举个例子更直观 #

假设我们有一个通用树，节点存字符串，叶子存整数：

myTree :: Tree String Int
myTree = Node "foo" (Leaf 1) (Node "bar" (Leaf 2) (Leaf 3))

如果我们想把整个树的元素都转成字符串，然后前序遍历输出，就可以这样调用那个通用函数：

preorder id show myTree

这里：

• id :: String -> String：直接保留节点的字符串值
• show :: Int -> String：把叶子的整数转换成字符串
  最终会得到结果：["foo", "1", "bar", "2", "3"]

回到你自己的场景 #

你的Tree里节点和叶子都是Int，如果用这个通用函数的话，相当于a和b都是Int，我们可以传入两个id函数（直接返回原Int值），这样调用后就和你想要的功能完全一致：

preorder id id :: Tree -> [Int]

不过对你的特定Tree类型来说，完全没必要这么麻烦，直接写一个只处理Int的前序遍历函数就好，比如：

preorder :: Tree -> [Int]
preorder (Leaf x) = [x]
preorder (Node x left right) = x : preorder left ++ preorder right

内容的提问来源于stack exchange，提问作者Martin