Fork me on GitHub
#clojure
<
2023-11-04
>
stagmoose03:11:17

i am solving problems regarding finding overlapped intervals. for a var intervals sorted by :start, and our targeted range specified by interval-start interval-end i want to find all item inside intervals, that are occluded. this is my current approach, and kinda achieve what i want. but i don't know whether this approach is in the clojure way. any suggestion for improving my method? thanks!

(def intervals [{:start 1 :end 5}
          {:start 6 :end 10}
          {:start 11 :end 12}
          {:start 13 :end 15}
          {:start 17 :end 19}])


  (defn finder [v interval-start interval-end]
    (loop [lidx 0
           lv v
           lfirst nil
           lend nil]
      (let [cur-item (first lv)
            cur-start (:start cur-item)
            cur-end (:end cur-item)]
        (cond (empty? lv) {:first lfirst :end lend}
              (nil? lfirst) (if (> cur-end interval-start)
                              (recur (inc lidx) (rest lv) (assoc cur-item :idx lidx) lend)
                              (recur (inc lidx) (rest lv) lfirst lend))
              :else (if (< cur-start interval-end)
                            (recur (inc lidx) (rest lv) lfirst (assoc cur-item :idx lidx))
                            (recur (inc lidx) (rest lv) lfirst lend))))))

  (finder intervals 9 14)
  ;; => {:first {:start 6, :end 10, :idx 1}, :end {:start 13, :end 15, :idx 3}}
  (let [i (finder intervals 9 14)]
    (subvec intervals (get-in i [:first :idx]) (inc (get-in i [:end :idx]))))
  ;; => [{:start 6, :end 10} {:start 11, :end 12} {:start 13, :end 15}]

stagmoose03:11:33

something like this pic, i want to filter out the yellow items from intervals

Bob B03:11:02

notwithstanding potential weirdness from sub/superset ranges, I think this can be done by dropping from the beginning ones that don't meet the start criteria, and then taking while they do meet the end criteria

stagmoose03:11:12

i kinda feel what you say haha. i should write a overlapped? predicate and just call filter i think i overcomplicated things:sweat_smile:

Bob B04:11:13

I think you want :start interval-start :end or interval-start :end interval-end, right?

stagmoose04:11:53

i want this: [{:start 6, :end 10} {:start 11, :end 12} {:start 13, :end 15}] , from my example

stagmoose04:11:29

idk why i came up with a loop recur method, which is overcomplicated haha.

Bob B04:11:18

hmmm... so maybe it's just remove anything that ends before or starts after the range (assuming :end is always greater than or equal to :start)

stagmoose06:11:43

this is my final solution:

(def intervals [{:start 1 :end 5}
                  {:start 6 :end 10}
                  {:start 11 :end 12}
                  {:start 13 :end 15}
                  {:start 17 :end 19}])

  (defn overlapped?
    [t1 t2 range-start range-end]
    (and (> t2 range-start)
         (< t1 range-end)))

  (defn range-overlapped? [range-start range-end]
    (fn [x]
       (overlapped? (:start x) (:end x)
                    range-start range-end)))

  (filter (range-overlapped? 9 14) intervals)
  ;; => ({:start 6, :end 10} {:start 11, :end 12} {:start 13, :end 15})

thom11:11:52

For what it’s worth there exists a data structure called an interval tree to optimise this sort of search. There is a Clojure library for dealing with such structures: https://github.com/danlentz/com.dean.clojure-interval-tree

🙏 1
roklenarcic23:11:33

generally speaking you can use two sorted maps

roklenarcic23:11:42

one contains the ends and one the starts

evocatus20:11:20

How do you use Clojure CLI tools? Just raw or with helper binaries? I'm interested in the latter, could you recommend any?

Bob B20:11:27

Many dev environments (calva, cursive, cider) have helpers that will at least spin up an nREPL. CLI aliases can also act as helpers, specifying functions to be executed and things of that nature. Babashka can also act in this capacity, especially the tasks functionality and its clojure function: <https://book.babashka.org/#tasks:clojure>, and that's nice because all the coding/configuration is basically still clojure

practicalli-johnny09:11:19

A user config can provide a wide range of additional tools, via aliases or a tool install. e.g. https://practical.li/clojure/clojure-cli/practicalli-config/

👍 1
practicalli-johnny09:11:18

Having worked in mixed programming language teams, I also use make and a Makefile of Clojure CLI tasks to provide a consistent and simplified command line experience (which non-clojurians find more approachable) https://practical.li/engineering-playbook/build-tool/make/

practicalli-johnny09:11:48

Clojure CLI Projects created with Practicalli Project Templates include a Makefile of tasks as a common way to use any project. https://practical.li/clojure/clojure-cli/projects/templates/practicalli/

practicalli-johnny09:11:04

A series of shell scripts could be created in the project, one for each task, e.g bin/repl to run a repl and bin/test to run tests or a test watcher. Shell scripts would be quite simple, one line to define as a shell script, the second line the actual command to run (taking arguments where relevant) Or for a Clojure approach, a babashka script with all the tasks defined in one Clojure file (requires babashka install of course).

practicalli-johnny09:11:29

When working with a team I seek consensus as to what everyone finds most useful and provide that. There is no significant downside in providing several options, but having the same way of interacting across multiple projects does help with onboarding (and wider use of the project)

devn20:11:02

Since make came up I run just these days. Yes it’s a dependency but people I work with generally feel more comfortable tinkering with the justfile than with a make file and for me that’s worth the trade

Noah Bogart20:11:49

I’ve read the source but I’m still a little confused about how exactly for works. Is there any material about how the binds vector is parsed to produce values?

Bob B22:11:40

for is a macro, so it can be macroexpanded, but the resultant code is not necessarily immediately readable - the parsing specifically is mainly just a partition 2 seq-exprs (with handling for the keyword clauses like :when

hiredman23:11:56

if you are interested in implementing something like for, https://ce2144dc-f7c9-4f54-8fb6-7321a4c318db.s3.amazonaws.com/reducers.html has a mini for macro called rfor, missing all of the keyword related functionality, but an example of how to build for on top of map and mapcat

👍 1
hiredman23:11:40

If you have ever seen bind or >>= for monads, for is let implemented in terms of bind (or do notation) for the lazy sequence monad

Noah Bogart23:11:38

Cool, thank you. I was wondering what a non-lazy for or one that produces alternate collections might be like.

hiredman23:11:11

Scala has a for construct that is polymorphic, they use it for composing async tasks like futures

p-himik08:11:58

> a non-lazy for or one that produces alternate collections might be like Maybe you'll like loopr from https://github.com/aphyr/dom-top.

Noah Bogart13:11:48

Loopr is very cool. I am purely interested for my own curiosity lol