Haskell: Parse error in pattern x ++ xs

Question

Doing the third of the 99-Haskell problems (I am currently trying to learn the language) I tried to incorporate pattern matching as well as recursion into my function which now looks like this:

myElementAt :: [a] -> Int -> a
myElementAt (x ++ xs) i =
  if length (x ++ xs) == i && length xs == 1 then xs!!0
  else myElementAt x i

Which gives me Parse error in pattern: x ++ xs. The questions:

1. Why does this give me a parse error? Is it because Haskell is no idea where to cut my list (Which is my best guess)?
2. How could I reframe my function so that it works? The algorithmic idea is to check wether the list has the length as the specified inde; if yes return the last elemen; if not cut away one element at the end of the list and then do the recursion.

Note: I know that this is a really bad algorithm, but it I've set myself the challenge to write that function including recursion and pattern matching. I also tried not to use the !! operator, but that is fine for me since the only thing it really does (or should do if it compiled) is to convert a one-element list into that element.

Answer 1

Haskell has two different kinds of value-level entities: variables (this also includes functions, infix operators like ++ etc.) and constructors. Both can be used in expressions, but only constructors can also be used in patterns.

In either case, it's easy to tell whether you're dealing with a variable or constructor: a constructor always starts with an uppercase letter (e.g. Nothing, True or StateT) or, if it's an infix, with a colon (:, :+). Everything else is a variable. Fundamentally, the difference is that a constructor is always a unique, immediately matcheable value from a predefined collection (namely, the alternatives of a data definition), whereas a variable can just have any value, and often it's in principle not possible to uniquely distinguish different variables, in particular if they have a function type.

Yours is actually a good example for this: for the pattern match x ++ xs to make sense, there would have to be one unique way in which the input list could be written in the form x ++ xs. Well, but for, say [0,1,2,3], there are multiple different ways in which this can be done:

[] ++[0,1,2,3]
[0] ++ [1,2,3]
[0,1] ++ [2,3]
[0,1,2] ++ [3]
[0,1,2,3]++ []

Which one should the runtime choose?

Answer 2

Presumably, you're trying to match the head and tail part of a list. Let's step through it:

myElementAt (x:_) 0 = x

This means that if the head is x, the tail is something, and the index is 0, return the head. Note that your x ++ x is a concatenation of two lists, not the head and tail parts.

Then you can have

myElementAt(_:tl) i = myElementAt tl (i - 1)

which means that if the previous pattern was not matched, ignore the head, and take the i - 1 element of the tail.

Answer 3

In patterns, you can only use constructors like : and []. The append operator (++) is a non-constructor function.

So, try something like:

myElementAt :: [a] -> Int -> a
myElementAt (x:xs) i = ...

There are more issues in your code, but at least this fixes your first problem.

Answer 4

in standard Haskell pattern matches like this :

f :: Int -> Int
f (g n 1) = n

g :: Int -> Int -> Int
g a b = a+b

Are illegal because function calls aren't allowed in patterns, your case is just a special case as the operator ++ is just a function.

To pattern match on lists you can do it like this:

myElementAt :: [a] -> Int -> a
myElementAt (x:xs) i = // result

But in this case x is of type a not [a] , it is the head of the list and xs is its tail, you'll need to change your function implementation to accommodate this fact, also this function will fail with the empty list []. However that's the idiomatic haskell way to pattern match aginst lists.

I should mention that when I said "illegal" I meant in standard Haskell, there are GHC extensions that give something similar to that , it's called ViewPatterns But I don't think you need it especially that you're still learning.