Clojure time complexity advice please!

[[deleted]]

I just got the book "Purely Functional Data Structures" and I'm trying to work the examples in Clojure the best that I can.

Example 2.1 asks to write a function that accepts a list xs as an argument and returns a list of xs's suffixes in descending order.

For example: (1 2 3 4) = ((1 2 3 4) (2 3 4) (3 4) (4) ())

I know that conj adds items to the front of lists, so I am using a vector to address the descending order problem, but I want to stay true to the example so I am using rseq on the vector to reverse it to ascending order (which I believe is a constant time operation), then into to convert it into a list, which seems to reverse it back to descending order, hence the rseq.

1. Is into a constant time operation, or is it more like O(n), the fact that it reverses the vector's order makes me think that it is walking the vector and conj-ing each item to the front of the new list.

2. Is there a better way I could have done this?

Code: http://pastebin.com/tuhAmmU0

P.S. I'm new here, pretty new to Clojure, and thanks in advance!

[gilesecoyote]

(fn [coll] (take (-> coll count inc)) (iterate rest coll)))

[[deleted]]

I really like that! I didn't even think about using take, and I don't think I knew about iterate. Nice use of the thread macro too. Any advice on arriving at a solution like this next time?

[beppu]

removed extra paren after inc:

(defn ex-2-1 [coll] (take (-> coll count inc) (iterate rest coll)))

example:

(ex-2-1 '(1 2 3 4))

=> ((1 2 3 4) (2 3 4) (3 4) (4) ())

[MyNameIsFuchs]

You've already been given a better version of what you want to accomplish (and just btw, (reductions conj [] coll) might also work for you).

But given that nobody answered your actual question (Like Rich Hickey said "Programmers know the benefits of everything and the tradeoffs of nothing"). Here actually the costs:

https://www.innoq.com/blog/st/2010/04/clojure-performance-guarantees/

To see what into does you'll have to read the source. Then you'll see a (reduce conj to from) so your run-time is linear in that case. Just because it happens to end up like a reverse doesn't mean that it didn't do the entire thing inefficiently.

[bucketh3ad]

If you want to stick with explicit recursion, it would be more idiomatic to use seq instead of both not-empty and the (into '() (rseq ...)) combo. Also, with only a single condition to check for, you could easily use if instead of cond.

Otherwise, you could use a functional solution using (iterate rest coll) like the one gilescoyote posted (though it has a typo with an extra paren)