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

最近学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似乎不是解决这个的

@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

有点意思

(This is just a spam message)

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

之前的回答有一些错误(已删除):

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