user3097712
user3097712

Reputation: 1675

Parse error in pattern: xs - understanding

i have the following two functions in haskell:

plusList :: [[Int]] -> [Int]
plusList [xs ys] = add xs + plusList [ys]
plusList [[]] = 0


add::[Int] -> Int
add (x:xs) = x + add xs
add [] = 0

so, i think i have the error in plusList [xs ys] = add xs + plusList ys

My idea was to go through the set of the sets, namely [[Int]], by taking the first List xs, apply "add" on it and after that, call the second list ys recursively with "plusList ys"

I am new in haskell, can I do that? And if no, why?

Upvotes: 0

Views: 138

Answers (1)

bheklilr
bheklilr

Reputation: 54058

You can certainly do what you want in Haskell, but your syntax is wrong. Your add function is correct, but plusList is not. In particular, the syntax [xs ys] makes no sense as a pattern to Haskell, you probably want

plusList (xs:ys) = add xs + plusList ys

Notice how this is exactly the same pattern as with add? Although, from your type signature it's hard to tell what exactly you want. The type says return a list of Int, but your function body says to just return an Int. If you want the former, you can achieve it with

plusList (xs:ys) = add xs : plusList ys

But this is exactly map add! If instead you want the latter, use the first snippet from above.

The second problem you have is

plusList [[]] = 0

This is a perfectly valid and legal line of Haskell code, but it won't do what you want. You see, there's a difference between [] :: [[Int]] and [[]] :: [[Int]]. The first is an empty list of lists of Ints, the second is a list containing an empty lists of Ints. If you run length ([] :: [[Int]]), you'll get 0, but for length ([[]] :: [[Int]]) you'll get 1!. Instead, just do

plusList [] = 0

Again, this is exactly like the pattern in add. If you want plusList to return [Int] instead, this line should just be

plusList [] = []

So the two versions we have are

plusList :: [[Int]] -> Int
plusList (xs:ys) = add xs + plusList ys
plusList [] = 0

And

plusList :: [[Int]] -> [Int]
plusList (xs:ys) = add xs : plusList ys
plusList [] = []
-- or just
-- plusList xs = map add xs

There is an easier way to do this, though. Firstly, add is merely the built-in sum function but specialized to Ints. However, the built-in sum is not very efficient due to the fact that it uses foldl. Instead, you can implement a faster variant with

add :: [Int] -> [Int]
add xs = foldr (+) 0 xs

The foldr and foldl functions generalize the kind of recursion you have used, since it is such a common pattern in functional programming. Instead of operating on the entire list, you provide a function for combining the next value and an accumulator together, an initial accumulator value, and the values to accumulate. In your case, the accumulator has the same type as your values, which is pretty common. The difference between foldl and foldr is subtle, their implementations look pretty similar, but Haskell's laziness means that foldl can have space leaks and efficiency problems (there's plenty of explanations out there as to why, look it up when you get there).

Additionally, if you want to sum a list of lists, you can do it using higher order functions with simply

plusList = add . map add

Nothing extra is needed, no patterns to match, much less syntax to get wrong.

Upvotes: 10

Related Questions