Instantly share code, notes, and snippets.

# ericnormand/00 Element promotion.md

Created April 5, 2021 19:05
Show Gist options
• Save ericnormand/098143e8cdbecef0faeba92f730b9cba to your computer and use it in GitHub Desktop.

Element promotion

Sometimes you have a list and you want to "promote" one element toward the front of the list. Essentially, you need to swap the element with its immediate predecessor (if it exists). Write a function `promote` that takes a predicate and a list. If the predicate is true, the element should be promoted.

Examples

```(promote even? [1 3 5 6]) ;=> (1 3 6 5)
(promote even? []) ;=> ()
(promote even? [2 1]) ;=> (2 1)
(promote even? [0 2 4 6]) ;=> (0 2 4 6)
(promote even? [0 1 2 3 4 5 6]) ;=> (0 2 1 4 3 6 5)
(promote even? [1 2 2 2 2]) ;=> (2 2 2 2 1)```

Thanks to Enzzo Cavallo for the challenge idea!

### burnall commented Apr 10, 2021

```(defn promote [pred xs]
(->> xs
(reduce (fn [[res tail] x]
(if (pred x)
[(conj res x) tail]
[(apply conj res tail) (list x)]))
[[] nil])
(apply concat)))```

### sim-f commented Apr 11, 2021

```(defn promote [pred ls]
(sequence
(loop [[x y & r :as l] ls
rl []]
(cond
(empty? l) rl
(nil? y) (conj rl x)
(and (pred x)
(pred y)) (recur r
(conj rl x y))
(pred y) (recur
(cons x r)
(conj rl y))
(not (pred y)) (recur
(cons y r)
(conj rl x))))))```

I enjoyed this challenge because it confronts you with the seemly obvious need to keep state while processing the collection. At least for me, an imperative solution seems so straight forward in my mind.

In this gist, I've seems several approaches to overcoming the problem e.g. loop, reduce, stateful transducer, recursion and some other clever ones that I struggle to understand.

I spend an embarrassing amount of time implementing two recursive solutions before settling on a straight forward brute force attempt that keeps state in a map.

```(defn promote [pred coll]
(->> coll
(reduce (fn [{:keys [xs buffer]} x]
(if (pred x)
{:xs (conj xs x) :buffer buffer}
{:xs (conj xs buffer) :buffer x}))
{:xs []})
(#(conj (:xs %) (:buffer %)))
(remove nil?))) ```

I find it... practical!?

-----edit------
@miner you are correct. :-)

I adjusted my solution. I think my solution is less elegant but close to @burnall 's solution.

```(defn promote [pred coll]
(let [f (fn [{:keys [xs buffer]} x]
(if (pred x)
{:xs (conj xs x) :buffer buffer}
{:xs (apply conj xs buffer) :buffer [x]}))]
(as-> (reduce f {:xs []} coll) {:keys [xs buffer]}
(seq (apply conj xs buffer)))))```

### miner commented Apr 15, 2021

You have to be extra careful if you allow nils in your input collection.
`(promote nil? [true nil false true nil nil])`
;=> `[nil true false nil nil true]`

```(defn promote [pred xs]
(->>
(loop [[hd nxt & more :as all] xs acc []]
(cond
(empty? all)
acc
(= 1 (count all))
(conj acc hd)
(or (pred hd) (not (pred nxt)))
(recur (cons nxt more) (conj acc hd))
:else
(recur (cons hd more) (conj acc nxt))))
(apply list)))```