Haskell Noob question: What's wrong with my append function?

Question

Hi guys, 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?

Answer 1

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.

Answer 2

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.

Answer 3

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.