Haskell pattern match error with bind operator

299 views Asked by At

I have a task, where I am stuck at a point, where I do not get any further. Given is a function:

transpose :: [[a]] -> [[a]]
transpose []       =  []
transpose ([]:ls)  =  transpose ls
transpose ll       =  [h | (h:_) <- ll] : transpose [t |(_:t) <- ll]

I shall write it again using the do-notation on the one hand and the bind-operator on the other hand. I may use hd, tl and (:). I do not have problems with the do-notation solution but there is a pattern matching problem with the bind version. Here is, what I have so far:

transheadA ll = ll >>= \(h:_) ->
    return h

transtailA ll = ll >>= \(_:t) ->
    return t

transposeA :: [[a]] -> [[a]]
transposeA []       =  []
transposeA ([]:ls)  =  transposeA ls
transposeA ll       =  (transheadA ll : transposeA (transtailA ll))

The same style for the do-notation works but with the bind operator I get a pattern match error at transheadA with

\(h:_) -> ...

See:

transposeA [[1,2,3],[4,5,6],[7,8]]
[[1,4,7],[2,5,8],[3,6*** Exception: transpose.hs:(16,22)-(17,24): Non-exhaustive patterns in lambda

I was thinking about how to solve this problem a longer time but I do not know, where to add a new pattern to let this work.

EDIT

I just want hints, of course. Direct solutions are not the sense of the homework nor of this board. Thank You

EDIT SOLUTION

Thanks to CommuSoft I could solve this problem, I think. My solution now is the following:

transheadA :: [[a]] -> [a]
transheadA ll = ll >>= f
    where f (h:_) = return h
          f _     = fail []


transtailA :: [[a]] -> [[a]]
transtailA ll = ll >>= f
    where f (_:t) = return t
          f _     = fail []

transposeA :: [[a]] -> [[a]]
transposeA []       =  []
transposeA ([]:ls)  =  transposeA ls
transposeA ll       =  (transheadA ll : transposeA (transtailA ll))
1

There are 1 answers

0
willeM_ Van Onsem On BEST ANSWER

There are a few problems with this approach:

  • The signature of transheadA should be different than the one for transtailA.

    transheadA :: [[a]] -> [a]
    transtailA :: [[a]] -> [[a]]
    
  • Since you do some pattern matching in the list comprehension, you cannot simply use this in the lambda expression: it is possible the pattern fails in which case that part of the list comprehension fails as well. You can inline this as:

    where f (h:_) = return h
          f _ = fail []
    

    Then you can use f in the side of the binding operator >>=. Clearly this has an impact on how to encode things. Implicitly for each such pattern matching (thus everything not x <- with x a single variable) Haskell could have written such fail (be aware Haskell does not necessarily uses the list monad).

  • As you can read here for the list monad, you don't need to use return, although in this context it not much of a problem, but will reduce the length of your code. In that case you need to replace the right hand side of the expression with [x] instead of x.

Based on the above hints, I've managed to fix your implementation of transpose myself. I hope this clarifies a thing or two?