find the last and the nth item without using last or nth

[Roelof Wobben]

Hello,

IM busy with 4Clojure and I have now two challenges which I think can be solved the same way.

On a list I first have to find the last item of a list without using last and after that I have to do the same for a nth item and im not allowed to use nth.

Now I can convert the list to a vector and use the vector things but I think this is cheating at some way.

Could a recurvice way or a loop do the trick. And how do I then take the right value.

Should I use first then or is there a better way. I also read about doseq but then I have to find out how to print only the item I want.

Anyone who can give a hint without spoiling the answer.

Roelof

[James Reeves]

Your intuition that this can be done through recursion or a loop is correct (the latter being a more specialised version of the former).

When dealing with recursion, it often helps to consider the base case, i.e. where the recursion stops. Typically this is when you get to zero or one elements.

You may wish to consider the following questions:

1. How do you find the last element of a seq with exactly one element?

2. How do you find out whether a seq has one element, or more than one element?

3. How do you find out the last element if a seq with exactly two elements?

4. How do you find out the last element of a seq that may have one or two elements?

- James

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Tassilo Horn]

Roelof Wobben <rwo...@hotmail.com> writes:

> Could a recurvice way or a loop do the trick.

Yes.

> And how do I then take the right value.

For nth, you need a counter that you can increment in each recursion
step. For last, you return the first element of the list whose rest is
the empty list.

Bye,
Tassilo

[Roelof Wobben]

Op woensdag 30 april 2014 08:21:40 UTC+2 schreef James Reeves:

Your intuition that this can be done through recursion or a loop is correct (the latter being a more specialised version of the former).

When dealing with recursion, it often helps to consider the base case, i.e. where the recursion stops. Typically this is when you get to zero or one elements.

You may wish to consider the following questions:

1. How do you find the last element of a seq with exactly one element?

   the last and the first element are the same
 

2. How do you find out whether a seq has one element, or more than one element?

Look at the length of the seq
 

3. How do you find out the last element if a seq with exactly two elements?

take the first element away and you have a seq of one element . 

4. How do you find out the last element of a seq that may have one or two elements?

Look at the length. If it has one element , see question 1
if it has 2 elements, see question 3.

 

[Roelof Wobben]

Op woensdag 30 april 2014 08:22:07 UTC+2 schreef Tassilo Horn:

Thanks, and if I use cons (item, list) then item is the value I want. I only have to print it.

Roelof
 

[Roelof Wobben]

Op woensdag 30 april 2014 08:50:22 UTC+2 schreef Roelof Wobben:

If I look at the documentations I think I have to use doseq for running and cons for finding and a if then to stop at the right place.

Am I at the right track.  

 

[James Reeves]

On 30 April 2014 07:49, Roelof Wobben <rwo...@hotmail.com> wrote:

Op woensdag 30 april 2014 08:21:40 UTC+2 schreef James Reeves:

1. How do you find the last element of a seq with exactly one element?

   the last and the first element are the same

Right. So to formalise it:

    (defn last* [coll]

      (first coll))

 

I'm using "last*" as the name so that it doesn't conflict with the function "last" in clojure.core.

2. How do you find out whether a seq has one element, or more than one element?

Look at the length of the seq

Unlike vectors, seqs are simple structures and don't know their own length.

You can count seqs, but this involves iterating through every element in turn. If all you want to do is find out whether there is more than one element, there's a much simpler and more efficient way.

3. How do you find out the last element if a seq with exactly two elements?

take the first element away and you have a seq of one element . 

So in other words:

    (defn last* [coll]

      (first (rest coll)))

 

4. How do you find out the last element of a seq that may have one or two elements?

Look at the length. If it has one element , see question 1
if it has 2 elements, see question 3.

In code, this would be:

    (defn last* [coll]

      (if (more-than-one-element? coll)

        (first (rest coll))

        (first coll)))

The "more-than-one-element?" to be replaced with the answer to question 2, of course.

