3

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!

Improve this question
3
  • When you say "without recursion" do you mean "with recursion"? That is what the loop/recur construct is. Commented Sep 10, 2014 at 15:34
  • I mean to say, we might want to use looping constructs but the function should not explicitly make a call to itself. Commented Sep 10, 2014 at 15:39
  • 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. Commented Sep 10, 2014 at 16:00

6 Answers 6

Reset to default
4

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

4

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
Improve this answer

Comments

3

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).

Improve this answer

1 Comment

Yes i know about the built-in nth function, but i am just exercising here.
1

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.

Improve this answer

5 Comments

it will count backward from the end with vectors
@noisesmith, just tried it... it seems to return first element for any supplied index... Wait a minute..
user> (pop [0 1 2 3 4]) => [0 1 2 3] - using this method, you get nth item from the end, not from the beginning
oh, haha, it is mixing first and pop - it should be using first / rest or peek / pop, mixing first and pop gives absurd results
@noisesmith, you're right, but first is also guilty :-)
1 
(fn [xs n]
  (if (= n 0)
    (first xs)
    (recur (rest xs) (dec n))))
Improve this answer

Comments

0

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))))))
Improve this answer

1 Comment

(first (drop n input-list)) will also work, try using cond to eliminate chain of if else statements.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.