I'm trying to follow. Can you explain in pseudo code? That's
impressive that it follows the classic approach on persistent data
structures . . .. from what I can tell. You successively divide the
list in halves of halves of halves. Then the lists of size 1 are
merged together as the stack unwinds . . .then I kinda lose it. Are
lists of equal length merged like what's needed for the runtime?
I mean, if all the size one lists are just merged in with the first
list as they come, then it won't run out of lists NEARLY as quickly as
it should.
so as long as it does that.
so here's the psuedo code I'm trying to implement in clojure. . . .
python code also worked.
The trouble is I can't just do the pop_front thing below, which makes
the code ugly. . . . or can I?
given a list of items in myOriginalList:
1) myBrokenUpList = {[x], foreach x in myOriginalList}
do while myBrokenUpList has more than one mini-list in it:
2) a = pop_front the first list in myBrokenUpList
3) b = pop_front the first list in myBrokenUpList
4) merged = some_merge_func(a, b)
5) myBrokenUpList = myBrokenUpList + merged <------- important
that the merged list go in at the back.
Is that what yours does? or does it merge all the singleton lists
into one growing list? If it is the latter, then that seems to be O
(n^2) time instead of O(n logn)
On Jan 11, 2:41 am, John <lgast...@gmail.com> wrote:
> Hi,
>
> I'm just learning Clojure too, so I don't have much to add to what
> everyone else has said, but here's my crack at a full implenentation
> of merge-sort in Clojure. I'm sure that there is plenty of room for
> improvement (especially wrt. the merge function) but in case it's
> helpful, here it is:
>
> (defn lazy-merge [seq1 seq2]
> (cond (<= (count seq1) 0) (lazy-cons (first seq2) (rest seq2))
> (<= (count seq2) 0) (lazy-cons (first seq1) (rest seq1))
> :else (let [h1 (first seq1)
> h2 (first seq2)]
> (if (< h1 h2)
> (lazy-cons h1 (lazy-merge (rest seq1) seq2))
> (lazy-cons h2 (lazy-merge seq1 (rest seq2)))))))
>
> (defn merge-sort [seq]
> (if (> (count seq) 1)
> (apply lazy-merge (map merge-sort (split-at (/ (count seq) 2)
> seq)))
> seq))
>
> -
> John
>
> On Jan 10, 9:21 pm, e <evier...@gmail.com> wrote:
>
> > I'm just trying to understand basic stuff.
> > say I have a local list called "myList" (assigned using 'let' . . .
> > should I have used something else?) Who cares what's in it. Maybe I
> > set it up from a list comprehension from some input to my function.
>
> > I have no idea how to iteratively mess with it since everything is
> > persistent. Ok, like, say it's a list of lists and I am going to be
> > merging the lists, like Tarjan's mergesort from some book from
> > college.
>
> > so I have myList with contents [[11] [2] [4] [1] [99]]
>
> > here's how I would do it in python:
>
> > def msort(myList):
> > myList = [[x] for x in someList]
> > while len(myList) > 1:
> > l1 = myList.pop(0)
> > l2 = myList.pop(0)
> > listmerge = some_merge_function(l1, l2)
> > myList.append(listmerge) # important that newly merged go
> > to back of queue to get proper runtime
> > return myList[0]
>
> > here's what I'm trying to do for clojure, and it's a mess:
>
> > (defn msort [toSort]
> > (def sorted (let
> > [myList (for [x toSort] [x])] <----- so far so good (not a
> > real comment. I don't know how, yet)
> > [
> > (while (> (count myList) 1) <------- infinite loop the way
> > written? I don't know how to overwrite myList
> > (let [l1 (nth myList 0)][])
> > (let [l2 (nth myList 1)][])
> > (let [listmerge (some_merge_func l1 l2)][])
> > (let [myList (concat (drop 2 myList) listmerge)][myList]) <---
> > probably a different local variable
> > )
> > ]))
> > sorted)
>
> > doesn't compile anyway . . . I see that the let is causing the scope
> > to be all screwed up. l1 and l2 can't be seen for the merge function.
>
> > should I be using let at all here? Can things be redefined using
> > def? see how much simpler it is not to say anything? Which is
> > it .... def or let in python? Answer: No . . .but I'm sure there's
> > value. This seems like something that might be in the FAQ. . . .or
> > somewhere back in these discussions. I'll look around.
>
> > Thanks.
--~--~---------~--~----~------------~-------~--~----~
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
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
-~----------~----~----~----~------~----~------~--~---
