CODEWITHSUNDEEP
clojure
jbrown
jbrown

Reputation: 7996

Is there a better way to write this code that inserts an element into a sorted list in clojure?

I'm working on exercise 7 on https://iloveponies.github.io/120-hour-epic-sax-marathon/one-function-to-rule-them-all.html. I've got a solution, but because the expected output is a list, I've had to add a 'reverse' to some of my outputs. This seems a bit hacky.

Here's my code:

(defn insert [sorted-seq n]
  (loop [output ()
         my-seq sorted-seq]
    (cond 
     (nil? (first my-seq)) 
       (conj output n)
     (nil? (first (rest my-seq))) 
       (reverse (conj output (first my-seq) n))
     :else
      (if (> (first (rest my-seq)) n (first my-seq))
        (reverse (apply conj output (first my-seq) n (rest my-seq)))
        (recur (conj output (first my-seq)) (rest my-seq))))))

(insert [] 2)      ;=> (2)
(insert [1 3 4] 2) ;=> (1 2 3 4)
(insert [1] 2)     ;=> (1 2)

Is there a better way of writing this that will be more efficient, and not require reversing the outputs? Also, the first 2 conditions seem clunky. Is there a better way?

Upvotes: 3

Views: 364

Answers (3)

Thumbnail
Thumbnail

Reputation: 13483

You can do this quite simply with a list provided you are prepared to employ proper recursion:

(defn insert [ss n]
  (if (empty? ss)
    (list n)
    (let [[x & xs] ss]
      (if (< n x)
        (cons n ss)
        (cons x (insert xs n))))))
  • Wrap the body in a lazy-seq if you want it to work on long sequences without blowing the stack.
  • It's still going to be much slower than A. Webb's solution.

Upvotes: 0

soulcheck
soulcheck

Reputation: 36777

@A.Webb's solution is the one you're looking for, but leaving this for the future visitors.

I think you overcomplicated the problem slightly.

The general idea is this:

  1. Find the site where you need to insert the element.
  2. Split the sequence in two at that point.
  3. Concatenate the first resulting sequence, the element, the second resulting sequence.

You can combine 1 and 2 using split-with, which splits the sequence in two parts: one where a predicate is true, and the other where it is false.

So, speaking clojure:

(defn insert [coll n]
   (let [[l r] (split-with #(< % n) coll)]
       (concat l [n] r))

Upvotes: 3

A. Webb
A. Webb

Reputation: 26446

I think the point of the exercise is to work with recursion, not necessarily to produce the most idiomatic code. You can avoid the reversing by using a data structure that does conj to the right, a vector.

(defn insert [sorted-seq n]
  (loop [s sorted-seq, a []]
    (cond 
      (empty? s)       (conj a n)
      (< (first s) n)  (recur (rest s) (conj a (first s)))
      :else            (apply conj a n s))))

Upvotes: 2

Related Questions