Topic: （sort） lst or maybe Transpose

[Q1241274614]

(setq lst
(list
(list a1 a2 a3 a4 a5 )
(list b1 b2 b3 b4 b5 )
(list c1 c2 c3 c4 c5 )
(list d1 d2 d3 d4 d5 )
)
)

Result:
(list
(list a1 b1 c1 d1)
(list a2 b2 c2 d2)
(list a3 b3 c3 d3)
(list a4 b4 c4 d4)
(list a5 b5 c5 d5)
)

[Kerry]

Are the list values meant to be strings?.

Are you trying to do a matrix translation or a sort ?
... seems to be just a translation to me.

Is there a question or statement associated with your post?

[Q1241274614]

strings

[irneb]

strings

So do you mean you've got the lists like this:

Code - Auto/Visual Lisp: [Select]

1. (setq lst (list
2.             (list "a1" "a2" "a3" "a4" "a5")
3.             (list "b1" "b2" "b3" "b4" "b5")
4.             (list "c1" "c2" "c3" "c4" "c5")
5.             (list "d1" "d2" "d3" "d4" "d5")))

In that case it would be strings yes.

What you've shown is using symbols to place their values inside the list(s). There's no way for us to see what's inside those symbols and how they compare to each other to see how the "sorting" should happen. E.g. if I run your code as is I simply get a list of nil values:

Code: [Select]

_$ (setq lst
       (list
         (list a1 a2 a3 a4 a5)
         (list b1 b2 b3 b4 b5)
         (list c1 c2 c3 c4 c5)
         (list d1 d2 d3 d4 d5)
         )
      )
((nil nil nil nil nil) (nil nil nil nil nil) (nil nil nil nil nil) (nil nil nil nil nil))
If strings, then as per Kerry's answer: Matrix Transpose.

The oldest sample of a Transpose function I can find is this (1996): http://autocad.xarch.at/lisp/transpose.002.html
It works very well:

Code - Auto/Visual Lisp: [Select]

1. (defun transpose-matrix (lst)
2.   (apply 'mapcar (cons 'list lst)))

Code: [Select]

_$ (setq lst (list
            (list "a1" "a2" "a3" "a4" "a5")
            (list "b1" "b2" "b3" "b4" "b5")
            (list "c1" "c2" "c3" "c4" "c5")
            (list "d1" "d2" "d3" "d4" "d5")))
(("a1" "a2" "a3" "a4" "a5") ("b1" "b2" "b3" "b4" "b5") ("c1" "c2" "c3" "c4" "c5") ("d1" "d2" "d3" "d4" "d5"))
_$ (transpose-matrix lst)
(("a1" "b1" "c1" "d1") ("a2" "b2" "c2" "d2") ("a3" "b3" "c3" "d3") ("a4" "b4" "c4" "d4") ("a5" "b5" "c5" "d5"))

[Kerry]

or, starting from scratch, something like

Code - Auto/Visual Lisp: [Select]

