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

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

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

(my-transpose '((1 2 3) (4 5 6)))
;; => ((1 4) (2 5) (3 6))
2赞
(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,可能不是很好,如果你真的要做矩阵的运算的时候。 考虑下这些选项。

写一个标准实现:

(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赞

爆栈警告.jpg

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

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

(vec (map -> (mapv

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

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

有个函数叫 zip

迭代版:

(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赞

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

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

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

我知道zip,我的意思是:zip在这里怎么解决爆栈的问题呢?

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

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

你@都能@歪来。

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

突然好奇一个问题,map 会爆栈吗?apply map 会爆栈吗

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

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

理论上说,map是不会爆栈的,map本质上是一个并行函数。

但是一般的map实现是会爆栈的,它不是尾递归。

transpose之所以会爆栈,是因为它本质上是一个foldr的操作,不是尾递归,中间临时变量需要push到栈上。

是的,用mapcar或者zip,底层确实可以做不少优化,甚至可以做到并行计算。

因为mapcar和zip从语义上讲每一次计算并不依赖于先前的值,这可能也是为什么函数式语言会提供这类原始操作的原因(反正底层用mutable也好,用并行也好,对上层不可见就是了)

不过如果要使用矩阵的话,还是建议直接使用矩阵库。

我这里只是提供一个标准做法而已。