Clojure 从递归重构代码

Question

我有以下代码可以产生正确的结果：

(ns scratch.core
  (require [clojure.string :as str :only (split-lines join split)]))
(defn numberify [str]
  (vec (map read-string (str/split str #" "))))
(defn process [acc sticks]
  (let [smallest (apply min sticks)
        cuts (filter #(> % 0) (map #(- % smallest) sticks))]
    (if (empty? cuts)
      acc
      (process (conj acc (count cuts)) cuts))))
(defn print-result [[x & xs]]
  (prn x)
  (if (seq xs)
    (recur xs)))
(let [input "8n1 2 3 4 3 3 2 1"
      lines (str/split-lines input)
      length (read-string (first lines))
      inputs (first (rest lines))]
  (print-result (process [length] (numberify inputs))))

上面的 process 函数递归调用自身，直到序列sticks empty?。

我很想知道我是否可以使用类似take-while或其他技术来使代码更简洁？

如果我需要在序列上做一些工作，直到它为空，那么我使用递归，但我忍不住想有更好的方法。

Answer 1

你的核心问题可以描述为

1. 如果棍数为零，则停止
2. 累积棍数
3. 从每根棍子中减去最小的棍子
4. 过滤正棒
5. 返回到 1。

将最小的子问题确定为步骤 3 和 4，并在其周围放置一个框

(defn cuts [sticks]
  (let [smallest (apply min sticks)]
    (filter pos? (map #(- % smallest) sticks))))

请注意，sticks在步骤 5 和 3 之间没有变化，cuts是一个 fn sticks->sticks，因此请使用迭代在其周围放置一个框：

(defn process [sticks]
  (->> (iterate cuts sticks)
;; ----- 8< -------------------

这给出了sticks、(cuts sticks)、(cuts (cuts sticks))等的无限序列

合并步骤 1 和 2

(defn process [sticks]
  (->> (iterate cuts sticks)
       (map count)         ;; count each sticks
       (take-while pos?))) ;; accumulate while counts are positive
(process [1 2 3 4 3 3 2 1])
;-> (8 6 4 1)

在幕后，这个算法与您发布的算法几乎没有区别，因为惰性 seqs 是递归的延迟实现。不过，它更惯用，更模块化，使用take-while进行取消，这增加了其表现力。此外，它不需要一个人通过初始计数，如果棍子是空的，它会做正确的事情。我希望这是你要找的。

Answer 2

我认为编写代码的方式是一种非常简洁的方式。当然，在《小图式》中有很多例子遵循这种减少/递归的格式。

为了替换递归，我通常会寻找一种涉及使用高阶函数的解决方案，在本例中为 reduce .它将每次迭代的min调用替换为开始时的单个排序。

(defn process [sticks]
  (drop-last (reduce (fn [a i]
                       (let [n (- (last a) (count i))]
                         (conj a n)))
                     [(count sticks)]
                     (partition-by identity (sort sticks)))))
(process [1 2 3 4 3 3 2 1])
=> (8 6 4 1)

我更改了算法以拟合减少，方法是在排序后对相同的数字进行分组，然后对每个组进行计数并减小计数大小。