Can you think of a way of making this function recursive to work with any number of elements?

- James

[Tassilo Horn]

Roelof Wobben <rwo...@hotmail.com> writes:

>>> For nth, you need a counter that you can increment in each recursion
>>> step. For last, you return the first element of the list whose rest
>>> is the empty list.
>>

>> Thanks, and if I use cons (item, list) then item is the value I
>> want. I only have to print it.

I think you should return it, not just print it.

> If I look at the documentations I think I have to use doseq for
> running and cons for finding and a if then to stop at the right place.

No. doseq doesn't allow you to stop after you've found the right item,
and cons constructs a new list given an item and another list.

You want either an explicit recursion or `loop`/`recur` for running
through the list, and in each step you want to use `first` and `rest` to
split the list into its head item and its tail.

Bye,
Tassilo

[Roelof Wobben]

Op woensdag 30 april 2014 09:58:26 UTC+2 schreef James Reeves:

On 30 April 2014 07:49, Roelof Wobben <rwo...@hotmail.com> wrote:

Op woensdag 30 april 2014 08:21:40 UTC+2 schreef James Reeves:

1. How do you find the last element of a seq with exactly one element?

   the last and the first element are the same

Right. So to formalise it:

    (defn last* [coll]

      (first coll))

 

I'm using "last*" as the name so that it doesn't conflict with the function "last" in clojure.core.

2. How do you find out whether a seq has one element, or more than one element?

Look at the length of the seq

Unlike vectors, seqs are simple structures and don't know their own length.

You can count seqs, but this involves iterating through every element in turn. If all you want to do is find out whether there is more than one element, there's a much simpler and more efficient way.

Yep, if there is only 1 item is a list (rest coll) is nil.

 

 

In code, this would be:

    (defn last* [coll]

      (if (more-than-one-element? coll)

        (first (rest coll))

        (first coll)))

The "more-than-one-element?" to be replaced with the answer to question 2, of course.

Can you think of a way of making this function recursive to work with any number of elements?

