I'm having a conceptual problem, thinking functionally, and I was
hoping the fine Clojurians could take a peek.
Boiled down, I need to do a combination of map and reduce on a
collection. My "walker" needs to look at pairs along the collection,
but then sort of "inject" new values and restart when necessary.
Since I don't know of a "more general" über-HOF that will do what I
want, I tried to write my own function. It's not tail recursive,
which is a big problem. So I need help. But let me back up, and
start where it will make sense.
I need to represent, in their most-reduced form, collections of half-
closed intervals on Z (integers). So an interval might be [2, 4)
which means 2 and 3 are elements, but 1 and 4 are not. Since the
collections of intervals must be "reduced", I can't have (using
chicken lips as vector for clarity):
< [2, 4) [4, 8) >
Note that all elements between 2 (inclusive) and 8 (exclusive) satisfy
this collection, so the two intervals must be merged. This collection
should be:
< [2, 8) >
Similarly, all partially or completely overlapping intervals must be
merged. See how this could be like a map/reduce function? Sort the
collection. Look at the first two elements; if they can merge, merge
them and then restart with the newly merged interval at the head. If
they can't be merged, release the first into the result, and consider
the second and third, etc.
So I'm representing spans (ranges) of integers with a map, like so:
(defn make-span
"Makes a non-zero-width span of integer value."
([start end]
{:pre [(integer? start) (integer? end) (< start end)]}
{:start (min start end) :end (max start end)})
([singleton]
(make-span singleton (inc singleton))))
I can tell if these intervals are in some way overlapping or perfectly
adjacent like this:
(defn overlap?
"Are these two spans partially or totally
overlapping or perfectly adjacent?"
[s1 s2]
(not (or (pos? (- (:start s2) (:end s1)))
(pos? (- (:start s1) (:end s2))))))
Straightforward so far. Now, given a *sorted* collection of spans, I
should be able to reduce the collection to its canonical form by
looking at first and second, merging their span if they overlap, and
recurring as necessary:
(defn merge-spans [spans]
(if (empty? spans) spans
(let [x (first spans)
ys (rest spans)]
(if (empty? ys) spans
(let [y (first ys)
zs (rest ys)]
(if (overlap? x y) ; this is the merge
(let [xy (make-span (min (:start x) (:start y))
(max (:end x) (:end y)))]
(recur (into [xy] zs)))
; this is the recursive
problem
(into [x] (merge-spans ys))))))))
Let's try some demo code:
(defn safe-merge []
(let [s1 (make-span 1)
s2 (make-span 2)
s3 (make-span 9)
demo-spans (sort-by :start [s2 s3 s1])] ; we sort by :start
(merge-spans demo-spans)))
(defn unsafe-merge []
(let [bad-spans (sort-by :start (map make-span (range 0 100000 2)))]
(count (merge-spans bad-spans))))
user=> (safe-merge)
[{:start 1, :end 3} {:start 9, :end 10}] ; perfect!
user=> (unsafe-merge)
StackOverflowError clojure.lang.PersistentArrayMap.equalKey
(PersistentArrayMap.java:201)
OK, this is a really long post because of all the code, but thanks for
reading this far. Can anyone suggest a way for me to either A) get
rid of the ordinary recursion in merge-spans, or B) approach this
problem from a different angle I'm not thinking about?
Thanks in advance everybody…
Mike
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
