clojure中的列表处理，需要尾递归

Question

给定间隔的排序列表，例如 (def lst (list [7 10] [32 35]))

我需要实现一个向列表添加新间隔的函数。如果新区间与列表中的任何区间相邻，则应合并它们：

(= (add-range [1 3] lst)   (list [1 3] [7 10] [32 35]))  ;; prepend left
(= (add-range [1 6] lst)   (list [1 10] [32 35]))        ;; merge left
(= (add-range [11 20] lst) (list [7 20] [32 35]))        ;; merge right
(= (add-range [11 31] lst) (list [7 35]))                ;; merge left and right

这是我的实现：

(defn add-range
  [range range-list]
  (if (empty? range-list)
    (list range)
    (let
      [lo (first range)
       hi (second range)
       head (first range-list)
       head-lo (dec (first head))
       head-hi (inc (second head))]
        (if (< hi head-lo)
          (cons range range-list)
          (if (= hi head-lo)
            (cons [lo (second head)] (rest range-list))
            (if (= lo head-hi)
              (recur [(first head) hi] (rest range-list))
              (cons head (add-range range (rest range-list)))))))))

它可以工作并且看起来也很优雅，但是最后一行包含一个递归调用 add-range，不能用 recur 替换，因为它不是最后一次调用。我计划在我的应用程序中使用长范围列表，我不想破坏堆栈。

如何使用尾递归重写？有没有另一种方法来解决这个问题？可能是惰性序列？

更新实际上不需要排序列表。这可以是一个集合，甚至是一个未排序的列表，但一次完成它会非常好。

Answer 1

根据我的经验，制作尾递归涉及将所有本地状态作为参数传递。查看算法，看起来已经处理的范围项是本地状态。即，final result = (ranges ignored + merged-range + ranges not required to be considered).

考虑以下版本，它明确传递了一系列已处理的项目。

(defn add-range
  [range-obj ranges]
  (loop [processed []
         range-obj range-obj
         remaining (list* ranges)]
    (if (empty? remaining)
      (conj processed range-obj)
      (let [[lo hi] range-obj
            [h-lo h-hi :as head] (first remaining)
            upper-merge-threshold (dec h-lo)
            lower-merge-threshold (inc h-hi)]
        (cond 
          (< hi upper-merge-threshold) (into processed 
                                             (conj remaining range-obj))
          (= hi upper-merge-threshold) (into processed 
                                             (conj (rest remaining) [lo h-hi]))
          (= lo lower-merge-threshold) (recur processed
                                              [h-lo hi]
                                              (rest remaining))
          :else (recur (conj processed head)
                       range-obj
                       (rest remaining)))))))

我的版本接受向量，return接受向量。您可以修改相关代码以使其接受列表和 return 列表。

至于有没有更好的算法，不知道。我只是将您的算法转换为尾递归。

Answer 2

使用排序集，您可以将其实现为：

;; first the constructor
(defn ranges [& rs]
  (apply sorted-set-by
    (fn [[from-a to-a] [from-b to-b]]
      (< to-a (dec from-b))) rs))

;; then add-range itself
(defn add-range [ranges [from to :as r]]
  (let [rs (subseq ranges <= [from from] <= [to to])
        ranges (reduce disj ranges rs)]
    (conj ranges
      (let [[from'] (or (first rs) r)
            [_ to'] (or (last rs) r)]
        [(min from from') (max to to')]))))

让我们试试你的测试：

=> (def lst (ranges [7 10] [32 35]))
#'user/lst
=> (add-range lst [1 3])
#{[1 3] [7 10] [32 35]}
=> (add-range lst [1 6])
#{[7 10] [32 35]}
=> (add-range lst [11 20])
#{[7 20] [32 35]}
=> (add-range lst [11 35])
#{[7 35]}

附录 #1：add-range 是 O((m + 1) log n)，其中 n 是范围集的大小，m 是合并间隔的数量。

clojure中的列表处理，需要尾递归

List processing in clojure, tail recursion needed

algorithm

clojure

functional-programming

tail-recursion