I'm trying to implement the reverse of a list:
myLast :: [a] -> a
myLast [] = error "No end for empty lists!"
myLast [x] = x
myLast (_:xs) = myLast xs
myReverse :: [a] -> [a]
myReverse (x:xs) = myLast xs + myReverse xs
but I get this error:
/workspaces/hask_exercises/exercises/src/Lib.hs:42:32: error:
* Occurs check: cannot construct the infinite type: a ~ [a]
* In the second argument of `(+)', namely `myReverse xs'
In the expression: myLast xs + myReverse xs
In an equation for `myReverse':
myReverse (x : xs) = myLast xs + myReverse xs
* Relevant bindings include
xs :: [a] (bound at src/Lib.hs:42:14)
x :: a (bound at src/Lib.hs:42:12)
myReverse :: [a] -> [a] (bound at src/Lib.hs:41:1)
|
42 | myReverse (x:xs) = myLast xs + myReverse xs
| ^^^^^^^^^^^^
What does it mean that cannot construct the infinite type: a ~ [a]? I get this error a lot and would like to understand what it means.
You have
myLast :: [a] -> a
myReverse :: [a] -> [a]
myReverse (x:xs) = myLast xs + myReverse xs
\___a___/ \____[a]___/
(x:xs) :: [a]
---------------
x :: a
xs :: [a] xs :: [a]
myLast :: [a] -> a myReverse :: [a] -> [a]
------------------------- ----------------------------
myLast xs :: a myReverse xs :: [a]
myReverse (x:xs) :: [a]
but
> :t (+)
(+) :: Num a => a -> a -> a
which means that the type of the thing on the left of + and the type of the thing on the right must be the same.
But they can't be: as we just saw above, in your code the first (of myLast xs) is some type a, and the second (of myReverse xs) is [a] the list of those same as.
These two can't be the same, because it would mean
a ~ [a] OK, this is given to us, then
a ~ [a] we can use it, so that
--------------
a ~ [[a]] this must hold;
a ~ [a] we know this, then
--------------
a ~ [[[a]]] this must also hold; and
a ~ [a] ........
-------------- ........
a ~ [[[[a]]]] ........
.........................
and so on ad infinitum, thus making this a an "infinite" type. Hence the error.
You could fix it by replacing the + with
(+++) :: a -> [a] -> [a]
and implementing it to do what you need it to do.
You will also need to fix your off-by-one error whereby you completely ignore the first element in the received input, x.