I cannot seem to figure out a way to do Scheme's cons boxes in Ruby (it seems its pretty much all arrays). This is a pretty rough outline:
class cons
def initialize (car, cdr)
@car = car
@cdr = cdr
end
#return the car of the pair
def car
return @car
end
#return the cdr of the pair
def cdr
return @cdr
end
end
I can pass two values and call the car and cdr, but this is not a list of any sort (just two values). How do I make a list on which I can insert something as in Scheme cons:
myCons = (cons(1, cons(2, cons(3, cons(4, 5)))))
The closest I can find is making my own array like myArray = Array[1, 2, 3, 4, 5] and then using puts myArray.join(' '). This only gives me "1 2 3 4 5" and not (1 2 3 4 5) though, and that's not taking into account I still can't actually build the array with cons, I simply made it myself.
Here's an implementation of Cons that has a decent print syntax built-in (including support for improper lists), and is enumerable:
class Cons
include Enumerable
attr_accessor :car, :cdr
class << self
alias [] new
end
def initialize(car, cdr)
self.car = car
self.cdr = cdr
end
def each_pair
return to_enum(:each_pair) unless block_given?
cell = self
while cell.is_a? Cons
yield cell.car, cell.cdr
cell = cell.cdr
end
end
def each
return to_enum unless block_given?
each_pair { |car,| yield car }
end
def print
sb = '('
each_pair do |car, cdr|
sb << yield(car)
case cdr
when Cons
sb << ' '
when nil
else
sb << ' . ' << yield(cdr)
end
end
sb << ')'
end
def to_s
print &:to_s
end
def inspect
print &:inspect
end
end
Oh, and here's an easy way to create a list (similar to the list function found in both Common Lisp and Scheme):
def list(*items)
items.reverse_each.reduce(nil) { |result, item| Cons[item, result] }
end
Examples:
irb(main):001:0> a = Cons[1, Cons[2, Cons[3, nil]]]
=> (1 2 3)
irb(main):002:0> b = Cons[1, Cons[2, Cons[3, 4]]]
=> (1 2 3 . 4)
irb(main):003:0> a.to_a
=> [1, 2, 3]
irb(main):004:0> a.map(&Math.method(:sqrt))
=> [1.0, 1.4142135623730951, 1.7320508075688772]
irb(main):005:0> list(1, 2, 3, 4, 5)
=> (1 2 3 4 5)
Update: A user wrote me asking how to (among other things) append cons-based lists. As a Schemer, I like to treat cons cells as immutable, so the standard approach for appending is to cons each element, right-to-left, from the left-hand list onto the right-hand list. Here's how I would implement it.
First, let's define a reduce_right method. (Technically, this is a right fold, not a right reduce, but Ruby prefers the term "reduce" rather than "fold", so that's what I'll use here.) We'll reopen both NilClass and Cons to make this work:
class NilClass
def reduce_right(init)
init
end
end
class Cons
def reduce_right(init, &block)
block.call(cdr.reduce_right(init, &block), car)
end
end
Then, append is as simple as using reduce_right:
def append(lhs, rhs)
lhs.reduce_right(rhs) { |result, item| Cons[item, result] }
end
This allows you to append two lists, but usually, it's more handy to allow appending any number of lists (and this is what Scheme's append allows):
def append(*lists)
lists.reverse_each.reduce do |result, list|
list.reduce_right(result) { |cur, item| Cons[item, cur] }
end
end
Notice that in both cases, the rightmost "list" is not required to be a proper list, and you can create improper lists by putting something that's not a cons cell there:
irb(main):001:0> append(list(1, 2, 3), list(4, 5))
=> (1 2 3 4 5)
irb(main):002:0> append(list(1, 2, 3), list(4, 5), 6)
=> (1 2 3 4 5 . 6)
irb(main):003:0> append(list(1, 2, 3), list(4, 5), list(6))
=> (1 2 3 4 5 6)
(Non-rightmost lists must be proper lists.)
You can declare a method (to_a) which will build your array:
class Cons
def initialize(car, cdr)
@car = car
@cdr = cdr
end
attr_reader :car, :cdr
def to_a
list = cdr.respond_to?(:to_a) ? cdr.to_a : cdr
[car, *list]
end
end
myCons = Cons.new(1, Cons.new(2, Cons.new(3, Cons.new(4,5))))
myCons.to_a
# => [1, 2, 3, 4, 5]
This method checks if cdr supports to_a itself, and calls it if possible, then it adds car to the beginning of the list, and returns the created list.
If you want to have a syntax similar to cons(1, cons(2,...) you can do it using []:
class Cons
def self.[](car, cdr)
Cons.new(car, cdr)
end
end
Now you can write:
myCons = Cons[1, Cons[2, Cons[3, Cons[4,5]]]]
Or a more curious approach from SICP :)
def cons(a, b)
lambda { |seek|
seek == 0 ? a : b
}
end
def car(pair)
pair.call(0)
end
def cdr(pair)
pair.call(1)
end
