7

如果我有这个插入功能：

insert x []     = [x]
insert x (h:t)
  | x <= h      = x:(h:t)
  | otherwise   = h:(insert x t)

这会产生一个排序列表：

foldr insert [] [1,19,-2,7,43]

但是这个：

foldr1 insert [1,19,-2,7,43]

产生'不能构造无限类型：a0 = [a0] '

我很困惑为什么第二个电话不能工作。

我查看了foldr和foldr1的定义，并使用简单的算术函数进行了跟踪，但我仍然无法明确解释为什么第二次调用失败。

4

5 回答 5

16

让我们看一些类型签名。

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

在这两种情况下，第一个参数都是两个参数的函数。

  • 对于foldr1，这两个参数必须具有相同的类型（并且结果也具有这种类型）
  • 对于foldr，这两个参数可能具有不同的类型（并且结果与第二个参数具有相同的类型）

你的类型是insert什么？

于 2012-12-08T21:43:36.297 回答
11

我喜欢这里给出的基于类型的答案，但我也想给出一个可操作的答案来解释为什么我们不希望它进行类型检查。让我们从源代码foldr1开始：

foldr1          :: (a -> a -> a) -> [a] -> a
foldr1 _ [x]    = x
foldr1 f (x:xs) = f x (foldr1 f xs)

现在，让我们尝试运行您的程序。

foldr1 insert [1,19,-2,7,43]
= { list syntax }
foldr1 insert (1:[19,-2,7,43])
= { definition of foldr1 }
insert 1 (foldr1 insert [19,-2,7,43])
= { three copies of the above two steps }
insert 1 (insert 19 (insert (-2) (insert 7 (foldr1 insert [43]))))
= { definition of foldr1 }
insert 1 (insert 19 (insert (-2) (insert 7 43)))

……哎呀！那insert 7 43永远行不通。=)

于 2012-12-09T01:34:58.200 回答
4

foldr1is的类型(a -> a -> a) -> [a] -> a，即该函数的参数和结果具有相同的类型。但是，insert有类型Ord a => a -> [a] -> [a]。用于foldr1 insert良好的类型，a并且[a]必须是相同的类型。

但这意味着a == [a] == [[a]] == [[[a]]] == ...，即，a是一种无限多列表。

于 2012-12-08T21:42:51.823 回答
1

因为foldr1正在尝试这样做：

insert 43 -7

这将失败。

于 2012-12-08T21:41:50.357 回答
1

问题如下：

foldr会这样做：

  1. 结果设置为insert 43 []
  2. 结果设置为insert 7 result
  3. 等等

这显然有效。

而foldr1会尝试执行以下操作：

  1. 结果设置为insert 7 43
  2. 结果设置为insert -2 result
  3. 等等

这绝对是错误的。您可以看到，foldr1要求操作的参数是同一类型，而insert.

于 2012-12-08T21:45:12.893 回答