Getting the tail of a list?

Hi everybody,

I have spent the night reading about the wonders of Scheme at
http://www.teach-scheme.org and have stumbled over a small demo program.

This function checks whether a guest is on the guest list or not:

(define (guest name list)
(cond
((empty? list) 'no)
((equal? name (first list)) 'yes)
(else (guest name (rest list)) )))

I am in love with Ruby and I’m not about to switch to Scheme, so I
wanted to write this in ruby:

def guest (name, list)
if list.empty?
:no
elseif name == list.first
:yes
else
guest(name, list.rest)
end
end

Well looks nice but there’s a little something missing: there’s no such
method “rest” for an array! Whereas there are things like Array#first
and Array#last, this seems to have been forgotten. Of course I could
write it like this:

def guest(name list)
if list.empty?
:no
elsif name == list.shift
:yes
else
guest(name,list)
end
end

But this would change my list in place, which is definetely not what I
want. And I could also just add the rest function to Array:

class Array
def rest()
self[1…self.length]
end
end

Easy enough, but still, why isn’t this included per default in the array
class? Or am I the only one missing it?

Cheers,
Carsten.

Carsten Eckelmann wrote:

Hi everybody,

I have spent the night reading about the wonders of Scheme at
http://www.teach-scheme.org and have stumbled over a small demo program.

This function checks whether a guest is on the guest list or not:

(define (guest name list)
(cond
((empty? list) 'no)
((equal? name (first list)) 'yes)
(else (guest name (rest list)) )))

I am in love with Ruby and I’m not about to switch to Scheme, so I
wanted to write this in ruby:

def guest (name, list)
if list.empty?
:no
elseif name == list.first
:yes
else
guest(name, list.rest)

No Array#rest as you noted bellow, you may use list[1…-1] here.

end
end

However, why not just this:

def guest(name,list)
list.include?(name) ? :yes : :no
end

And what’s wrong with boolean return values?

···

Well looks nice but there’s a little something missing: there’s no such
method “rest” for an array! Whereas there are things like Array#first
and Array#last, this seems to have been forgotten. Of course I could
write it like this:

def guest(name list)
if list.empty?
:no
elsif name == list.shift
:yes
else
guest(name,list)
end
end

Nobody’s really addressed this question posed by the OP. There are
several facets to the answer. The short answer is that procedural and
object-oriented languages & libraries usually don’t /need/ a Lisp-style
cdr. The reason why Lisp (and its descendants, like Scheme) /do/ is
because lists are the paramount (read: only) built-in data structure,
and cdr() facilitated optimization that was necessary to prevent
needless array copying. (It’s reasonable to ask why there wasn’t a
similar tail function, since day one of most procedural programming
courses teach you how to write a function like it.) Procedural
languages allow direct (i.e. random-access) array access, so that an
operation like arr[ 34 ] can be compiled into the same number of
instructions as arr[ 2348 ]–a constant-time operation. Not so in Lisp,
where element access is an O(n) operation. Object-oriented libraries
often take this one step further, with custom data structures to handle
numerous lists of many types, such as stacks, vectors, sets, and maps.

jason r tibbetts
tibbetts at acm dot org
http://www.toad.net/~tibbetts/jason

:wq

···

On Jan 12, 2004, at 6:42 PM, Carsten Eckelmann wrote:

Easy enough, but still, why isn’t this included per default in the
array class? Or am I the only one missing it?

class Array
def rest()
self[1…self.length]
end
end

This creates a duplicate of the list, and if you’re simulating tail recursion with that it might not necessarily be what you want

a = [1,2,3,4,5]
c = a.shift
p c #=> 3
p a #=> [2,3,4,5]

Using list.include?(name) is probably better, but for reference, you can use shift for something like this:

def guest(name,list)
if list.empty?
:no
elsif name == list.shift
:yes
else
guest(name, list)
end
end

For that matter, didn’t someone discuss adding c[ad]+r functions using undefined_method? Using regexp and iterating to allow even insane amounts like caddaaaddar or so

  • Greg Millam

Hi,

···

At Tue, 13 Jan 2004 11:01:38 +0900, Tim Sutherland wrote:

Taking the rest' of a linked list is a constant time operation. In contrast, when you ary[1…-1]', Ruby constructs a new array and fills it in
using the entries in ary. The time for this is linear in terms of the
number of entries in the array.

No, they can be shared and copy-on-write.


Nobu Nakada

Gennady wrote:

Carsten Eckelmann wrote:

Hi everybody,

I have spent the night reading about the wonders of Scheme at
http://www.teach-scheme.org and have stumbled over a small demo program.

This function checks whether a guest is on the guest list or not:

(define (guest name list)
(cond
((empty? list) 'no)
((equal? name (first list)) 'yes)
(else (guest name (rest list)) )))

I am in love with Ruby and I’m not about to switch to Scheme, so I
wanted to write this in ruby:

def guest (name, list)
if list.empty?
:no
elseif name == list.first
:yes
else
guest(name, list.rest)

No Array#rest as you noted bellow, you may use list[1…-1] here.

OKAY! That’s a bit shorter, thanks.

However, why not just this:

def guest(name,list)
list.include?(name) ? :yes : :no
end

And what’s wrong with boolean return values?

Yes of course that’s the way to do it in ruby. My example was a bit of
an academic exercise used to demonstrate recursive processing of lists
to beginning students.
And there’s nothing wrong with booleans, I just wanted to model the ruby
code as close as possible to the scheme code.

Cheers,
Carsten.

Gregory Millam wrote:

For that matter, didn’t someone discuss adding c[ad]+r functions using undefined_method?
Using regexp and iterating to allow even insane amounts like caddaaaddar or so

I don’t remember that post, but I love the idea. It has a very high level of “cuteness” … effectively adding an infinite number of methods to a class.

H.

Good answer, but a minor quibble is addressed below …

jason r tibbetts wrote:

Nobody’s really addressed this question posed by the OP. There are
several facets to the answer. The short answer is that procedural and
object-oriented languages […]

Its not so much the difference between procedural and OO languages, but
between link-list and array-based lists.

A lot of times, with our glut of data structures in modern languages, we
forget the elegance of the simple linked list data structure. Ward
Cunningham uses linked lists to great effect in his FIT library and
achieves elegance in code that would have been clumsy if he had stayed
with the library supplied container classes. The source for the FIT
library is recommended reading for programmers.

···


– Jim Weirich jweirich@one.net http://onestepback.org

“Beware of bugs in the above code; I have only proved it correct,
not tried it.” – Donald Knuth (in a memo to Peter van Emde Boas)

Or list[1,-1], which should be more efficient since it doesn’t build
a Range object.

-Mark

···

On Tue, Jan 13, 2004 at 09:18:54AM +0900, Carsten Eckelmann wrote:

No Array#rest as you noted bellow, you may use list[1…-1] here.

Jim Weirich wrote:

Good answer, but a minor quibble is addressed below …

jason r tibbetts wrote:

Nobody’s really addressed this question posed by the OP. There are
several facets to the answer. The short answer is that procedural and
object-oriented languages […]

Its not so much the difference between procedural and OO languages,
but between link-list and array-based lists.

A lot of times, with our glut of data structures in modern languages,
we forget the elegance of the simple linked list data structure. Ward
Cunningham uses linked lists to great effect in his FIT library and
achieves elegance in code that would have been clumsy if he had stayed
with the library supplied container classes. The source for the FIT
library is recommended reading for programmers.

It’s always horses for courses though. If the OP just wants to show the
class a simular construct in ruby creating a linked list class strays
from the problem. It’s also a grand example of premature optimisation
inthis case - the root of many programing evils.

How about simply this (to show the conversion of the scheme, and also
show how you can replace and extend ruby)

class Array

def guest (name, list)
return false if list.empty?
return true if name == list.shift
guest name,list
end

def include?(name)
guest name,clone
end

end

Ralph

Harry Ohlsen wrote:

caddaaaddar or so
I don’t remember that post, but I love the idea. It has a very high
level of “cuteness” … effectively adding an infinite number of methods
to a class.

You only think that until you find such an abomination in someone elses
code and tries to figure out what it does.

There’s a reason for Common Lisp to limit the number to 7 or whatever it
was :stuck_out_tongue:

Whups, never mind, that doesn’t work. :slight_smile:

···

On Tue, Jan 13, 2004 at 12:40:03AM +0000, Mark J. Reed wrote:

Or list[1,-1], which should be more efficient since it doesn’t build
a Range object.

“Mark J. Reed” markjreed@mail.com schrieb im Newsbeitrag
news:20040113004115.GC8806@mulan.thereeds.org

Or list[1,-1], which should be more efficient since it doesn’t build
a Range object.

Whups, never mind, that doesn’t work. :slight_smile:

But this does:

irb(main):001:0> a=[1,2,3,4]
=> [1, 2, 3, 4]
irb(main):002:0> a[1,a.length]
=> [2, 3, 4]

The second parameter is the length. Simply using a.length is sufficient
since then all elements to the end are used.

robert
···

On Tue, Jan 13, 2004 at 12:40:03AM +0000, Mark J. Reed wrote:

I would like to write a[2,Infinity], or something like that…

Gergo

···

On 0113, Robert Klemme wrote:

Whups, never mind, that doesn’t work. :slight_smile:

But this does:

irb(main):001:0> a=[1,2,3,4]
=> [1, 2, 3, 4]
irb(main):002:0> a[1,a.length]
=> [2, 3, 4]

The second parameter is the length. Simply using a.length is sufficient
since then all elements to the end are used.


±[ Kontra, Gergelykgergely@mcl.hu PhD student Room IB113 ]---------+

http://www.mcl.hu/~kgergely “Olyan langesz vagyok, hogy |
Mobil:(+36 20) 356 9656 ICQ: 175564914 poroltoval kellene jarnom” |
±- Magyar php mirror es magyar php dokumentacio: http://hu.php.net --+

Dave Brown wrote:

In article 20040114130426.GA15734@mlabdial.hit.bme.hu,
: On 0113, Robert Klemme wrote:
: > > Whups, never mind, that doesn’t work. :slight_smile:
: >
: > But this does:
: >
: > irb(main):001:0> a=[1,2,3,4]
: > => [1, 2, 3, 4]
: > irb(main):002:0> a[1,a.length]
: > => [2, 3, 4]
: >
: > The second parameter is the length. Simply using a.length is sufficient
: > since then all elements to the end are used.
:
: I would like to write a[2,Infinity], or something like that…

a[1,-1]

:slight_smile: “Error: Cycle detected in ruby-talk thread”

Read again. Robert’s point was that this doesn’t work. The second
parameter is a length, and a length of -1 gives you nil.

Hal

···

KONTRA Gergely kgergely@mlabdial.hit.bme.hu wrote:

“Dave Brown” dagbrown@LART.ca schrieb im Newsbeitrag
news:cio6ub.3h9.ln@lart.ca…

In article 4005AC05.90007@hypermetrics.com,
: Dave Brown wrote:
: > In article 20040114130426.GA15734@mlabdial.hit.bme.hu,
: > : On 0113, Robert Klemme wrote:
: > : > > Whups, never mind, that doesn’t work. :slight_smile:
: > : >
: > : > But this does:
: > : >
: > : > irb(main):001:0> a=[1,2,3,4]
: > : > => [1, 2, 3, 4]
: > : > irb(main):002:0> a[1,a.length]
: > : > => [2, 3, 4]
: > : >
: > : > The second parameter is the length. Simply using a.length is
sufficient
: > : > since then all elements to the end are used.
: > :
: > : I would like to write a[2,Infinity], or something like that…
: >
: > a[1,-1]
:
: :slight_smile: “Error: Cycle detected in ruby-talk thread”
:
: Read again. Robert’s point was that this doesn’t work. The second
: parameter is a length, and a length of -1 gives you nil.

D’oh.

That’s what I get for not firing up irb.

a[1…-1] is what I actually meant.

–Dave

Error: Cycle detected in ruby-talk thread cycle. Bailing out.

a[1…-1] was proposed already. :-))

Nevermind, 't was fun.

robert
···

Hal Fulton hal9000@hypermetrics.com wrote:
: > KONTRA Gergely kgergely@mlabdial.hit.bme.hu wrote: