在clojure中进行列表处理，需要尾递归(List processing in clojure, tail recursion needed)

给定一个有序的间隔列表，例如(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替换，因为它不是最后一次调用。我打算在我的应用程序中有很长的范围列表，我不想炸掉堆栈。

如何使用尾递归重写它？还有另一种解决问题的方法吗？懒序列可能？

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

Given a sorted list of intervals, e.g. (def lst (list [7 10] [32 35]))

I need to implement a function that adds a new interval to the list. If the new interval is adjacent to any of those from the list, they should be merged:

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

This is my implementation:

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

It works and looks quite elegant too, but the last line contains a recursive call add-range which can not be replaced with recur because it is not the last call. I'm planning to have long range lists in my application and I don't want to blow up the stack.

How this can be rewritten using the tail recursion? Is there another approach to solve the problem? Lazy sequences maybe?

UPDATE The sorted list is actually not required. This can be a set or even an unsorted list, but it would be really nice to do it in a single pass.

最满意答案

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

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

Using a sorted set you can implement it as:

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

Let's try your tests:

=> (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]}

Addendum #1: add-range is O((m + 1) log n) where n is the size of the ranges set and m the number of merged intervals.

更多推荐