Idiomatic Clojure for solving dynamic programming algorithm

Question

I decided to work through the CLRS Introduction to Algorithms text, and picked the printing neatly problem here.

I worked through the problem and came up with an imperative solution which was straightforward to implement in Python, but somewhat less so in Clojure.

I'm completely stumped on translating the compute-matrix function from my solution into idiomatic Clojure. Any suggestions? Here is the pseudocode for the compute-matrix function:

// 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

Additionally, I would very much appreciate feedback on the rest of my Clojure source, specifically with regards to how idiomatic it is. Have I managed to think sufficiently outside of the imperative paradigm for the Clojure code I've written thus far? Here it is:

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

EDIT: I've updated my matrix-construct function with the feedback given, so now it's actually one line shorter than my Python implementation.

;-----------------------------------------------------------------------------
; 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. Instead of using let with fn's in it, try letfn.
2. doseq doseq -> looks like it would likely be better as a for comprehension
3. Your cond / zero? / = 1 code would be easier to read (and faster) with case.
4. My spidey-sense tells me that the loop/recurs here should be some kind of map call instead
5. I strongly suspect that this would be far faster with primitive arrays (and possibly cleaner in some places)
6. You might like to use or look at the source for Incanter

Answer 2

Your matrix-lookup and matrix-set functions can be simplified. You can use assoc-in and get-in for manipulating nested associative structures.

(defn matrix-lookup [matrix row col]
 (get-in matrix [row col]))

(defn matrix-set [matrix row col value]
  (assoc-in matrix [row col] value))

Alex Miller mentioned using primitive arrays. If you end up needing to go that direction you can start by looking at int-array, aset-int, and aget. Look at the clojure.core documentation to find out more.

Answer 3

I climbed the wall and was able to think in a sufficiently Clojure-like way to translate the core compute-matrix algorithm into a workable program.

It's just one line longer than my Python implementation, although it appears to be more densely written. For sure, concepts like 'map' and 'reduce' are higher-level functions that require you to put your thinking cap on.

I believe this implementation also fixes a bug in my Python one. :)

;-----------------------------------------------------------------------------
; Compute all table entries so we can compute the optimal cost path and
; reconstruct an optimal solution.
;
(defn compute-matrix [m cost]
  (letfn [; Return a function that computes 'cost(k+1,j) + c[i-1,k]'
          ; OR just 'c[i-1,k]' if we're on the last row.
          (make-min-func [matrix i j]
            (if (< j (- (count matrix) 1))
              (fn [k]
                (+ (cost (+ k 1) j) (get-in matrix [(- i 1) k])))
              (fn [k]
                (get-in matrix [(- i 1) k]))))

          ; Find the minimum cost for the new cost: 'cost(k+1,j)'
          ; added to the previous entry's cost: 'c[i-1,k]'
          (min-cost [matrix i j]
            (let [this-cost (make-min-func matrix i j)
                  rang (range (- i 1) (- j 1))
                  cnt (if (= rang ()) (list (- i 1)) rang)]
              (apply min (map this-cost cnt))))

          ; Takes a matrix and indices, returns an updated matrix.
          (combine [matrix indices]
            (let [i (first indices)
                  j (nth indices 1)
                  opt (min-cost matrix i j)]
              (assoc-in matrix [i j] opt)))]

    (reduce combine m
        (for [i (range 1 (count m)) j (range i (count m))] [i j]))))

Thank you Alex and Jake for your comments. They were both very helpful and have helped me on my way toward idiomatic Clojure.

Answer 4

My general approach to dynamic programs in Clojure is not to mess with construction of the matrix of values directly, but rather to use memorization in tandem with a fixed point combinator. Here's my example for computing edit distance:

(defn edit-distance-fp
  "Computes the edit distance between two collections"
  [fp coll1 coll2]
  (cond
      (and (empty? coll1) (empty? coll2)) 0
      (empty? coll2) (count coll1)
      (empty? coll1) (count coll2)
      :else (let [x1 (first coll1)
                  xs (rest coll1)
                  y1 (first coll2)
                  ys (rest coll2)]
                 (min
                  (+ (fp fp xs ys) (if (= x1 y1) 0 1))
                  (inc (fp fp coll1 ys))
                  (inc (fp fp xs coll2))))))

The only difference from the naive recursive solution here is simply to replace the recursive calls with calls to fp.

And then I create a memoized fixed point with:

(defn memoize-recursive [f] (let [g (memoize f)] (partial g g)))

(defn mk-edit-distance [] (memoize-recursive edit-distance-fp))

And then call it with:

> (time ((mk-edit-distance) 
  "the quick brown fox jumped over the tawdry moon" 
  "quickly brown foxes moonjumped the tawdriness"))
"Elapsed time: 45.758 msecs"
23

I find memoization easier to wrap my brain around than mutating tables.