使用 foldl 时无法构造无限类型

Question

我定义了一棵二叉树并使用我的函数创建了一棵新树。

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
    | x < a     = Node a (treeInsert x left) right
    | x > a     = Node a left (treeInsert x right)
    | otherwise = Node a left right

当我在终端中执行此命令时：

let nums = [8,6,4,1,7,3,5]
let numsTree= foldl treeInsert EmptyTree nums

返回错误。

Occurs check: cannot construct the infinite type: a ~ Tree a
Expected type: Tree a -> Tree a -> Tree a
Actual type: a -> Tree a -> Tree a

不过，我把foldl改成foldr后就可以了

let numsTree= foldr treeInsert EmptyTree nums

谁能告诉我为什么？ foldl 和 foldr 在这种情况下有什么区别，我不清楚。谢谢！

Answer 1

foldl的签名是：

foldl :: (<b>b -> a -> b</b>) -> b -> [a] -> b

我们将 foldl 应用于一个函数 (insertTree) 以及一个 Tree 和一个 Int 列表，所以这意味着 b ~ Tree Int, 和 a ~ Int.

所以这意味着到目前为止构造的 Tree 应该是这里的第一个参数。

我们可以用flip :: (a -> b -> c) -> b -> a -> c:

来解决

let numsTree = foldl <b>(flip</b> treeInsert<b>)</b> EmptyTree nums

flip 翻转参数，所以 f x y == flip f y x.

foldl 表示对于列表 [8,6,4]，我们将像这样应用它：

insertTree 4 (insertTree 6 (insertTree 8 EmptyTree))

我们也可以决定使用foldr :: (b -> a -> b) -> b -> [a] -> b（注意参数的顺序已经改变）像：

let numsTree = <b>foldr</b> treeInsert EmptyTree nums

然后对于列表 [8,6,4] 这将导致：

insertTree 8 (insertTree 6 (insertTree 4 EmptyTree))

由于元素在 Tree 中的插入顺序会产生影响，因此两者在语义上，不等效。

Answer 2

foldr 和 foldl 有两点不同。重要的是他们用括号括起计算的方式：

foldl (+) 0 [1..3] = ((0 + 1) + 2) + 3
foldr (+) 0 [1..3] = 1 + (2 + (3 + 0))

另一个是他们期望他们的第一个参数（函数）以相反的顺序接受它的个参数：

> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

我认为造成第二个差异的唯一原因是匹配表达式在第一个代码片段中的书写顺序。您应该根据所需的括号顺序在函数之间进行选择，并在必要时翻转函数以匹配。

所以在你的情况下，两个选项是：

foldr treeInsert EmptyTree nums
foldl (flip treeInsert) EmptyTree nums

使用 foldl 时无法构造无限类型

cannot construct the infinite type when using foldl

haskell

haskell-stack