[racket] Find nth term of a List

[Ashley Fowler]

I need to make a function that finds the nth term of a list

Hence (getNth N LS)

Examples of use:
(getNth 0 '(a b c)) 		==> a
(getNth 3 '(a b c d e)) 	==> d
(getNth 3 '(a b c)) 		==> error

so far I have 

(define getNth (lambda (N LS)

                   (if (eq? N 0)(car LS)

which only includes the "base case". I need help on how to create this function. Any ideas?

[Todd O'Bryan]

Well, I know how I'd do it, but I don't think your professor is
teaching you the design recipe or templates, so I'm not sure how to
help you without giving away the answer.

Here's a hint. Most numbers involving natural numbers (0, 1, 2, 3,
...) have the following form:

(define f
(lambda (n)
(if (= n 0) base-case (do-something-to (f (- n 1)))))

Since zero is the base case, the only way you can get there is to
subtract. The tricky part is figuring out what you have to do to the
(f (- n 1)) and how to handle any other arguments to the function.

So, looking at your test cases, (getNth 3 '(a b c d e)) will probably
change into (getNth 2 ...) where you have to fill in the ... with
something that makes the expressions equivalent and you might have to
do some manipulating of the result.

Good luck!

> ____________________
> Racket Users list:
> http://lists.racket-lang.org/users
>
____________________
Racket Users list:
http://lists.racket-lang.org/users

[Matthias Felleisen]

Ashley, the proper way to derive the answer to these questions
can be found here:

http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-22.html#node_chap_17

Once you understand the design recipe, the kind of questions you're asking
on this mailing list disappear. At that point, you can start exploiting the
language and software design to interesting questions, like getting Yahooo
to tell you which maps to download from Google ad display locally -- via
a Racket program.

I have sent a similar suggestion to your instructor.

In the future, I suggest that your postings go like this:

-- My problem is X.
-- I have followed the design recipe to step C.
-- Can someone help me get from C to D.

I am not saying this to make our life easier, I am suggesting this to
help you become a good problem solver and software designer.

-- Matthias

[Stephen Bloch]

On Sep 25, 2012, at 9:08 PM, Ashley Fowler wrote:

so far I have 

(define getNth (lambda (N LS)

                   (if (eq? N 0)(car LS)

which only includes the "base case".

And even with only the base case written, there's already a bug that will cause it to crash horribly.

I need help on how to create this function. Any ideas?

No, you don't need help on how to create THIS function; you need help on how to create functions.  You've got several test cases with correct answers, which is one important step in the right direction (although I would also add a test case with an empty list).  The next (or perhaps previous!) step should be to really understand the data types of your inputs: a whole number and a list.  Both of these are recursively-defined data types, so you need to look at http://picturingprograms.com/download/chap25.pdf , which is entitled "Multiple recursive data".  Of course, that chapter assumes that you're already fluent at writing functions that operate on ONE recursive data type, e.g. http://picturingprograms.com/download/chap22.pdf and http://picturingprograms.com/download/chap24.pdf .

Stephen Bloch

sbl...@adelphi.edu

[Marco Morazan]

On Tue, Sep 25, 2012 at 9:08 PM, Ashley Fowler
<afow...@broncos.uncfsu.edu> wrote:
> I need to make a function that finds the nth term of a list
> Hence (getNth N LS)
>
> Examples of use:
> (getNth 0 '(a b c)) ==> a
> (getNth 3 '(a b c d e)) ==> d
> (getNth 3 '(a b c)) ==> error
>
>
> so far I have
>
> (define getNth (lambda (N LS)
> (if (eq? N 0)(car LS)
>

A couple of observations:

1. Is eq? the most natural way to test the equality of numbers? (minor quibble)

2. You need to process two pieces of (recursively defined) data of
arbitrary size: a natural number and a list. Your code suggests you
have decided to write this function as you would any function that
processes a natural number. Is this the best choice? What will happen
if N is 0 and the list is empty?

Others have pointed you to references in which you will discover that
you ought to write this function analyzing the different possible
combinations of the input data. Specifically, a natural number can be
0 or not be zero while a list can be empty or not empty. This gives
you four possible scenarios:

N is 0 and LS is empty
N 0 and LS is not empty
N is not 0 and LS is empty
N is not 0 and LS is not empty

What should your code do for each of these?

I hope that helps.

--

Cheers,

Marco

Have a´¨)
¸.·´¸.·*´¨) ¸.·*¨)
(¸.·´ (¸.·´ * wonderful day! :)

[Tim Brown]

On 26/09/12 15:31, Marco Morazan wrote:
> 1. Is eq? the most natural way to test the equality of numbers? (minor quibble)

I was wondering this, myself, earlier, but is zero? the fastest way to
test for zero-ness?

Tim

--
Tim Brown <tim....@cityc.co.uk> | City Computing Limited |
T: +44 20 8770 2110 | City House, Sutton Park Road |
F: +44 20 8770 2130 | Sutton, Surrey, SM1 2AE, GB |
-----------------------------------------------------------------------|
BEAUTY: What's in your eye when you have a bee in your hand |
-----------------------------------------------------------------------'
City Computing Limited registered in London No. 1767817.
Registered Office: City House, Sutton Park Road, Sutton, Surrey, SM1 2AE
VAT number 372 8290 34.

[Matthias Felleisen]

Fast is so irrelevant for this question.

Correct is what really matters.

[Tim Brown]

What is the difference in correctness between "(= x 0)" vs. "(zero? x)"?

Fast is relevant to some questions (solutions) I have -- terminating tight
loops etc. And given a choice of (eq? 0 x), (= 0 x) and (zero? x), which
would, and which should take the shortest time to perform 10^12 times?

Maybe I'm thinking a bit too much like a C programmer -- (!x)... works for
me as a test in so many ways; that I tend to want to use something like it
when I'm writing in other languages. (Where I should be using zero? false?
and/or null?).

Tim

[Robby Findler]

If you have a loop where the exit condition test is a significant
contribution to the time, then we should look at the loop to answer
these questions, as it will depend on what else you're doing there.
(This seems like a rare situation to me, but not entirely out of the
realm of possibility).

Otherwise, I'd ignore the speed issue.

Robby

[Sam Tobin-Hochstadt]

On Thu, Sep 27, 2012 at 12:10 PM, Tim Brown <tim....@cityc.co.uk> wrote:
> What is the difference in correctness between "(= x 0)" vs. "(zero? x)"?

There is none: http://docs.racket-lang.org/reference/number-types.html?q=zero%3F#%28def._%28%28quote._~23~25kernel%29._zero~3f%29%29

> And given a choice of (eq? 0 x), (= 0 x) and (zero? x), which
> would, and which should take the shortest time to perform 10^12 times?

(= 0 x) and (zero? x) should compile to the same code.

(eq? 0 x) produces simpler code, because:

(= 0 0.0) => #t, but (eq? 0 0.0) => #f.

For actual performance numbers, as opposed to reasoning from
instructions sequences, Robby's advice about benchmarking is very
wise.
--
sam th
sa...@ccs.neu.edu

[Stephen Bloch]

On Sep 27, 2012, at 12:10 PM, Tim Brown wrote:

> What is the difference in correctness between "(= x 0)" vs. "(zero? x)"?

None, although neither one is equivalent to "(eq? 0 x)".

> Fast is relevant to some questions (solutions) I have -- terminating tight
> loops etc. And given a choice of (eq? 0 x), (= 0 x) and (zero? x), which
> would, and which should take the shortest time to perform 10^12 times?

If you're looking for elements specified by their position in a list of 10^12 elements, you should probably be using a different data structure in the first place :-)

For almost any program I can think of, the performance difference among (eq? 0 x), (= 0 x), and (zero? x) is likely to be insignificant by comparison with other parts of the program.

> Maybe I'm thinking a bit too much like a C programmer -- (!x)... works for
> me as a test in so many ways; that I tend to want to use something like it
> when I'm writing in other languages. (Where I should be using zero? false?
> and/or null?).

Yes, C programmers routinely rely on all sorts of machine-dependent assumptions: almost any datum can be viewed as an integer, null pointers are represented by the same bit pattern as the integer 0, the floating-point number 0.0 is represented by the same bit pattern as the integer 0, etc.

I've worked on systems that intentionally used the bit pattern for 1, not 0, as a null pointer (it was a word-addressable machine, and if you tried to dereference an odd-numbered address, it would crash immediately, as one would expect of dereferencing a null pointer). And on MANY systems (including Racket), the floating-point number 0.0 doesn't necessarily resemble the integer 0.


Stephen Bloch
sbl...@adelphi.edu