loop/recur with multiple branches

[Glen Mailer]

I was recently working on some toy recursion problems, when I ran into a function that I can express simply using normaly recursion, but I can't seem to convert it into a form that works nicely with loop/recur.

It's certainly not the right way to solve this problem, but I'm intrigued to see what this pattern looks like with explicit tail calls:

Problem:
Extract a slice from a list
(slice [ 3 4 5 6 7 8 9 ] 2 4)
;=> [ 5 6 7 8 ]

Normal Recursive Solution:
(defn slice [[h & tail] s n]
  (cond
    (zero? n) nil
    (zero? s) (cons h (slice tail s (dec n)))
    :else     (slice tail (dec s) n)))

What would the tail recursive version of this look like? can it retain the nice readability of this form?

[Cedric Greevey]

What about the accumulator pattern?

(defn slice

  ([h s n]

    (slice h s n nil))

  ([[h & tail] s n acc]

    (cond

      (zero? n) acc

      (zero? s) (recur tail s (dec n) (cons h acc))

      :else     (recur tail (dec s) n acc))))

[Vincent Chen]

Try this (not tested, might be missing parens and whatnot):

(defn slice [x s n]
(loop [[h & tail] x, s s, n n, acc []]
(cond
(zero? n) acc
(zero? s) (recur tail s (dec n) (conj acc h))

:else (recur tail (dec s) n acc))))

Few notes:
- When trying for tail recursions, use an accumulator. The accumulator
carries the eventual result, which is returned at the base case.
- Since we're destructuring into head and tail, I used vectors. conj
will push to the end of the vector.
- In Clojure, vectors tend to be more natural than lists. Accumulating
into lists usually requires a reverse in the base case.

Regards,

Vincent Chen

[Cedric Greevey]

On Tue, Dec 10, 2013 at 6:29 PM, Vincent Chen <nood...@gmail.com> wrote:

Try this (not tested, might be missing parens and whatnot):

(defn slice [x s n]
  (loop [[h & tail] x, s s, n n, acc []]
    (cond
      (zero? n) acc
      (zero? s) (recur tail s (dec n) (conj acc h))

      :else (recur tail (dec s) n acc))))

Few notes:
- When trying for tail recursions, use an accumulator. The accumulator
carries the eventual result, which is returned at the base case.
- Since we're destructuring into head and tail, I used vectors. conj
will push to the end of the vector.
- In Clojure, vectors tend to be more natural than lists. Accumulating
into lists usually requires a reverse in the base case.

If you're going to go with vectors, why not go transient as well?

(defn slice [x s n]

  (loop [[h & tail] x, s s, n n, acc (transient [])]
    (cond
      (zero? n) (persistent! acc)
      (zero? s) (recur tail s (dec n) (conj! acc h))

      :else (recur tail (dec s) n acc))))

Might be more runtime efficient.

[Vincent Chen]

On Tue, Dec 10, 2013 at 11:46 PM, Cedric Greevey <cgre...@gmail.com> wrote:
> On Tue, Dec 10, 2013 at 6:29 PM, Vincent Chen <nood...@gmail.com> wrote:
>>
>> Try this (not tested, might be missing parens and whatnot):
>>
>> (defn slice [x s n]
>> (loop [[h & tail] x, s s, n n, acc []]
>> (cond
>> (zero? n) acc
>> (zero? s) (recur tail s (dec n) (conj acc h))
>> :else (recur tail (dec s) n acc))))
>>
>> Few notes:
>> - When trying for tail recursions, use an accumulator. The accumulator
>> carries the eventual result, which is returned at the base case.
>> - Since we're destructuring into head and tail, I used vectors. conj
>> will push to the end of the vector.
>> - In Clojure, vectors tend to be more natural than lists. Accumulating
>> into lists usually requires a reverse in the base case.
>
>
> If you're going to go with vectors, why not go transient as well?
>

Ah. I've read about them, but have never used them before myself. Thanks.

By the way, my reply wasn't directed at you. I didn't know that you
had already answered his questions until after I had sent mine :)