Haskell Noob question: What's wrong with my append function?
-
18-09-2019 - |
Question
I'm trying to write a Haskell append function... Here's what I have:
myappend :: [a] -> [a] -> [a]
myappend [] x = x
myappend [x:xs] y = x : myappend xs y
But it's giving me an error: Occurs check: cannot construct the infinite type: a = [a] When generalising the type(s) for `myappend'
So, obviously there's something wrong with it but I can't see it... What's wrong with my append function?
Solution
The constructors of the type [a] are:
[] The empty list
(:) Cons operator (just a regular infix constructor)
So, you must use:
myappend :: [a] -> [a] -> [a]
myappend [] x = x
myappend (x:xs) y = x : myappend xs y
The syntax
[x:xs]
is pretty much equivalent to
[(x:xs)]
which matches a list with one element, a non-empty list, and has type
[(x:xs)] :: [[a]]
I recommend reading this page if you want to understand the constructor and pattern matching concept.
OTHER TIPS
The pattern in the second case of the function should just be (x:xs)
, not [x:xs]
:
myappend (x:xs) y = x : myappend xs y
x:xs
matches an element followed by a list, the parenthesis are just there to make it syntactically clear what belongs to that pattern. [x:xs]
would match a list containing x:xs
.
There should be no []
brackets in
myappend (x:xs) y = x : (myappend xs y)
[1,2,3]
and 1:2:3:[]
are different ways of defining the same list.
So that [x:xs]
matches one item list consisting of another list.