Why am I getting a stack overflow in the following Clojure function:
(defn length
[xs]
(if ,(not= xs nil)
(println (+ 1 (length (rest xs))))
(println 0)))
-
1You don't talk about stack overflow on StackOverflow. lolR. Martinho Fernandes– R. Martinho Fernandes2009-07-16 17:04:55 +00:00Commented Jul 16, 2009 at 17:04
-
1<insert witty statement about site/question recursion here>MattC– MattC2009-07-16 17:05:43 +00:00Commented Jul 16, 2009 at 17:05
-
Not knowing clojure, but will "rest xs" return nil when xs has only 1 element? or will it return an empty list/string/whatever that isn't nil?Lasse V. Karlsen– Lasse V. Karlsen2009-07-16 17:06:22 +00:00Commented Jul 16, 2009 at 17:06
-
I assume the stack is just overflowing for the expected reasion. Clojure does not automatically optimize tail calls (and although this is not a tail call, it could be trivially be rewritten to be one).jrockway– jrockway2009-07-16 17:08:44 +00:00Commented Jul 16, 2009 at 17:08
-
I also find it hard to believe that this is the best way to implement a length function in a functional language, it looks horribly non-performant to me.Lasse V. Karlsen– Lasse V. Karlsen2009-07-16 17:10:47 +00:00Commented Jul 16, 2009 at 17:10
|
Show 1 more comment
2 Answers
I think the idiomatic way of doing this is to call seq on your collection. seq on a collection returns nil if the collection is empty.
(defn length [xs]
(if (seq xs)
(inc (length (rest xs)))
0))
This isn't tail-recursive (you aren't using recur and can't here) so this will still overflow the stack on very large collections.
user> (println (length (range 1000000)))
;; stack overflow
One tail-recursive version would be
(defn length [xs]
(loop [xs xs
acc 0]
(if (seq xs)
(recur (rest xs) (inc acc))
acc)))
user> (println (length (range 1000000)))
1000000
This won't overflow the stack even for huge collections but it's still slow. Many Clojure collections implement the Counted interface and the built-in count function returns the length of those collections in constant time.
Comments
After the switch to all lazy seqs, rest will never return nil, just an empty list - try this:
(defn length
[xs]
(if (not (empty? xs))
(println (+ 1 (length (rest xs))))
(println 0)))
OR this
(defn length
[xs]
(if ,(not= xs nil)
(println (+ 1 (length (next xs))))
(println 0)))
