Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Rewrite haskell list comprehension in do-notation

I have read in Learn you a Haskell, that list comprehensions in Haskell could be rewritten as monadic joins or (which is practically the same) do-notation.

However, when I try to rewrite the following code (produce all possible lists having each element from one of given lists):

c :: [[a]] -> [[a]]
c []     = [[]]
c (x:xs) = [a:b | a <- x, b <- c xs]

in such a manner:

d :: [[a]] -> [[a]]
d []     = [[]]
d (x:xs) = do
              a <- x
              b <- d xs
              return a:b

I get the following error:

Couldn't match type `a' with [a]
    `a' is a rigid type variable bound by
        the type signature for d :: [[a]] -> [[a]] 
Expected type: [[a]]
  Actual type: [a] 
In the second argument of `(:)', namely `b' 
In a stmt of a 'do' block: return a : b

if I change the last line of do to this: return a:[b], I don't get errors, but the result is obviously incorrect:

ghci> c [[1, 2], [3, 4]] 
[[1,3],[1,4],[2,3],[2,4]]

ghci> d [[1, 2], [3, 4]]
[[1],[3],[1],[],[1],[4],[1],[],[2],[3],[2],[],[2],[4],[2],[]]

So the questions are:

  1. How can I rewrite this list comprehension?
  2. Are list comprehension and do-notation interchangeable, how replacement can be done generically?
like image 960
sukhmel Avatar asked Feb 24 '14 18:02

sukhmel


2 Answers

Look closely at the error message:

Couldn't match type `a' with [a]
    `a' is a rigid type variable bound by
        the type signature for d :: [[a]] -> [[a]] 
Expected type: [[a]]
  Actual type: [a] 

In the second argument of `(:)', namely `b' In a stmt of a 'do' block: return a : b

This means that it was parsed as

(return a) : b

and thus b became the second argument to (:) there; but you intended it as

return (a : b)
like image 106
Will Ness Avatar answered Sep 22 '22 14:09

Will Ness


You need brackets.

return (a:b)
like image 22
MathematicalOrchid Avatar answered Sep 20 '22 14:09

MathematicalOrchid