Haskell: foldr vs foldr1

Question

If I have this insert function:

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

this produces a sorted list:

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

but this:

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

produces 'cannot construct the infinite type: a0 = [a0]'

I'm confused about why the second call cannot work.

I have looked at the definitions for both foldr and foldr1 and have traced both with simple arithmetic functions, but I still cannot come up with a clear explanation for why the second call fails.

Answer 1

Let's look at some type signatures.

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

In both cases, the first argument is a function of two arguments.

• for foldr1, these two arguments must have the same type (and the result has this type also)
• for foldr, these two arguments may have different types (and the result has the same type as the second argument)

What's the type of your insert?

Answer 2

I like the type-based answers given here, but I also want to give an operational one explaining why we don't want this to typecheck. Let's take the source of foldr1 to start with:

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

Now, let's try running your program.

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)))

...whoops! That insert 7 43 is never going to work. =)