CODEWITHSUNDEEP
haskell
Joao Parente
Joao Parente

Reputation: 453

Why does foldr give me this error?

foldr (\x ante->[x]:[ante]) [4] [1,2,3]

So if I get foldr right, the first time the function (\x ante->[x]:[ante]) will do something, I will call this function f, it will be in:

   f 3 [4] = [3]:[[4]] = [[3],[4]]

Why doesn't the function do this? It shows this error instead:

* Occurs check: cannot construct the infinite type: a ~ [a]
  Expected type: [a]
    Actual type: [[a]]
* In the expression: [x] : [ante]
  In the first argument of `foldr', namely
    `(\ x ante -> [x] : [ante])'
  In the expression: foldr (\ x ante -> [x] : [ante]) [4] [1, 2, 3]
* Relevant bindings include
    ante :: [a] (bound at testefoldr.hs:51:21)
    x :: a (bound at testefoldr.hs:51:19)
    folder4 :: [a] (bound at testefoldr.hs:51:1)
   |51 | folder4 = foldr (\x ante->[x]:[ante]) [4] [1,2,3]

I created a .hs then I put 

folder4 = foldr (\x ante->[x]:[ante]) [4] [1,2,3]

for faster testing. That's why there is folder4 in the error.

Upvotes: 2

Views: 71

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477190

The foldr function has type:

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

So that means that it takes as input an element (type a) of the list to fold, together with the accumulator (type b), and returns an accumulator (again type b). In case Haskell was not statically typed, it would each time wrap the accumulator in a new list. So it would result in:

[4]
-> [[3],[4]]
-> [[2],[[3],[4]]]
-> [[1],[[2],[[3],[4]]]]

which makes no sense.

There are two problems here:

  1. if ante has type b, then [x] : [ante] has type [b]; and
  2. the type of the initial accumulator [4] is not the result of the foldr.

So you can fix this by writing:

foldr (\x ante->[x]:ante) [[4]] [1,2,3]

Upvotes: 4

chi
chi

Reputation: 116174

Let's pretend this type checks, and run it anyway

foldr (\x ante->[x]:[ante]) [4] [1,2,3]

Let's write f for \x ante -> [x]:[ante].

foldr f [4] [1,2,3]
=
f 1 (f 2 (f 3 [4]))
=
f 1 (f 2 ([3]:[[4]]))
=
f 1 (f 2 [[3],[4]])

So far, so good.

=
f 1 ([2] : [[[3],[4]]])
=
f 1 [[2] , [[3],[4]] ]

Now we're in trouble. Is that a [[Int]] or a [[[Int]]]? Things get even worse if we continue.

The problem is that f must return a value of the same type as that of its second argument. Otherwise, we can't compose f in the way foldr does. Your f does not do that, instead adding a [] to the type at every call.

Upvotes: 3

Related Questions