I guess one answer to your question would be: If the seq is persistent (immutable) why would you need to make a copy of it?
On Dec 12, 8: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. > > This can be fixed by making the cons a lazy-cons. This creates a > lazily-called function that closes over the source parameter, thus > removing the call from the stack. This works fine in Clojure, and > seems to be the best solution for actual use in a program. (One > question... Is the reference to the lazy function maintained after the > function is realized? I don't want to have thousands seqs hanging > around in memory while they're not needed. Also, I'm not 100% sure of > the semantics of lazy-cons... the above code implemented with lazy- > cons IS O(n) in both time and space, correct? Or does lazy-cons do > something different than I'm thinking of) > > 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? > > (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). > > Thanks in advance for the help - I know this is probably a stupid > question, but I'm curious and want to make sure the way I'm thinking > about lists and seqs is correct. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
