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