尝试使用中序遍历将 Haskell 中的树展平

Question

正在尝试使用给定的折叠函数将树展平成列表。

treeFold :: (b -> a -> b -> b) -> b -> Tree a -> b
treeFold _ b Leaf         = b
treeFold f b (Node lt x rt) = f (treeFold f b lt) x (treeFold f b rt)

这是我到目前为止尝试过的：

treeToList :: Tree a -> [a]
treeToList = treeFold (\xs x ys -> xs ++ x : ys) (\x -> [x])

出于某种原因，我无法完全理解如何去做这件事？关于 Haskell，我似乎还没有完全理解某些事情。任何帮助以及如何解决它都将不胜感激。谢谢！

编辑：

我意识到我在这里使用的类型签名近乎荒谬。在 treeFold 的类型签名中，根据我的想法，第二个参数 (b) 可能是一个列表，因为它在这种情况下以某种方式充当累加器。这将使第三个参数（树 a）成为等式左侧参数的某个版本。函数中的两个参数必须是节点中的左右子树。第三个参数只是节点的值。在函数中，我需要按照通常的顺序组合左树、右树和值，但我尝试的所有不同变体都有一些问题

Answer 1

treeFold的类型是

treeFold :: (b -> a -> b -> b) -> b -> Tree a -> b

您想要 return 值列表，[a]。

因此结果类型 b 必须等于 [a]，给我们一个专门的类型签名

treeFold :: ([a] -> a -> [a] -> [a]) -> [a] -> Tree a -> [a]

请注意，第二个参数的类型为 [a]。

您传递的是什么值？

Answer 2

类型必须符合：

treeFold ::           ( b -> a -> b -> b              ) -> b -> Tree a -> b

treeToList = treeFold (\xs   x    ys -> xs ++ (x : ys))    z
-------------------------------------------------------------------
                        b    a    b     b      a   b       b
                                              --------
                                              b

由于x和ys参与同一个:，它们的类型必须兼容：

(:) ::   a  -> [a]  ->  [a]
x   ::   a
ys  ::          b
-------------------
              b ~ [a]

因此我们有

treeFold ::           ( [a] -> a -> [a] -> [a]           ) -> [a] -> Tree a->[a]

treeToList = treeFold (\ xs    x    ys  -> xs ++ (x : ys))     z
-------------------------------------------------------------------
                         [a]   a    [a]    [a]    a   [a]     [a]
                                                 --------
                                                 [a]

结论：最后一个参数 z 的类型必须是 [a].

这个参数是什么意思？与折叠一样，数据类型定义中的每个 "variant" 都有一个对应的折叠函数参数。

您的（缺失的）数据类型定义是：

data Tree a = Node (Tree a)    a   (Tree a)       | Leaf

折叠的类型是

treeFold ::   (         b  ->  a  ->  b  -> b )   ->  b     -> Tree a -> b

对应

的“递归结果持有类型”

data TreeF a r = NodeF  r      a      r           | LeafF

因此z是"the value to convert each Leaf to"。

最自然的选择就是[]。实际上，这是唯一的选择，因为我们对 a 类型（在 [a] 中）一无所知。

尝试使用中序遍历将 Haskell 中的树展平

Attempting to flatten a tree in Haskell using in-order traversal

binary-tree

haskell

functional-programming