Haskell List Comprehension and List Monad

user_10254215 0
Viewed 161

I'm trying to write some self-defined type Martix a, which is basically list of lists [[a]]. When I tried to implement a function named colAt, which should give the vertical elements of a matrix, I firstly used the list comprehension:

colAt :: Int -> Matrix a -> [a]
colAt c m = [ e | r <- m, e <- r !! c ]

But Ghci told me

Occurs check: cannot construct the infinite type: a ~ [a]
In the expression: r !! c

While the do notation worked perfectly with

colAt :: Int -> Matrix a -> [a]
colAt c m = do
    r <- m
    return (r !! c)

What caused this error? I thought that basically list comprehension is a syntax sugar of list do notations, but given this error my understanding is wrong?

list-comprehension monads haskell
2 Answers

If you write e <- r !! c, it expects r !! c to be a list, since you are enumerating over that list, but r !! c is an item (of type a), hence that would only work if you use for example a Matrix [a].

You do not need to enumerate here, you can move the r !! c to the "yield" part:

colAt :: Int -> Matrix a -> [a]
colAt c m = [ r !! c | r <- m ]

but what you here do is a mapping, so you can use map :: (a -> b) -> [a] -> [b]:

colAt :: Int -> Matrix a -> [a]
colAt c = map (!! c)
user_675790

Your understanding is entirely correct: list comprehensions are indeed just syntax sugar for do notation! The issue is that you have not desugared your list comprehension correctly.

To start, let’s repeat the list comprehension for reference:

colAt :: Int -> Matrix a -> [a]
colAt c m = [ e | r <- m, e <- r !! c ]

Now, I’ll desugar it partially, to move the r <- m bit outside the comprehension:

colAt :: Int -> Matrix a -> [a]
colAt c m = do
    r <- m
    [e | e <- r !! c]

And this is simple to desugar fully:

colAt :: Int -> Matrix a -> [a]
colAt c m = do
    r <- m
    e <- r !! c
    e

Compare to the correct implementation:

colAt :: Int -> Matrix a -> [a]
colAt c m = do
    r <- m
    return (r !! c)

The issue here is now obvious. In the correct implementation takes m, then for each item r <- m in turn, finds the element r !! c :: a, wraps it in a list, and then returns it. By contrast, your implementation extracts each item r <- m correctly, but then tries to extract each ‘element’ of the ‘list’ r !! c :: a — which is in fact not necessarily a list, giving the type error you see. The fix is easy: as in the correct implementation, simply add a return, giving [ e | r <- m, e <- return (r !! c) ]. Or, more simply, using the fact that [x | x <- return l] is just the same as [l], you can rewrite this more simply as [ r !! c | r <- m ].

user_73452980
Related