CODEWITHSUNDEEP
haskell
paulo_ferreira
paulo_ferreira

Reputation: 83

Rotate a matrix in Haskell

I have this type Mat a = [[a]] to represent a matrix in haskell. I have to write a function which rotate a matrix, for e.g [[1,2,3],[0,4,5],[0,0,6]] will become [[3,5,6],[2,4,0],[1,0,0]] so I made this:

rotateLeft :: Mat a->Mat a
rotateLeft [[]] = []
rotateLeft (h:t) = (map last (h:t)):(rotateLeft (map init (h:t)))

but the output is 

[[3,5,6],[2,4,0],[1,0,0],[*** Exception: Prelude.last: empty list

I don't know what to put in the base case to avoid this exception. Apreciate any help.

Upvotes: 5

Views: 4600

Answers (5)

okdewit
okdewit

Reputation: 2566

I think the simplest solution would be:

import Data.List

rotateLeft :: [[a]] -> [[a]]
rotateLeft = reverse . transpose

rotateRight :: [[a]] -> [[a]]
rotateRight = transpose . reverse

Data.List is a standard module.

transpose slices rows into columns, which is almost like rotating, but leaves the columns in the wrong order, so we just reverse them.

Upvotes: 7

pigworker
pigworker

Reputation: 43373

I'm an old man in a hurry. I'd do it like this (importing Data.List)

rotl :: [[x]] -> [[x]]
rotl = transpose . map reverse

Upvotes: 9

CR Drost
CR Drost

Reputation: 9807

The problem is that your pattern isn't matching. Stepping through what your code does, we start with:

Prelude> let x = [[1,2,3],[0,4,5],[0,0,6]]
Prelude> :m +Data.List
Prelude Data.List> map last x
[3,5,6]
Prelude Data.List> let y = map init x
Prelude Data.List> y
[[1,2],[0,4],[0,0]]
Prelude Data.List> map last y
[2,4,0]
Prelude Data.List> let z = map init y
Prelude Data.List> z
[[1],[0],[0]]
Prelude Data.List> map last z
[1,0,0]
Prelude Data.List> map init z
[[],[],[]]

So the basic problem is that your base case you're matching on is not [[],[],[]] but is instead [[]], so that pattern doesn't match.

You now have more or less three options: you can (a) try to terminate when the first empty list is seen; this is written in Haskell as any null, using the any function and the null function, both defined in the Prelude; or (b) you can hardcode that this only works for 3x3 matrices, and just match against [[],[],[]], or (c) you can try to terminate when all lists are empty (all null), in which case you can either skip elements that don't exist or wrap everything in the Maybe x datatype, so that missing elements are represented by Nothing while present elements are represented by Just x.

Upvotes: 1

dfridman1
dfridman1

Reputation: 171

rotateLeft []     = []
rotateLeft ([]:_) = []
rotateLeft (h:t)  = (map last (h:t)):(rotateLeft (map init (h:t)))

The first pattern is for the case when the head of the list of lists is longer than other elements.

You got the second pattern wrong: if we have a proper matrix (ie elements are of the same length), then the base case is a list of empty lists. However, you wrote [[]], which is only true if the initial list consists of a single list.

Upvotes: 0

karakfa
karakfa

Reputation: 67467

Your list won't be empty but a list of empty lists, you can do the following to pattern match based on the first sublist (assuming Mat ensures data structure consistency)

rl [] = []
rl ([]:_) = []
rl m = map last m : (rl (map init m))

rl mat
[[3,5,6],[2,4,0],[1,0,0]]

You're missing the second case.

Upvotes: 2

Related Questions