haskell - 尝试使用中序遍历在 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 的事情我还没有完全弄清楚。任何帮助以及如何解决这个问题将不胜感激。谢谢!

编辑:

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

Answer 1

类型必须适合:

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]。

这个论证的意义是什么？与折叠一样，数据类型定义中的每个“变体”都有一个对应的折叠函数参数。

您的(缺少的)数据类型定义是:

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 是“将每个 Leaf 转换为的值”。

最自然的选择就是[]。实际上，这是唯一的选择，因为我们还不知道有关 a 类型(在 [a] 中)的任何信息。