> Really? I get: > > (last (copy-seq (range 100000))) > -> 99999
I'm running inside of VirtualBox assigned very little memory. Maybe that's why? I'll run some more tests. I know I have been able to get up to 3000 levels of recursion without a stack overflow, once, at another time. In any case, it's bad practice to consume the stack for anything more than a handful of the same recursion, correct? Even if in a dry test you can have a stack 10,000 frames deep, you can't rely on it in a program. > Calling reverse when done is still O(N) Really? Maybe my grasp of big-O notation is faulty, but isn't the recursive function itself O(n), and then a reversal another O(n) operation on top of that, leading to two complete traversals of the source list? I thought it was impossible to do a reversal on a linked list in constant time. Or is the implementation actually doubly- linked? Thanks for the reply, Rich! I am really impressed by what you've done with Clojure. -Luke On Dec 13, 9:28 am, Rich Hickey <richhic...@gmail.com> wrote: > On Dec 12, 9:51 pm, levand <luke.vanderh...@gmail.com> wrote: > > > > > So, I'm trying to understand functional programming, particularly as > > it relates to the seq abstraction, and I'm hitting a slight difficulty > > as I'm playing around - something that seems as if it ought to be > > simple, is not. > > > I'm playing with copying one seq into another. I've found several > > different ways to do it, but the most obvious one, in my opinion, is > > missing. > > > Here's the straight-up, high performance tail recursive version that > > was my first thought: > > > (defn copy-seq-r [source] > > (loop [so-far '() to-go source] > > (if (nil? to-go) > > so-far > > (recur (cons (first to-go) so-far) > > (rest to-go))))) > > > The obvious problem with this is that because seqs are last-in first- > > out, this returns the seq in reverse order. Obviously not what we > > wanted. And using (reverse) or consing the (last) is awful for > > performance. > > > The next implementation is simpler, and uses recursion quite > > elegantly: > > > (defn copy-seq [source] > > (if (nil? source) > > '() > > (cons (first source) (copy-seq (rest source))))) > > > The obvious fault with this is that it's non tail-recursive and blows > > the stack with seqs of greater than 200-300 elements. > > Really? I get: > > (last (copy-seq (range 100000))) > -> 99999 > > > However, there is a sense in which using lazy-cons feels rather like a > > cheat. It feels like there ought to be a straightforward functional > > way to copy a seq/list, in order, in O(n) time, without using > > laziness. Or is this seemingly simple task an impossibility due to the > > nature of the singly-linked list? That's beginning to be what I'm > > thinking. What would one do in a language like Scheme, without lazy- > > cons? > > Calling reverse when done is still O(N) > > > (Of course, another solution in Clojure would be to copy to a vec > > instead of a list and then seq it... But I'm more interested in the > > theory, here). > > As others have pointed out, copying an immutable thing is unnecessary, > but, in general, if you want to build a result in order in a single > pass you should use vectors in Clojure. > > Rich --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
