Getting the tail of a list?

[Carsten Eckelmann]

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.

 

[Gennady]

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?

 

[Carsten Eckelmann]

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.

 

[Tim Sutherland]

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. [...]
I am in love with Ruby and I'm not about to switch to Scheme, so I
wanted to write this in ruby: [...]
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:

[...]

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.

For this reason[*], the normal Ruby coding style for manipulating Arrays is
not like the normal Scheme style for lists.

If you want to write Scheme-like code in Ruby, you may wish to write a
linked-list class and use this, rather than Arrays. Alternatively, you could
pass around an index to the Array and treat `ary[index]` as the head of
your list and pass `index+1` to represent taking the tail of the list.

[*] Also, Scheme supports `proper tail recursion', which assists in the
recursive-procedure style common in Scheme code.

 

[jason r tibbetts]

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

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

 

[Gregory Millam]

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

 

[Harry Ohlsen]

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.

 

[Jim Weirich]

Good answer, but a minor quibble is addressed below ...

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.

 

[Ralph Mason]

Good answer, but a minor quibble is addressed below ...

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

 

[nobu.nokada]

Hi,

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

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.

 

[Robert Klemme]

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

Whups, never mind, that doesn't work.

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

 

[Linus Sellberg]

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

 

[KONTRA Gergely]

Whups, never mind, that doesn't work.

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

Gergo

 

[Dave Brown]

: > > Whups, never mind, that doesn't work.
: >
: > 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]

--Dave

 

[Hal Fulton]

: > > Whups, never mind, that doesn't work.
: >
: > 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]

"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

 

[Dave Brown]

: > In article <[email protected]>,
: > : On 0113, Robert Klemme wrote:
: > : > > Whups, never mind, that doesn't work.
: > : >
: > : > 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]
:
: "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

 

[Robert Klemme]

: > In article <[email protected]>,
: > : On 0113, Robert Klemme wrote:
: > : > > Whups, never mind, that doesn't work.
: > : >
: > : > 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]
:
: "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