Я решил проработать текст CLRS Introduction to Algorithms и аккуратно выбрал проблему печати herher.
Я проработал проблему и нашел императивное решение, которое было просто реализовать на Python, но несколько сложнее в Clojure.
Я совершенно запутался в переводе функции вычислений-матрицы из моего решения в идиоматический Clojure. Какие-либо предложения? Вот псевдокод для функции calculate-matrix:
// 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))
EDIT: я обновил свою функцию построения матрицы с учетом отзывов, так что теперь она фактически на одну строку короче, чем моя реализация 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)))))
