1

这是一个相对简单的haskell问题，但我遇到了很多麻烦。我正在尝试应用此函数“添加”将字符串列表转换为 BST。（add 函数只是插入一个术语）我的问题是如何定义折叠，以便将 add 函数应用于 [String] 以便它基本上一个一个地插入每个函数？

我最初的想法是，我将应用于 xs 的函数将是 (add _ basetree)，其中 _ 将是 xs 的每个元素，而基树将是具有一个元素 x 的树。然后 foldr 只会将该函数应用于 xs 的每个元素。我不确定出了什么问题，但这给了我一个错误。

*** Expression     : foldr1 (add x (add x Empty)) xs
*** Term           : add x (add x Empty)
*** Type           : BST
*** Does not match : [Char] -> [Char] -> [Char]

 

data BST = MakeNode BST String BST
           | Empty

add :: String -> BST -> BST

listToTree :: [String] -> BST
listToTree (x:xs) = foldr (add x (add x Empty)) xs -- Here***

如果有人可以帮助我，那就太好了。我花了将近 3 个小时试图弄清楚这个文件夹已经..

4

3 回答 3

8

正如 Gabriel 在评论中所说，您正在以一种非常不寻常的方式将手动递归（模式匹配(x:xs)）与foldr。通常您想使用手动递归，或者foldr在递归遵循“重复将函数应用于列表的元素直到用尽列表”的模式的情况下使用。

我假设你的add函数看起来像这样：

add :: String -> BST -> BST
add string Empty            = MakeNode Empty string Empty
add string (MakeNode l s r) =
    if string < s
        then MakeNode (add string l) s r
        else MakeNode l s (add string r)

有了这个，该函数listToTree通常会以两种方式之一编写。首先是使用模式匹配和递归：

listToTree []     = Empty
listToTree (x:xs) = add x (listToTree xs)

也就是说，要么你有一个空列表，在这种情况下你返回空树，或者你有一个头后跟一个尾，在这种情况下，你将列表的头部添加到列表尾部返回的树中。

另一种方法是listToTree通过折叠列表来编写。这为您抽象出递归，这样您就可以编写

listToTree = foldr add Empty

这是有效的，因为foldr有类型

foldr :: (a -> b -> b) -> b -> [a] -> b

并且add有Empty类型

add   :: String -> BST -> BST
Empty :: BST

专门化类型a和b，你得到

foldr :: (String -> BST -> BST) -> BST -> [String] -> BST

意思就是

foldr add Empty :: [String] -> BST

您应该更喜欢哪一个？也许第一个对于初学者来说更容易阅读和理解。然而，随着您获得更多使用 Haskell 的经验，您会发现第二个版本变得更容易理解。它也更简洁，而且它是以折叠的形式编写的这一事实允许更频繁地触发列表融合规则，这可能会产生更高效的代码。

了解文件夹

在我看来，理解折叠的关键是要意识到折叠会用你给它的任何函数和常量替换列表构造函数。在 Haskell 中，列表有两种可能的构造函数：

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

当您对所有语法进行脱糖处理时，列表实际上看起来像这样（这是有效的 Haskell - 试试看！）

xs = 1 : 2 : 3 : []

当您调用foldr op x0 xs时，折叠有效地将所有(:)构造函数xs替换为op，并将所有[]构造函数替换为x0：

foldr op x0 xs = 1 `op` 2 `op` 3 `op` x0

当然，这里有一个歧义，因为我们不知道是op左联还是右联。为了使类型起作用，您必须提供一个与右侧关联的函数（这就是它被称为右折叠的原因），如下所示：

foldr op x0 xs = 1 `op` (2 `op (3 `op` x0))

左折叠是相同的，除了它关联到左侧（并将初始值放在列表的开头而不是结尾）所以你最终得到

foldl op x0 xs = ((x0 `op` 1) `op` 2) `op` 3
于 2013-02-28T23:01:08.537 回答
2

看起来你想要：

listToTree = foldr add Empty

foldr有类型(a -> b -> b) -> b -> a

所以它需要和累加器函数和一个初始值。Empty是您的初始树值，并add在给定元素和现有树的情况下构造一棵新树。

于 2013-02-28T22:57:28.027 回答
2

foldr 的类型是

(a -> b -> b) -> b -> [a] -> b,

即它接受一个函数，该函数接受ab，和一个[a] 的列表，并返回a b。现在添加这里是

(String -> BST -> BST),

所以它变成了

(String -> BST -> BST) -> BST -> [String] -> BST,

现在，我无法编译它，因为我没有添加功能，但我相信

listToTree (x:xs) = foldr add (add x (add x Empty)) xs

会成功的。它的类型签名至少是相同的。现在这应该将列表的开头添加两次，但是您的 Add 函数可能会忽略重复项？如果你能包括它会更好，这样我们就可以进一步调查它。

于 2013-02-28T22:55:09.063 回答