I think I can but I have to try some things but untested it looks like this

 (defn last* [coll]

      (if (nil? (rest coll)

           (first coll)))

   (last* (rest coll))

Now I wonder how I can make it work if I want to find lets say the 5th value of a array of any number of elements

Then rest is never nil. So at first glance if I do not know the length it cannnot be done recursive.

I have to do it in a for loop.

- James

[James Reeves]

On 30 April 2014 10:41, Roelof Wobben <rwo...@hotmail.com> wrote:

Op woensdag 30 april 2014 09:58:26 UTC+2 schreef James Reeves:

Unlike vectors, seqs are simple structures and don't know their own length.

You can count seqs, but this involves iterating through every element in turn. If all you want to do is find out whether there is more than one element, there's a much simpler and more efficient way.

Yep, if there is only 1 item is a list (rest coll) is nil.

Almost. Clojure distinguishes between nil and the empty list. The function you want is "next":

   (rest [1]) => ()

   (next [1]) => nil

Why the distinction between next and rest? It has to do with laziness, and if you're interested I can go into more detail. Otherwise just remember that rest returns an empty list, and next returns nil.

  

Can you think of a way of making this function recursive to work with any number of elements?

I think I can but I have to try some things but untested it looks like this

 (defn last* [coll]

      (if (nil? (rest coll)

           (first coll)))

  (last* (rest coll))

That's pretty much right. You just need to use (nil? (next coll)) or (empty? (rest coll))

 (defn last* [coll]

   (if (nil? (next coll))

     (first coll)

     (last* (next coll))))

You can also write it with loop/recur:

 (defn last* [coll]

   (loop [coll coll]

     (if (nil? (next coll))

       (first coll)

       (recur (next coll))))

See how the recursive step is replaced with "recur"? This is more efficient because we're not filling the stack up as we would with recursion. You can also write the above as:

 (defn last* [coll]

   (if (nil? (next coll))

     (first coll)

     (recur (next coll))))

If a recur is used without an outer loop, the whole function acts as an implicit loop. There's one more optimisation you can perform, and that's to take advantage of nil being a "falsey" value.

(defn last* [coll]

  (if (next coll)

    (recur (next coll))

    (first coll)))

If (next coll) isn't nil, it recurs. If it is, then the if statement fails and the first item of the collection is returned. The above code is actually how it's defined in clojure.core.

Now I wonder how I can make it work if I want to find lets say the 5th value of a array of any number of elements

Then rest is never nil. So at first glance if I do not know the length it cannnot be done recursive.

I have to do it in a for loop.

You need a counter. Take a look at the version of last* that has a loop/recur:

 (defn last* [coll]

   (loop [coll coll]

     (if (nil? (next coll))

       (first coll)

       (recur (next coll))))

Consider how you might add a counter to the loop. You'll want to increment the counter, then stop when it reaches the desired number.

- James

[Roelof Wobben]

Op woensdag 30 april 2014 12:14:39 UTC+2 schreef James Reeves:

On 30 April 2014 10:41, Roelof Wobben <rwo...@hotmail.com> wrote:

Op woensdag 30 april 2014 09:58:26 UTC+2 schreef James Reeves:

Unlike vectors, seqs are simple structures and don't know their own length.

You can count seqs, but this involves iterating through every element in turn. If all you want to do is find out whether there is more than one element, there's a much simpler and more efficient way.

Yep, if there is only 1 item is a list (rest coll) is nil.

Almost. Clojure distinguishes between nil and the empty list. The function you want is "next":

   (rest [1]) => ()

   (next [1]) => nil

Why the distinction between next and rest? It has to do with laziness, and if you're interested I can go into more detail. Otherwise just remember that rest returns an empty list, and next returns nil.

 

 (defn last* [coll]

   (loop [coll coll]

     (if (nil? (next coll))

       (first coll)

       (recur (next coll))))

Consider how you might add a counter to the loop. You'll want to increment the counter, then stop when it reaches the desired number.

So without checking it so out of my head I would do this

 (defn last* [coll, number]

   (loop [coll coll]

     (if == counter number))

       (first coll)

       (recur (next coll) (+counter 1 ))

 

[James Reeves]

On 30 April 2014 11:41, Roelof Wobben <rwo...@hotmail.com> wrote:

Op woensdag 30 april 2014 12:14:39 UTC+2 schreef James Reeves:

Consider how you might add a counter to the loop. You'll want to increment the counter, then stop when it reaches the desired number.

So without checking it so out of my head I would do this

 (defn last* [coll, number]

   (loop [coll coll]

     (if == counter number))

       (first coll)

       (recur (next coll) (+counter 1 ))

Essentially yes. You need to initiate the counter to zero, and you still need a condition to make sure you don't go past the end of the seq (in case n is more than the length of the list), but you've basically got it.

- James

[Roelof Wobben]

I tried this problem again.

So I did this:

(defn nth* [coll, number]

   (let [acc 0]

   (loop [coll coll acc]

     (if == acc number))

       (first coll)

       (recur (next coll) (+acc 1 ))

but when I do :

(nth* (1,2,3,4,5)2)) I see a cannot cast error message.

Is this because Clojure cannot figure out what the coll and what the number is ?

Roelof

Op woensdag 30 april 2014 12:53:01 UTC+2 schreef James Reeves:

[James Reeves]

You have a number of typos, syntax errors and missing brackets in your source code. It should be:

(defn nth* [coll number]

  (loop [coll coll, acc 0]

    (if (= acc number)

      (first coll)

      (recur (next coll) (+ acc 1)))))

Additionally, you're using an unquoted list to test. Use a vector or quote the list:

(nth* [1 2 3 4 5] 2)

- James

[Roelof Wobben]

Thanks,

Roelof

Op dinsdag 6 mei 2014 17:11:52 UTC+2 schreef James Reeves: