Geek Answers Handbook

Haskell: foldr vs foldr1

If I have this insert function:

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

creates a sorted list:

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

but this:

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

produces 'cannot build an infinite type: a0 = [a0]'

I am confused by why the second call cannot work.

I have examined the definitions for foldr and foldr1 and can be traced using simple arithmetic functions, but I still cannot give a clear explanation of the reasons for the failure of the second call.

+6
source share
5 answers

Let's look at some types of signatures.

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

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

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

What type of your insert ?

+14
source

I like the type-based answers given here, but I also want to give some up-to-date information explaining why we don't want this to be typecheck checked. Take the source of foldr1 to start with:

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

Now try to run 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)))

... oops! This insert 7 43 will never work. =)

+8
source

The type foldr1 is (a -> a -> a) -> [a] -> a , that is, the arguments and the result of this function are of the same type. However, insert is of type Ord a => a -> [a] -> [a] . For correct input, foldr1 insert a and [a] must be of the same type.

But this would mean that a == [a] == [[a]] == [[[a]]] == ... , i.e. a is a type of an infinite number of lists.

+3
source

Because foldr1 trying to do this:

 insert 43 -7

which will fail.

+1
source

The problem is as follows:

foldr will do it like this:

  • result insert 43 []
  • result insert 7 result
  • etc.

This clearly works.

While foldr1 will try to do the following:

  • result insert 7 43
  • result insert -2 result
  • and etc.

which is definitely wrong. You can see, foldr1 requires the operation arguments to be of the same type, which is not the case with insert .

+1
source

More articles:


All Articles