请问怎么用高阶函数写一个矩阵转置函数

Programming
1

最近学Clojure，但不知道怎么写一个矩阵转置函数，我想Clojure,Emacs Lisp都是Lisp方言，应该有相似的地方，有哪位能用Emacs Lisp写一个函数作为参考吗，用Clojure那是最好的了

2 
(defun my-transpose (matrix)
  (apply #'cl-mapcar #'list matrix))

(my-transpose '((1 2 3) (4 5 6)))
;; => ((1 4) (2 5) (3 6))
2 个赞
3 
(defn transpose [m] 
  (apply mapv vector m))

(let [m [[1 2 3]
         [4 5 6]
         [7 8 9]]]
  (transpose m))
;; => [[1 4 7] [2 5 8] [3 6 9]]

但是直接用vector，可能不是很好，如果你真的要做矩阵的运算的时候。 考虑下这些选项。

4

写一个标准实现：

(mapcar '1+ (3 4 5) ) 
;; => (4 5 6)

(defun transpose (mat)
  (if (eq (car mat) nil)
      '()
      (cons (mapcar 'car mat)
            (transpose (mapcar 'cdr mat)))))

(transpose '((1 2 3)
             (4 5 6)
             (7 8 9)
             (10 11 12)))
;; =>
;; ((1 4 7 10)
;;  (2 5 8 11)
;;  (3 6 9 12))
1 个赞
5

爆栈警告.jpg

6

那个，不自量力地写了一个

(defn transpose [m]
  (loop [temp (map vec m) res []]
    (if (every? empty? temp)
      res
      (recur (map rest temp)
             (conj res (vec (map first temp)))))))
7

(vec (map -> (mapv

8

这个代码的目的只是表达算法本身，而不是为了提供一个经过优化后的算法。

不想爆栈的话，把它改成迭代好了，无非是增加一个累加器而已，但是可读性会降低，并且代码里会出现append或者reverse （然后你肯定还会问我为什么要调用append或reverse。。。最终你将不得不使用mutable）

9

有个函数叫 zip

10

迭代版：

(defun transpose (mat)
  (defun iter (acc rest)
    (if (eq (car rest) nil)
        acc
      (iter (append acc (list (mapcar 'car rest))) (mapcar 'cdr rest)))
    )
  (iter '() mat))

(transpose '((1 2 3)
             (4 5 6)
             (7 8 9)
             (10 11 12)))

;; =>
;; ((1 4 7 10)
;;  (2 5 8 11)
;;  (3 6 9 12))

我们可以明显的看到：

和递归版相比，迭代版必须使用一个辅助函数iter，以及一个累积变量acc。同时，由于list的结合性问题，需要一个append操作，可读性不如递归版来高。

PS：这个append其实也是可以消除的，方法是使用reverse，虽然能提高性能，但可读性会进一步下降。

1 个赞
11

请问你说的zip，在这里又是解决什么问题呢？

12

懒得翻文档了吗？你们根本不需要定义一个叫 transpose 的函数，直接调用 zip 就完事了。

13

像Python里面有，但是Clojure和Elisp里面没有zip的。

14

我知道zip，我的意思是：zip在这里怎么解决爆栈的问题呢？

zip和我提供的算法之间有什么本质区别？

PS：@cirue 提供的 (apply #'cl-mapcar #'list matrix) 本质上就是zip，它同样会爆栈。

15

你@都能@歪来。

cl-mapcar 里面用的是循环，换算成你们纯洁的函数式就是尾递归。不过我们是反复push然后nreverse，所以虽然看似有野蛮的副作用，但他就是不会爆栈，而且暴露给外界的表现还是pure的，气不气？

16

突然好奇一个问题，map 会爆栈吗？apply map 会爆栈吗

17

Elisp的话，dash有个-zip，不过设计有失误，对于两个列表的情况会被zip成cons pair，所以不太好用。

clojure的zip似乎不是解决这个的

20

@glgl-schemer 说的可能是 scheme srfi-1 里的 zip

see SRFI 1: List Library

但是与cl-mapcar类似，zip 同样是一个不定长参数的函数。

你可以这么写：

(zip '(1 2 3) '(4 5 6) '(7 8 9))
>> '((1 4 7) (2 5 8) (3 6 9))

但不能这么写：

(zip '((1 2 3) (4 5 6) (7 8 9)))
>> '(((1 2 3)) ((4 5 6)) ((7 8 9)))

使用scheme里的zip实现transpose，需要使用apply：

(apply zip '((1 2 3) (4 5 6) (7 8 9)))
>> '((1 4 7) (2 5 8) (3 6 9))

Python里也有一个zip，但同样不能直接用，原因和scheme类似。

>>> zip([1,2,3],[4,5,6],[7,8,9])
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

解决方法是使用zip*

>>> zip*([1,2,3],[4,5,6],[7,8,9])
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

但是Python返回的list里的元素是tuple，而不是list，所以还要再做后处理

>>> map(list, zip(*a))
[[1, 4, 7], [2, 5, 8], [3, 6, 9]

Haskell里倒是提供了一个"真正的zip"，它直接被命名为transpose。

21

有点意思

(This is just a spam message)

22

最近我又重新思考了这个问题，有了一些新的理解。

之前的回答有一些错误（已删除）：

  1. map在大部分语言里都是不会爆栈的

    map作为一个primitive操作，大部分语言都会对其做优化。

    一般不会傻乎乎的写成这样：

     ```scheme
 (define (map f list)
   (if (null? list)
       nil
       (cons (f (car list))
         (map f (cdr list)))))
 ```

    这样写，在某些strict language里是会爆栈的，但是在lazy language里不会爆栈。

    然而，即使是strict language，即使你把map写成这个样子，语言的实现仍然可以做成不爆栈，比如：使用 trampolined Interpreter

    换句话说，首先语言的实现得先使用栈，其次才谈的上爆栈的问题。

  2. map不会爆栈 和 map是否可以看成并行函数 无关

    比如：foldr 是不能并行的，但是它仍然可以做成不爆栈的版本。

  3. foldr 操作 和 是否会爆栈 无关

    很多人认为foldr 会爆栈，而foldl不会，这种观点错误（见鬼，我之前也是这么认为）。

    之所以foldr会带给人这样的错觉，是因为在foldr op v这个代码里，op往往能合并值。由于foldr是右结合，它必须不断求值 list 直到 nil 之后才能开始 reduce，这导致了大量临时变量被 push 到栈上（相比foldl是左结合，每一次递归它都可以进行一次合并，因此不会有额外的内存消耗）

    然而，它们均与爆栈无关。

    这里仍然包含两层意思：

    (1) 首先你的语言实现得使用栈

    (2) 即使语言实现使用了栈，foldr 的实现仍然可以做成不爆栈的版本。比如：foldr 函数可以通过两次应用foldl实现：先 reverse，再foldl（或者，高级一点，也可以通过compose f函数的部分应用实现）

换句话说，我在4楼写的那个函数，确实是有可能爆栈，因为elisp是strict language，并且语言的实现使用了栈，从这个角度讲 @cireu 说的并没有错。

补充一下：

这里所说的“爆栈”取自于5楼和16楼的说法，这不是一个精确的词汇。

一般有两种理解：

(1) 如果op能合并值，尽早合并值，避免不必要的内存消耗。

(2) 如果语言的实现使用了栈结构，避免临时内存被分配在栈上。

这两种理解在不同的语言上有着不同的操作手法。

以上主要是针对(2)来说的。

对于(1)

在strict language里，如果op能合并值，则foldl能尽早合并值。

在lazy language里（如：Haskell），同样情况下直接使用foldl是不行的，注意：我上面有提到“尽早”，所以你必须使用strict版本的foldl，即foldl'。

在lazy language里，如果op不会合并值，则foldr能够最大程度的利用laziness，而foldl不行。

当然，这些都与具体数据结构和算法有关，比如：list本身是右结合，然后你的算法本身也要求右结合，在这种情况下，即便op可以合并，你也只能使用foldr。

对于(2)

首先得确保你的语言实现使用了栈，如果语言的实现没有使用栈，则根本没必要考虑(2)。

比如：你想在Haskell里实现一个map，你应该直接这么写：

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x : xs) = f x : map f xs

不要自作聪明把result累积在参数上写成尾递归，这样反而更糟。。。

其次，如果语言的实现使用了栈，那么尽量使用语言和库提供的函数，而不要自己写。 因为这些语言和库提供的函数已经考虑到了(2)中的优化问题。

1 个赞