Haskell:foldr vs foldr1

Question

如果我有这个插入功能:

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的定义,并使用简单的算术函数进行了跟踪,但我仍然无法清楚地解释为什么第二次调用失败.

Answer 1

我们来看一些类型的签名.

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

在这两种情况下,第一个参数是两个参数的函数.

• 因为foldr1,这两个参数必须具有相同的类型(结果也具有此类型)
• 因为foldr,这两个参数可能有不同的类型(结果与第二个参数的类型相同)

你的类型是insert什么？

Answer 2

我喜欢这里给出的基于类型的答案,但我也想提供一个可操作的答案,解释为什么我们不希望这样做.让我们从源头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永远不会奏效.=)

Answer 3

因为foldr1正在尝试这样做：

insert 43 -7

这将会失败。