1. (defun doit     (lst / result lst col-index _vertical-list)
2.   (defun _vertical-list (l i) (mapcar '(lambda (sub) (nth i sub)) l))
3.   (setq col-index 0)
4.   (foreach column (car lst)
5.         (setq result    (cons (_vertical-list lst col-index) result)
6.                   col-index     (1+ col-index)
7.         )
8.   )
9.   (reverse result)
10. )
11.  
12.  
13.  
14. (setq lst (list (list "a1" "a2" "a3" "a4" "a5")
15.                                 (list "b1" "b2" "b3" "b4" "b5")
16.                                 (list "c1" "c2" "c3" "c4" "c5")
17.                                 (list "d1" "d2" "d3" "d4" "d5")
18.                   )
19. )
20.  
21. (doit lst)
22.  
23.  

(("a1" "b1" "c1" "d1") ("a2" "b2" "c2" "d2") ("a3" "b3" "c3" "d3") ("a4" "b4" "c4" "d4") ("a5" "b5" "c5" "d5"))

A bit ugly and slow, but cheap

[Kerry]

If strings, then as per Kerry's answer: Matrix Transpose.

The oldest sample of a Transpose function I can find is this (1996): http://autocad.xarch.at/lisp/transpose.002.html
It works very well:

Code - Auto/Visual Lisp: [Select]

1. (defun transpose-matrix (lst)
2.   (apply 'mapcar (cons 'list lst)))
3.  

I'm rusty irne,   forgot all about that gem.

[irneb]

I'm rusty irne,   forgot all about that gem.

Yes, I forgot about it until a few years ago when I saw it again!

At first it seems to be "magic" ... but if you work out what it does, you realize this is probably the most awesome sample of functional programming!

[gile]

I'm rusty irne,   forgot all about that gem.

Yes, I forgot about it until a few years ago when I saw it again!

At first it seems to be "magic" ... but if you work out what it does, you realize this is probably the most awesome sample of functional programming!

1+

[irneb]

1+

Strange, I tried looking for similar code in other languages (even other functional stuff) but it seems Lisp simply lends itself to this function.

E.g. compare F#'s implementation here: http://rosettacode.org/wiki/Matrix_transposition

Not to mention, the Linq ideas going on here: http://stackoverflow.com/questions/312103/can-you-use-linq-or-lambdas-to-perform-matrix-operations

They all do much the same, though not as "simply". IMO clojure's method is simply sublimely free of clutter:

Code - Clojure: [Select]

1. (apply map list matrix)

Same with Scheme: http://rosettacode.org/wiki/Matrix_transposition#Scheme

[gile]

Strange, I tried looking for similar code in other languages (even other functional stuff) but it seems Lisp simply lends itself to this function.

I think this is due to the nature of LISP which uses the same structure (dynamically typed linked list) for data collections and function applications. This provides functions such as apply and use the mapcar with any number of lists.

With F#, which is statically typed, the implementation of a transpose function depends on the data structure used to represent the matrix.

Using a linked list as with LISP:

Code - F#: [Select]

1. let m1 = [[1.; 2.]; [3.; 4.]; [5.; 6.]]
2.  
3. let rec transpose1 = function
4.     | (_::_)::_ as m -> List.map List.head m :: transpose1 (List.map List.tail m)
5.     | _ -> []

Which LISP equivalent is:

Code - Auto/Visual Lisp: [Select]

1. (setq m1 '((1. 2.) (3. 4.) (5. 6.)))
2.  
3. (defun transpose (m)
4.   (if (and m (car m))
5.     (cons (mapcar 'car m) (transpose (mapcar 'cdr m)))
6.   )
7. )

Using a 2 dimensional array (as in the link you posted)

Code - F#: [Select]

1. let m2 = array2D [[1.; 2.]; [3.; 4.]; [5.; 6.]]
2.  
3. let transpose2 m =
4.     Array2D.init (Array2D.length2 m) (Array2D.length1 m) (fun i j -> m.[j, i])

Or simply using the Microsoft.FSharp.Math.Matrix<float> type (from the PowerPack library) which provides a Transpose property

Code - F#: [Select]

1. let m3 = matrix [[1.; 2.]; [3.; 4.]; [5.; 6.]]
2.  
3. m3.Transpose

[irneb]

Nice examples Gile!

Using a linked list as with LISP:

Code - F#: [Select]

1. let m1 = [[1.; 2.]; [3.; 4.]; [5.; 6.]]
2.  
3. let rec transpose1 = function
4.     | (_::_)::_ as m -> List.map List.head m :: transpose1 (List.map List.tail m)
5.     | _ -> []

Not sure, I'm no F# boffin ... but is this tail-recursively optimized?

[gile]

No the upper example is not tail recursive. The last call is 'cons' ( :: ).

Here's a tail recursive version using an auxiliary function:

Code - F#: [Select]

1. let transpose m =
2.     let rec loop acc = function
3.         | (_::_)::_ as m -> loop (List.map List.head m :: acc) (List.map List.tail m)
4.         | _ -> List.rev acc
5.     loop [] m