Rotating matrices

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Rotating matrices

Thomas Sutton
Dear list,

I'm currently engaged in an attempt to wrap my head around type  
arithmetic. To make sure that I've understood, I plan to write a few  
operations on matrices a la Oleg's Number Parameterised Types. Before  
I get down to it, I've been making sure I know how to implement the  
operations (so that all I need to think about later is the type  
arithmetic).

Today I've been looking at rotating matrices, i.e: taking a column-
wise matrix and making it row-wise and, in the process, swapping the  
dimensions (thus a 3*2 matrix becomes a 2*3 matrix). I've been  
working with lists of lists for simplicity and have come up with:

 > rotate' :: [[a]] -> [[a]]
 > rotate' [] = []
 > rotate' xs = (map (head) xs ):(rotate' $ filter (not . null) $ map  
(tail) xs)

which seems to work just fine. While this solution is adequate (it  
seems to work for infinite structures as well, which is good), I  
originally set out to solve this problem with a fold or a mapAccum of  
some sort (I don't really care if it doesn't work with infinite  
structures). Can anyone suggest a way to write this with a fold (or  
tell me why it isn't a good idea)?

Cheers,
Thomas Sutton
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Rotating matrices

Henning Thielemann

On Thu, 15 Jun 2006, Thomas Sutton wrote:

> Today I've been looking at rotating matrices, i.e: taking a column-wise
> matrix and making it row-wise and, in the process, swapping the dimensions
> (thus a 3*2 matrix becomes a 2*3 matrix).

You mean 'matrix transposition' which is available as Data.List.transpose.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Rotating matrices

Stefan Holdermans
In reply to this post by Thomas Sutton
Thomas,

> > rotate' :: [[a]] -> [[a]]
> > rotate' [] = []
> > rotate' xs = (map (head) xs ):(rotate' $ filter (not . null) $  
> map (tail) xs)
>
> which seems to work just fine. While this solution is adequate (it  
> seems to work for infinite structures as well, which is good), I  
> originally set out to solve this problem with a fold or a mapAccum  
> of some sort (I don't really care if it doesn't work with infinite  
> structures). Can anyone suggest a way to write this with a fold (or  
> tell me why it isn't a good idea)?

   transpose = foldr (zipWith (:)) (repeat [])

HTH,

   Stefan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Rotating matrices

David House
On 15/06/06, Stefan Holdermans <[hidden email]> wrote:
>    transpose = foldr (zipWith (:)) (repeat [])

While one-liners like this are very pretty, it's worth thinking about
how they work:

1. (:) takes an element and a list and prepends that element to the list.
2. zipWith (:) takes a list of elements and a list of lists and
prepends each element to its corresponding list.
3. repeat [] is the infinite list [[], [], [], [], ... ], i.e. the
infinite list of empty lists.
4. transpose, therfore, takes the last list in your list-of-lists
input, then prepends each element of it to the empty list. That is, if
the last list in the input was [x1, x2, ..., xn] then it produces
[[x1], [x2], ..., [xn]].
5. Then this is repeated with the penultimate list in the input (say
its elements are y1..yn), giving [[y1, x1], [y2, x2], ..., [yn, xn]]
6. And so on down the input list.

--
-David House, [hidden email]
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe