swap two elements in an arbitrary collection

[Mark Tomko]

I came up with a way to do it, but I'm sure there's a simpler way.
Here's what I have:

(defn swap [coll i j]
(let [li (min i j) ui (max i j)]
(let [[pre-li post-li] (split-at li coll)]
(let [[post-li-pre-ui post-li-post-ui] (split-at (- ui 1) (rest
post-li))]
(concat
pre-li
(list (nth coll j))
post-li-pre-ui
(list (nth coll i))
(rest post-li-post-ui))))))

Basically, I find the lower index and the upper index. I then find
the elements in the collection that appear before the lower index, and
the elements that appear between the lower index and the upper index,
and the elements that appear after the upper index. I then create a
new list that is the concatenation of these sublists, in order. It's
sort of the definition of swap on an immutable data structure, but it
feels like an awful lot of code.

I considered using subvec:

http://clojure.org/api#toc548

But I didn't want to require that my input collection be a vector, or
convert it to one. This the precursor to my implementing a heap data
structure, as a little toy application.

[Mark Tomko]

Oh, I posted too soon. My implementation has a bug.

[Mark Tomko]

Let's try this again:

(defn swap [coll i j]

(if (= i j) coll

(let [li (min i j) ui (max i j)]
(let [[pre-li post-li] (split-at li coll)]
(let [[post-li-pre-ui post-li-post-ui]

(split-at (- ui 1 li) (rest post-li))]
(concat
pre-li
(list (nth coll ui))
post-li-pre-ui
(list (nth coll li))
(rest post-li-post-ui)))))))

The code is actually even more complicated. I'm sure with a little
more time I could clean it up.

[Christophe Grand]

It's a pet peeve of mine but, please, try hard not to use indices :-)
(or if you need indices pick a better suited data structure)
The code you try to write is hard to write because you are going
against the grain.

If you try to write swap for vectors (which support efficient random
lookup and assoc) it's pretty simple:
(defn swap [v i j]
(-> v (assoc i (v j)) (assoc j (v i))))

But if you want to make it work with any kind of collection and return
a seq (it's the code you have written) it's far less pleasant... and
efficient.

hth

Christophe

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@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+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
>



--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.cgrand.net/ (en)

[Sean Devlin]

Yeah, and this code has the side effect of working on maps

user=>(swap [:a :b :c :d] 0 2)
[:c :b :a :d]

user=>(swap {:a "1" :b "2" :c "3" :d "4"} :a :c)
{:a "3", :b "2", :c "1", :d "4"}

Hmmm... is this worth keeping? Maybe use the name switch instead, to
avoid confusion with swap! (the atom operation).

Thoughts?

[Mark Tomko]

Indeed it does. I still think the array implementation of a heap is
probably worth using, in spite of its use of indexes, but rather than
use a generalized swap implementation to percolate elements up and
down the tree, I'll stick with a vector implementation and keep it all
hidden beneath the implementation details.

I notice you used the '->' macro. Perhaps I'm a little dense, but I
haven't found the documentation for it to be terribly helpful. Do you
have simple, succinct explanation for what it does?

Thanks!
Mark

[Lauri Pesonen]

Hi Mark,

2009/11/13 Mark Tomko <mjt...@gmail.com>:

>
> I notice you used the '->' macro.  Perhaps I'm a little dense, but I
> haven't found the documentation for it to be terribly helpful.  Do you
> have simple, succinct explanation for what it does?

The -> macro calls the given forms with the return value of previous
form inserted as the first argument of the subsequent form. Maybe an
example will help ;-)

(-> v (assoc i (v j)) (assoc j (v i))))

You can think of this as v -> (assoc $ i (v j)) -> (assoc $ j (v i))
where the $ placeholder is replaced by the value from the left of the arrow.

The above example translates to this:

(assoc (assoc v i (v j)) j (v i))

i.e. v is placed into the first assoc form which is then placed into
the second assoc form.

The macro helps you thread a chain of computations together where the
later forms want to use the return value of the preceding form. Very
useful with persistent data structures where you have to thread the
returned data structure through a number of functions.

> Thanks!

I hope this helps. I don't think I did a particularly good job in
explaining how the macro works...

> Mark

--
! Lauri

[Meikel Brandmeyer]

Hi,

Am 13.11.2009 um 17:29 schrieb Lauri Pesonen:

> I hope this helps. I don't think I did a particularly good job in
> explaining how the macro works...

And there is always macroexpand(-1)...

user=> (macroexpand-1 '(-> foo (bar baz)))
(bar foo baz)

Sincerely
Meikel

[Jacek Laskowski]

On Sat, Nov 14, 2009 at 11:59 PM, Meikel Brandmeyer <m...@kotka.de> wrote:

> And there is always macroexpand(-1)...
>
> user=> (macroexpand-1 '(-> foo (bar baz)))
> (bar foo baz)

I'm glad you've pointed it out as I've recently been asking myself how
to expand a macro entirely (including subforms)? I'd prefer knowing
what the final expansion would be for swap.

user=> (macroexpand '(-> v (assoc i (v j)) (assoc j (v i))))
(assoc (clojure.core/-> v (assoc i (v j))) j (v i))

How to expand the macro in the subform above?

Jacek

--
Jacek Laskowski
Notatnik Projektanta Java EE - http://www.JacekLaskowski.pl

[Lauri Pesonen]

2009/11/18 Jacek Laskowski <ja...@laskowski.net.pl>:

>
> user=> (macroexpand '(-> v (assoc i (v j)) (assoc j (v i))))
> (assoc (clojure.core/-> v (assoc i (v j))) j (v i))
>
> How to expand the macro in the subform above?

You can use clojure.walk/macroexpand-all:

(clojure.walk/macroexpand-all '(cond (even? 2) :foo (odd? 2) :bar :else :baz))
(if (even? 2) :foo (if (odd? 2) :bar (if :else :baz nil)))

In slime that's available as slime-macroexpand-all which is bound to
C-c M-m (at least in my system).

> Jacek

--
! Lauri

[John Harrop]

On Thu, Nov 19, 2009 at 4:31 AM, Lauri Pesonen <lauri....@iki.fi> wrote:

(clojure.walk/macroexpand-all '(cond (even? 2) :foo (odd? 2) :bar :else :baz))
(if (even? 2) :foo (if (odd? 2) :bar (if :else :baz nil)))

Eeeuw. Perhaps the cond macro should check if the last condition is self-evaluating and, if it is, optimize appropriately?

[David Brown]

Wouldn't it be better to do this kind of optimization in the compiler
so that more than just cond benefits?

I wonder how practical of an effect it has. The extra check does make
the bytecode bigger, but the JIT might figure out the constant
evaluation. The :else is evaluated at load time, not upon every
evaluation, so it really is just adding a pointer compare and a branch
to the code.

David