Clojure manually find nth element in a sequence

3
votes

I am a newbie to clojure (and functional programming for that matter) and I was trying to do some basic problems. I was trying to find the nth element in a sequence without recursion.

so something like

(my-nth '(1 2 3 4) 2) => 3

I had a hard time looping through the list and returning when i found the nth element. I tried a bunch of different ways and the code that I ended up with is

(defn sdsu-nth
 [input-list n]
 (loop [cnt n tmp-list input-list]
    (if (zero? cnt)
       (first tmp-list)
       (recur (dec cnt) (pop tmp-list)))))

This gives me an exception which says "cant pop from empty list"

I dont need code, but if someone could point me in the right direction it would really help!

6
clojurefunctional-programming
When you say "without recursion" do you mean "with recursion"? That is what the loop/recur construct is. – A. Webb
I mean to say, we might want to use looping constructs but the function should not explicitly make a call to itself. – Harsh Shah
Please note that even when you use recur inside of loop, it is to emulate recursion (although it will be compiled to loop), so it's more natural to think about this construction as of recursive anonymous function. – Mark Karpov

6 Answers

4
votes

You are using the function pop, which has different behavior for different data structures.

user> (pop '(0 1 2 3 4))
(1 2 3 4)
user> (pop [0 1 2 3 4])
[0 1 2 3]
user> (pop (map identity '(0 1 2 3 4)))
ClassCastException clojure.lang.LazySeq cannot be cast to clojure.lang.IPersistentStack  clojure.lang.RT.pop (RT.java:640)

Furthermore, you are mixing calls to pop with calls to first. If iterating, use peek/pop or first/rest as pairs, mixing the two can lead to unexpected results. first / rest are the lowest common denominator, if you want to generalize over various sequential types, use those, and they will coerce the sequence to work if they can.

user> (first "hello")
\h
user> (first #{0 1 2 3 4})
0
user> (first {:a 0 :b 1 :c 2})
[:c 2]

With your function, replacing pop with rest, we get the expected results:

user> (defn sdsu-nth
        [input-list n]
        (loop [cnt n tmp-list input-list]
              (if (zero? cnt)
                  (first tmp-list)
                (recur (dec cnt) (rest tmp-list)))))

#'user/sdsu-nth
user> (sdsu-nth (map identity '(0 1 2 3 4)) 2)
2
user> (sdsu-nth [0 1 2 3 4] 2)
2
user> (sdsu-nth '(0 1 2 3 4) 2)
2
user> (sdsu-nth "01234" 2)
\2
4
votes

given a list as list_nums, take up to n + 1 then from that return the last element which is nth.

(fn [list_nums n] (last (take (inc n) list_nums)))

and alternatively:

#(last (take (inc %2) %1))

proof:

(= (#(last (take (inc %2) %1)) '(4 5 6 7) 2) 6) ;; => true
2
votes

What you would really want to do is use the built-in nth function as it does exactly what you're asking: http://clojuredocs.org/clojure_core/clojure.core/nth

However, since you're learning this is still a good exercise. Your code actually works for me. Make sure you're giving it a list and not a vector -- pop does something different with vectors (it returns the vector without the last item rather than the first -- see here).

1
votes

Your code works fine for lists if supplied index is not equal or greater then length of sequence (you've implemented zero indexed nth). You get this error when tmp-list gets empty before your cnt gets to the zero.

It does not work so well with vectors:

user> (sdsu-nth [1 2 3 4] 2)
;; => 1
user> (sdsu-nth [10 2 3 4] 2)
;; => 10

it seems to return 0 element for every supplied index. As noisesmith noticed it happens because pop works differently for vectors because of their internal structure. For vectors pop will remove elements form the end, and then first returns first value of any vector.

How to fix: use rest instead of pop, to remove differences in behavior of your function when applied to lists and vectors.

1
votes
(fn [xs n]
  (if (= n 0)
    (first xs)
    (recur (rest xs) (dec n))))
0
votes

One more way that I thought of doing this and making it truly non recursive (ie without for/recur) is

(defn sdsu-nth
 [input-list n]
 (if (zero? (count input-list))
    (throw (Exception. "IndexOutOfBoundsException"))
    (if (>= n (count input-list))
       (throw (Exception. "IndexOutOfBoundsException"))
       (if (neg? n)
          (throw (Exception. "IndexOutOfBoundsException"))
          (last (take (+ n 1) input-list))))))