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

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

;; 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 是合并区间的数量。