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
-~----------~----~----~----~------~----~------~--~---
