No, it will be O(n), where the "cool magic" is in the use of lazy
sequences.
Here's a very simple way to write an O(n) lazy concat:
user> (defn my-concat [& seqs]
(when-first [s seqs]
(if (seq s)
(lazy-seq (cons (first s) (apply my-concat (rest s) (rest
seqs))))
(recur (rest seqs)))))
user> (my-concat '(1 2 3) [4 5] '(6 7))
(1 2 3 4 5 6 7)
This is not proper lazy programming style, but it should give you the
basic idea.
The actual definition of concat is significantly more complicated:
user> (source concat)
(defn concat
"Returns a lazy seq representing the concatenation of the elements
in the supplied colls."
([] (lazy-seq nil))
([x] (lazy-seq x))
([x y]
(lazy-seq
(let [s (seq x)]
(if s
(cons (first s) (concat (rest s) y))
y))))
([x y & zs]
(let [cat (fn cat [xys zs]
(lazy-seq
(let [xys (seq xys)]
(if xys
(cons (first xys) (cat (rest xys) zs))
(when zs
(cat (first zs) (next zs)))))))]
(cat (concat x y) zs))))
-Jason
On Mar 1, 2009, at 9:47 PM, Zededarian wrote:
>
> Thanks!
>
> One follow up question, though: will the first solution take O(n^2)
> time, or is clojure clever enough to keep track of where the end of a
> sequence is on its own (or, alternately, to start by concatenating the
> last two elements and working backward)? Or does it do some other
> cool magic to make this quick?
>
> On Mar 1, 9:07 pm, Jason Wolfe <[email protected]> wrote:
>> Hi,
>>
>> The problem is that you end up with the front of your worklist being
>> wrapped in <n-lines> nested calls to lazy-seq, one per each call to
>> concat. Then, realizing the first element causes a stack overflow.
>> This wouldn't happen if you reversed the arguments to concat, but
>> then
>> you wouldn't get what you want. Some possibilities (untested):
>>
>> ; probably the shortest, most idiomatic solution?
>>
>> (defn getstrlist [file]
>> (apply concat
>> (take-while identity
>> (repeatedly #(getline file)))))
>>
>> ;or, using vectors, and written more like your solution:
>>
>> (defn getstrlist [file]
>> (loop [worklst []]
>> (if-let [x (getline file)]
>> (recur (into worklst x))
>> worklst)))
>>
>> Cheers,
>> Jason
>>
>> On Mar 1, 4:53 pm, Zededarian <[email protected]> wrote:
>>
>>> My ultimate goal is to get a list of all the words in a file in
>>> order. I have a function that will get a list of all the words on
>>> one
>>> line of this file in order, and I want to efficiently concatenate
>>> these lists to end up with one large list. I'm working with about
>>> 12000 lines right now, but in a perfect world I'd like to scale much
>>> higher.
>>
>>> I started off just using concat. Basically my code looks like:
>>> (defn getstrlist
>>> ([file]
>>> (loop [x (getline file) worklst '()]
>>> (if x
>>> (recur (getline file) (concat worklst (splitstr x)))
>>> worklst))))
>>
>>> Then in the REPL, if I type (def a (getstrlist FILE)), it works
>>> fine.
>>> But if I try to output a or take (first a), I get a stack overflow
>>> error. I don't know why this is. I remember hearing somewhere that
>>> Clojure had lazy sequences, so my best guess is that it isn't
>>> actually
>>> concatenating anything, but is storing pointers to the start of all
>>> the lists on a stack that overflows when I try to evaluate one of
>>> these pointers.
>>
>>> I know in Scheme I would write this using metalists that keep
>>> track of
>>> the location of their last element:
>>> (define (concat metalst1 metalst2)
>>> (set-cdr! (car metalst1) (cdr metalst2))
>>> (set-car! metalst1 (car metalst2))
>>> metalst1)
>>
>>> (define (make-metalst lst)
>>> (cons (get-end lst) lst))
>>
>>> (define (get-end lst)
>>> (if (null? lst)
>>> '()
>>> (if (null? (cdr lst))
>>> lst
>>> (get-end (cdr lst)))))
>>
>>> Which would be fairly efficient. But since Clojure doesn't seem to
>>> have real lists, I'm not quite sure how I could port this over. I
>>> suppose I could implement my own cons pairs like an idiot and do all
>>> of this manually, but I figure I'm just not understanding the
>>> "Clojure
>>> solution" to this problem.
> >
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
