algorithm - 用于解决动态规划算法的惯用 Clojure

Question

我决定学习 CLRS 算法简介文本，并选择了打印整齐的问题 here .

我解决了这个问题并提出了一个命令式解决方案，该解决方案可以直接在 Python 中实现，但在 Clojure 中实现起来就不太容易了。

我完全无法将计算矩阵函数从我的解决方案转换为惯用的 Clojure。有什么建议么？这是计算矩阵函数的伪代码:

// n is the dimension of the square matrix.
// c is the matrix.
function compute-matrix(c, n):
    // Traverse through the left-lower triangular matrix and calculate values.
    for i=2 to n:
        for j=i to n:

            // This is our minimum value sentinal.
            // If we encounter a value lower than this, then we store the new
            // lowest value.
            optimal-cost = INF

            // Index in previous column representing the row we want to point to.
            // Whenever we update 't' with a new lowest value, we need to change
            // 'row' to point to the row we're getting that value from.
            row = 0

            // This iterates through each entry in the previous column.
            // Note: we have a lower triangular matrix, meaning data only
            // exists in the left-lower half.
            // We are on column 'i', but because we're in a left-lower triangular
            // matrix, data doesn't start until row (i-1).
            //
            // Similarly, we go to (j-1) because we can't choose a configuration
            // where the previous column ended on a word who's index is larger
            // than the word index this column starts on - the case which occurs
            // when we go for k=(i-1) to greater than (j-1)
            for k=(i-1) to (j-1):

                // When 'j' is equal to 'n', we are at the last cell and we
                // don't care how much whitespace we have.  Just take the total
                // from the previous cell.
                // Note: if 'j' <  'n', then compute normally.

                if (j < n):
                    z = cost(k + 1, j) + c[i-1, k]

                else:
                    z = c[i-1, k]

                if z < optimal-cost:
                    row = k
                    optimal-cost = z

            c[i,j] = optimal-cost
            c[i,j].row = row

此外，我非常感谢对我的 Clojure 源代码的其余部分的反馈，特别是关于它是多么地道的反馈。到目前为止，我是否设法在命令式范例之外充分思考我所编写的 Clojure 代码？在这里:

(ns print-neatly)

;-----------------------------------------------------------------------------
; High-order function which returns a function that computes the cost
; for i and j where i is the starting word index and j is the ending word
; index for the word list "word-list."
;
(defn make-cost [word-list max-length]
  (fn [i j]
    (let [total (reduce + (map #(count %1) (subvec word-list i j)))
          result (- max-length (+ (- j i) total))]
      (if (< result 0)
        nil
        (* result result result)))))

;-----------------------------------------------------------------------------
; initialization function for nxn matrix
;
(defn matrix-construct [n cost-func]
  (let [; Prepend nil to our collection.
        append-empty
          (fn [v]
            (cons nil v))

        ; Like append-empty; append cost-func for first column.
        append-cost
          (fn [v, index]
            (cons (cost-func 0 index) v))

        ; Define an internal helper which calls append-empty N times to create
        ; a new vector consisting of N nil values.
        ; ie., [nil[0] nil[1] nil[2] ... nil[N]]
        construct-empty-vec
          (fn [n]
            (loop [cnt n coll ()]
              (if (neg? cnt)
                (vec coll)
                (recur (dec cnt) (append-empty coll)))))

        ; Construct the base level where each entry is the basic cost function
        ; calculated for the base level. (ie., starting and ending at the
        ; same word)
        construct-base
          (fn [n]
            (loop [cnt n coll ()]
              (if (neg? cnt)
                (vec coll)
                (recur (dec cnt) (append-cost coll cnt)))))]

    ; The main matrix-construct logic, which just creates a new Nx1 vector
    ; via construct-empty-vec, then prepends that to coll.
    ; We end up with a vector of N entries where each entry is a Nx1 vector.
    (loop [cnt n coll ()]
      (cond
        (zero? cnt) (vec coll)
        (= cnt 1) (recur (dec cnt) (cons (construct-base n) coll))
        :else (recur (dec cnt) (cons (construct-empty-vec n) coll))))))

;-----------------------------------------------------------------------------
; Return the value at a given index in a matrix.
;
(defn matrix-lookup [matrix row col]
  (nth (nth matrix row) col))

;-----------------------------------------------------------------------------
; Return a new matrix M with M[row,col] = value
; but otherwise M[i,j] = matrix[i,j]
;
(defn matrix-set [matrix row col value]
  (let [my-row (nth matrix row)
        my-cel (assoc my-row col value)]
    (assoc matrix row my-cel)))

;-----------------------------------------------------------------------------
; Print the matrix out in a nicely formatted fashion.
;
(defn matrix-print [matrix]
  (doseq [j (range (count matrix))]
    (doseq [i (range (count matrix))]
      (let [el (nth (nth matrix i) j)]
        (print (format "%1$8.8s" el)))) ; 1st item max 8 and min 8 chars
    (println)))


;-----------------------------------------------------------------------------
; Main
;-----------------------------------------------------------------------------


;-----------------------------------------------------------------------------
; Grab all arguments from the command line.
;
(let [line-length (Integer. (first *command-line-args*))
      words (vec (rest *command-line-args*))
      cost (make-cost words line-length)
      matrix (matrix-construct (count words) cost)]
  (matrix-print matrix))

编辑:我已经根据给定的反馈更新了我的矩阵构造函数，所以现在它实际上比我的 Python 实现短了一行。

;-----------------------------------------------------------------------------
; Initialization function for nxn matrix
;
(defn matrix-construct [n cost-func]
  (letfn [; Build an n-length vector of nil
          (construct-empty-vec [n]
            (vec (repeat n nil)))

          ; Short-cut so we can use 'map' to apply the cost-func to each
          ; element in a range.
          (my-cost [j]
            (cost-func 0 j))

          ; Construct the base level where each entry is the basic cost function
          ; calculated for the base level. (ie., starting and ending at the
          ; same word)
          (construct-base-vec [n]
            (vec (map my-cost (range n))))]

    ; The main matrix-construct logic, which just creates a new Nx1 vector
    ; via construct-empty-vec, then prepends that to coll.
    ; We end up with a vector of N entries where each entry is a Nx1 vector.
    (let [m (repeat (- n 1) (construct-empty-vec n))]
      (vec (cons (construct-base-vec n) m)))))

Answer 1

1. 与其使用带有 fn 的 let，不如试试 letfn。
2. doseq doseq -> 看起来它作为一种理解可能会更好
3. 你的条件/零？/= 1 带大小写的代码更容易阅读(也更快)。
4. 我的直觉告诉我这里的循环/递归应该是某种 map 调用
5. 我强烈怀疑使用原始数组这会快得多(并且在某些地方可能更干净)
6. 您可能想使用或查看 Incanter 的来源