Reputation: 1675
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
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 Int
s, the second is a list containing an empty lists of Int
s. 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 Int
s. 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