> On Wed, Dec 29, 2010 at 8:13 PM, Mark Engelberg
>> However, it should be pointed out that even this latest version
>> doesn't share all the performance characteristics of the classic
>> functional insertion sort given at the Htdp link. Specifically, one
>> of the (few) great things about insertion sort is that it is blazingly
>> fast on input lists that are already sorted, or nearly sorted. As a
>> challenge (to you or Andreas, or anyone who is interested in this
>> thread), figure out why the original insertion sort works so quickly
>> on sorted lists, why the above code does not, and then try to
>> duplicate that performance characteristic with an insertion sort
>> algorithm in Clojure.
So here's the answer to the puzzle I posed earlier, for anyone who's
still following along. The reason the other implementation is fast on
already sorted lists is because the insert function only needs to
traverse as far as the insertion point, and then can share the
structure of the remainder of the list. This is handled transparently
by the recursive process, with the stack accumulating the conses that
need to be done. To simulate this in Clojure, you need some way to
manually accumulate the list of things you traversed on the way to the
insertion point, and then non-lazily stick them on the front of the
remainder of the list.
Here's one way to do that:
; (append l1 l2) is equivalent to a non-lazy (concat (reverse l1) l2)
(defn append [l1 l2]
(loop [l1 (seq l1) result l2]
(if l1
(recur (next l1) (cons (first l1) result))
result)))
(defn insert [n alon]
(loop [alon (seq alon), traversed nil]
(cond
(nil? alon) (append traversed (list n))
(<= n (first alon)) (append traversed (cons n alon))
(> n (first alon)) (recur (next alon) (conj traversed (first alon))))))
Then, do the actual insertion sort either using Ken's reduce technique
(on the reverse of the list if stability is desired), or manually
implementing the equivalent pattern:
(defn isort [alon]
(loop [alon (seq (reverse alon)), sorted nil]
(if alon
(recur (next alon) (insert (first alon) sorted))
sorted)))
This is really fast on sorted lists and as fast as any of the other
versions we've batted around on random data. I believe this is the
closest Clojurian equivalent to the Racket version. Sadly, it loses
much of its simplicity. I have students write insertion sort in
Racket after only a dozen or so lessons, but writing the equivalent in
Clojure requires some significant machinations. (If anyone sees a
simpler way to accomplish the same thing in Clojure, please let me
know!)
Still, I hope this helps explain how to transform stack-consuming
patterns into Clojure's loop/recur construct. It can be a bit of
work, but it's necessary in Clojure to implement many functional
algorithms.
--
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
