Idiomático Clojure para resolver el algoritmo de programación dinámica

Question

Decidí trabajar a través del texto Introducción a Algoritmos de CLRS, y elegí claramente el problema de impresión here.

Trabajé a través del problema y se me ocurrió una solución imperativa que fue fácil de implementar en Python, pero algo menos en Clojure.

Estoy completamente perplejo al traducir la función de matriz de cálculo de mi solución a Clojure idiomática. ¿Alguna sugerencia? Aquí está el pseudocódigo para la función de cálculo de matriz:

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

Además, me gustaría mucho recibir sus comentarios como en el resto de mi fuente Clojure, específicamente en lo que respecta a la forma idiomática que es. ¿He logrado pensar lo suficiente fuera del paradigma imperativo para el código de Clojure que he escrito hasta ahora? Aquí está:

(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: He actualizado mi función matricial-construcción con la información dada, por lo que ahora es en realidad una línea más corta que mi implementación de 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. En lugar de utilizar dejó con FN en el mismo, tratar letfn.
2. doseq doseq -> parece probable que sea mejor como comprensión
3. ¿Su condición/cero?/= 1 código sería más fácil de leer (y más rápido) con mayúsculas y minúsculas.
4. Mi sentido arácnido me dice que el bucle/se repite aquí debería ser una especie de mapa de llamada en lugar
5. tengo la fuerte sospecha de que esto sería mucho más rápido con matrices primitivas (y posiblemente más limpia en algunos lugares)
6. Usted le gustaría utilizar o consultar la fuente de Incanter

Answer 2

Se pueden simplificar las funciones de matriz de búsqueda y de conjunto de matrices. Puede usar assoc-in y get-in para manipular estructuras asociativas anidadas.

(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 mencionó el uso de matrices primitivas. Si necesita ir en esa dirección, puede comenzar por mirar int-array, aset-int y aget. Mire la documentación clojure.core para obtener más información.

Answer 3

Trepé por la pared y pude pensar de una manera lo suficientemente similar a Clojure para traducir el algoritmo de la matriz de cómputo central en un programa viable.

Es solo una línea más larga que mi implementación de Python, aunque parece estar más densamente escrita. Por supuesto, conceptos como 'mapa' y 'reducir' son funciones de alto nivel que requieren que pongas tu límite de pensamiento.

Creo que esta implementación también corrige un error en mi Python. :)

;----------------------------------------------------------------------------- 
; 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])))) 

Gracias Alex y Jake por sus comentarios. Ambos fueron muy útiles y me han ayudado en mi camino hacia Clojure idiomático.

Answer 4

Mi enfoque general para los programas dinámicos en Clojure no es interferir con la construcción de la matriz de valores directamente, sino más bien utilizar la memorización en conjunto con un combinador de punto fijo. Aquí está mi ejemplo para la informática distancia de edición:

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

La única diferencia con respecto a la solución recursiva ingenua aquí es simplemente para reemplazar las llamadas recursivas con llamadas a fp.

Y entonces crear un punto fijo con memoized:

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

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

y luego llamar con:

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

encuentro memoization más fácil de envolver mi cerebro alrededor de la mutación de tablas.