CODEWITHSUNDEEP
algorithmclojurefunctional-programmingtail-recursion
conceptacid
conceptacid

Reputation: 338

List processing in clojure, tail recursion needed

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.

Upvotes: 2

Views: 232

Answers (2)

cgrand
cgrand

Reputation: 7949

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.

Upvotes: 5

Amith George
Amith George

Reputation: 5916

In my experience making something tail recursive involves passing as arguments all local state. Looking at the algo, it looks like already processed range items is the local state. ie, final result = (ranges ignored + merged-range + ranges not required to be considered).

Consider the following version, it explicitly passes a seq of already processed items. 

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

My version accepts a vector and returns a vector. You could modify the relevant code to make it accept a list and return a list.

As for is there a better algorithm, I don't know. I have simply converted your algo to be tail recursive.

Upvotes: 2

Related Questions