SICP Chapter #02 Examples in Ruby
# Functions defined in previous chapters #
def gcd(a, b)
if (b == 0) then
a
else
gcd(b, a % b)
end
end
def fib(n)
if (n == 0) then
0
elsif (n == 1) then
1
else
fib(n - 1) + fib(n - 2)
end
end
def identity(x) x end
# utility functions #
def putx(s)
def puty(s)
if (s.kind_of?(Array)) then
print "["
s.each{|i| puty i; print ","}
print "]"
else
print s
end
end
puty(s)
print "\n"
end
def min(x, y) if x <= y then x else y end end
def max(x, y) if x >= y then x else y end end
# 2 Building Abstractions with Data
def linear_combination(a, b, x, y)
a*x + b*y
end
def mul(a, b) a * b end
def linear_combination(a, b, x, y)
mul(a, x) + mul(b, y)
end
# 2.1.1 Introduction to Data Abstraction - Example: Arithmetic Operations for CRational Numbers
# Literal Translation #
def make_rat(n, d) [n, d] end
def numer(xs) xs[0] end
def denom(xs) xs[1] end
def add_rat(x, y)
make_rat(numer(x)*denom(y) + numer(y)*denom(x), denom(x)*denom(y))
end
def sub_rat(x, y)
make_rat(numer(x)*denom(y) - numer(y)*denom(x), denom(x)*denom(y))
end
def mul_rat(x, y)
make_rat(numer(x)*numer(y), denom(x)*denom(y))
end
def div_rat(x, y)
make_rat(numer(x)*denom(y), denom(x)*numer(y))
end
def equal_rat(x, y)
numer(x)*denom(y) == numer(y)*denom(x)
end
def cons(x, y) [x, y] end
def car(xs) xs[0] end
def cdr(xs) xs[1] end
x = cons(1, 2)
puts car(x)
puts cdr(x)
x = cons(1, 2)
y = cons(3, 4)
z = cons(x, y)
puts car(car(z))
puts car(cdr(z))
putx z
#footnote # alternative definitions
def make_rat(x, y) cons(x, y) end
def numer(xs) car(xs) end
def denom(xs) cdr(xs) end
x = [1, 2]
y = [3, 4]
puts numer(x)
puts denom(x)
def compose(f, g) lambda{|x| f.call(g(x)) } end
def print_rat(x)
puts String(numer(x)) + "/" + String(denom(x))
end
one_half = make_rat(1,2)
print_rat(one_half)
one_third = make_rat(1, 3)
print_rat(add_rat(one_half, one_third))
print_rat(mul_rat(one_half, one_third))
print_rat(add_rat(one_third, one_third))
# reducing to lowest terms in constructor
def make_rat(n, d)
g = gcd(n, d)
[n / g, d / g]
end
def add_rat(x, y)
make_rat(numer(x)*denom(y) + numer(y)*denom(x), denom(x)*denom(y))
end
print_rat(add_rat(one_third, one_third))
# end Literal Translation #
# Object Translation #
class CRational
attr :numer
attr :denom
def initialize(n, d)
@numer = n
@denom = d
end
def add_rat(y)
CRational.new(@numer*y.denom + y.numer*@denom, @denom*y.denom)
end
def sub_rat(y)
CRational.new(@numer*y.denom - y.numer*@denom, @denom*y.denom)
end
def mul_rat(y)
CRational.new(@numer*y.numer, @denom*y.denom)
end
def div_rat(y)
CRational.new(@numer*y.denom, @denom*y.numer)
end
def equal_rat(y)
@numer*y.denom == y.numer * @denom
end
def print_rat
puts String(@numer) + "/" + String(@denom)
end
end
one_half = CRational.new(1, 2)
one_half.print_rat
one_third = CRational.new(1, 3)
one_half.add_rat(one_third).print_rat
one_half.mul_rat(one_third).print_rat
one_third.add_rat(one_third).print_rat
# reducing to lowest terms in constructor
class CRational
attr :numer
attr :denom
def initialize(n, d)
g = gcd(n, d)
@numer = n / g
@denom = d / g
end
def add_rat(y)
CRational.new(@numer*y.denom + y.numer*@denom, @denom*y.denom)
end
def sub_rat(y)
CRational.new(@numer*y.denom - y.numer*@denom, @denom*y.denom)
end
def mul_rat(y)
CRational.new(@numer*y.numer, @denom*y.denom)
end
def div_rat(y)
CRational.new(@numer*y.denom, @denom*y.numer)
end
def equal_rat(y)
@numer*y.denom == y.numer * @denom
end
def print_rat
puts String(@numer) + "/" + String(@denom)
end
end
one_third = CRational.new(1, 3)
one_third.print_rat
one_third.add_rat(one_third).print_rat
# end Object Translation #
# Exercise 2.1
def make_rat(n, d)
if (d < 0 and n < 0) or n < 0 then
[d * -1, n * -1]
else
[d, n]
end
end
# 2.1.2 Introduction to Data Abstraction - Abstraction barriers
# Literal Translation #
# reducing to lowest terms in selectors
def make_rat(n, d) [n, d] end
def numer(x)
g = gcd(x[0], x[1])
x[0] / g
end
def denom(x)
g = gcd(x[0], x[1])
x[1] / g
end
# end Literal Translation #
# Object Translation #
# reducing to lowest terms in selectors
class CRational
attr :n
attr :d
def initialize(n, d)
@n = n
@d = d
end
def numer
g = gcd(@n, @d)
@n / g
end
def denom
g = gcd(@n, @d)
@d / g
end
def add_rat(y)
CRational.new(numer*y.denom + y.numer*denom, denom*y.denom)
end
def sub_rat(y)
CRational.new(numer*y.denom - y.numer*denom, denom*y.denom)
end
def mul_rat(y)
CRational.new(numer*y.numer, denom*y.denom)
end
def div_rat(y)
CRational.new(numer*y.denom, denom*y.numer)
end
def equal_rat(y)
numer*y.denom == y.numer * denom
end
def print_rat
puts String(numer) + "/" + String(denom)
end
end
# end Object Translation #
# Exercise 2.2
def make_point(x, y) [x, y] end
def x_point(point) point[0] end
def y_point(point) point[1] end
def make_segment(start_segment, end_segment)
[start_segment, end_segment]
end
def start_segment(segment) segment[0] end
def end_segment(segment) segment[1] end
def midpoint_segment(segment)
s = segment.start_segment
e = segment.end_segment
make_point((s.x + e.x) / 2.0, (s.y + e.y) / 2.0)
end
def print_point(p)
puts string.format("(%d,%d)", p.x, p.y)
end
# Exercise 2.3
def square(x) x * x end
def length_segment(segment)
s = start_segment(segment)
e = end_segment(segment)
Math.sqrt(square(x_point(e) - x_point(s)) + square(y_point(e) - y_point(s)))
end
# Constructors create type tagged using
def make_rectangle_axy(anchor, xlen, ylen)
["axy", anchor, xlen, ylen]
end
def make_rectangle_seg(start_segment, end_segment)
["seg", start_segment, end_segment]
end
def is_axy(rect) rect[0] == "axy" end
def is_seg(rect) rect[0] == "seg" end
# 'length_rectangle' and 'width_rectangle' act as an abstraction barrier for higher-level
# procedures because 'rectangle' implementation details are buried here, and should the
# implementation change, only these procedures will need to be altered to support the change
def length_rectangle(rect)
if is_axy(rect) then
0 # Compute length ...
elsif is_seg(rect) then
0 # Compute length ...
end
end
def width_rectangle(rect)
# As per 'length_rectangle' except that rectangle width is returned ...
0
end
# High-level procedures are quarantined from representation / implementation details
def area_rectangle(rect)
length_rectangle(rect) * width_rectangle(rect)
end
def perimeter_rectangle(rect)
length_rectangle(rect) * 2 + width_rectangle(rect) * 2
end
# 2.1.3 Introduction to Data Abstraction - What is meant by data?
def cons(x, y)
dispatch = lambda{|m|
if (m == 0) then
x
elsif (m == 1) then
y
else
raise Exception.new("Argument not 0 or 1 -- CONS " + String(m))
end
}
dispatch
end
def car(z) z.call(0) end
def cdr(z) z.call(1) end
# Exercise 2.4
def cons(x, y)
lambda{|m| m.call(x, y)}
end
def car(z)
z.call(lambda{|p, q| p})
end
def cdr(z)
z.call(lambda{|p, q| q})
end
# Exercise 2.5
def cons(x, y)
2 ** (x * (3 ** y))
end
def car(z)
if z % 2 == 0 then
car((z / 2) + 1)
else
0
end
end
def cdr(z)
if z % 3 == 0 then
cdr((z / 3) + 1)
else
0
end
end
xxx = cons(2, 3)
puts "need to fix this one???"
puts xxx
puts car(xxx)
puts cdr(xxx)
# Exercise 2.6
zero = lambda{|f| lambda{|x| x}}
def add1(n)
lambda{|f| lambda{|x| f.call((n.call(f)).call(x))}}
end
# 2.1.4 Introduction to Data Abstraction - Extended Exercise: Interval Arithmetic
# Literal Translation #
def make_interval(a, b) [a, b] end
def lower_bound(p) return p[0] end
def upper_bound(p) return p[1] end
def add_interval(x, y)
make_interval(lower_bound(x) + lower_bound(y), upper_bound(x) + upper_bound(y))
end
def mul_interval(x, y)
p1 = lower_bound(x) * lower_bound(y)
p2 = lower_bound(x) * upper_bound(y)
p3 = upper_bound(x) * lower_bound(y)
p4 = upper_bound(x) * upper_bound(y)
make_interval(
min(min(p1, p2), min(p3, p4)),
max(max(p1, p2), max(p3, p4)))
end
def div_interval(x, y)
z = make_interval(1.0 / upper_bound(y), 1.0 / lower_bound(y))
mul_interval(x, z)
end
def make_center_width(c, w)
make_interval(c-w, c+w)
end
def center(interval)
(lower_bound(interval) + upper_bound(interval)) / 2.0
end
def width(interval)
(upper_bound(interval) - lower_bound(interval)) / 2.0
end
# parallel resistors
def par1(r1, r2)
div_interval(mul_interval(r1, r2), add_interval(r1, r2))
end
def par2(r1, r2)
one = make_interval(1, 1)
div_interval(one,
add_interval(div_interval(one, r1),
div_interval(one, r2)))
end
# end Literal Translation #
# Object Translation #
class Interval
attr :lower_bound
attr :upper_bound
def initialize(lower_bound, upper_bound)
@lower_bound = lower_bound
@upper_bound = upper_bound
end
def add_interval(y)
Interval.new(@lower_bound + y.lower_bound, @upper_bound + y.upper_bound)
end
def mul_interval(y)
p1 = @lower_bound * y.lower_bound
p2 = @lower_bound * y.upper_bound
p3 = @upper_bound * y.lower_bound
p4 = @upper_bound * y.upper_bound
Interval.new(
min(min(p1, p2), min(p3, p4)),
max(max(p1, p2), max(p3, p4)))
end
def div_interval(y)
z = Interval.new(1.0 / y.upper_bound, 1.0 / y.lower_bound)
mul_interval(z)
end
def make_center_width(c, w)
Interval.new(c-w, c+w)
end
def center
(@lower_bound + @upper_bound) / 2.0
end
def width
(@upper_bound - @lower_bound) / 2.0
end
end
interval = Interval.new(10, 20)
# parallel resistors
def par1(r1, r2)
r1.mul_interval(r2).div_interval(r1.add_interval(r2))
end
def par2(r1, r2)
one = Interval.new(1, 1)
one.div_interval(one.div_interval(r1).add_interval(one.div_interval(r2)))
end
# end Object Translation #
# Exercise 2.8
def sub_interval(x, y)
make_interval(lower_bound(x) - lower_bound(y), upper_bound(x) - upper_bound(y))
end
# Exercise 2.9
i = make_interval(5, 10)
j = make_interval(15, 25)
# width of the sum (or difference) of two intervals *is* a function only of the widths of
# the intervals being added (or subtracted)
puts String(width(i)) + " " + String(width(j))
puts width(add_interval(i, j))
puts width(sub_interval(i, j))
# width of the product (or quotient) of two intervals *is not* a function only of the widths
# of the intervals being multiplied (or divided)
puts width(mul_interval(i, j))
puts width(div_interval(i, j))
# Exercise 2.10
def is_zero_interval(i)
i.lower_bound == 0 or i.upper_bound == 0
end
def div_interval_zero_check(x, y)
if is_zero_interval(y) then
raise Exception.new("Zero interval divisor")
else
div_interval(x, y)
end
end
# Exercise 2.12
def make_center_percent(c, p)
make_center_width(c, p * c / 100.0)
end
def percent(i)
width(i) / center(i) * 100.0
end
# 2.2.1 Hierarchical Data and the Closure Property - Representing Sequences
one_through_four = [1, 2, 3, 4]
putx one_through_four
puts one_through_four[0]
puts one_through_four[1..-1]
puts one_through_four[1]
putx one_through_four[0..-1].unshift(10) # note: Ruby unshift modifies state (make slice copy)
putx one_through_four
def list_ref(items, n)
items[n]
end
squares = [1, 4, 9, 16, 25]
puts list_ref(squares, 3)
def length(items)
items.length
end
odds = [1, 3, 5, 7]
puts odds.length
def append(xs, ys)
rt = xs[0..-1]
ys.each{|value| rt.push(value)}
rt
end
putx append(squares, odds)
putx append(odds, squares)
# Mapping over lists
def scale_list(factor, xs)
rt = []
xs.each{|value| rt.push(value * factor)}
rt
end
putx scale_list(10, [1, 2, 3, 4, 5])
# uncurried version of map
def map(proc, xs)
rt = []
xs.each{|value| rt.push(proc.call(value))}
rt
end
putx map(lambda{|x| x.abs}, [-10, 2.5, -11.6, 17])
putx map(lambda{|x| x * x}, [1, 2, 3, 4])
def scale_list(factor, items)
map(lambda{|x| x * factor}, items)
end
putx scale_list(10, [1, 2, 3, 4, 5])
# curried version map
def mapc(proc)
map_lambda = lambda{|xs|
rt = []
xs.each{|value| rt.push(proc.call(value))}
rt
}
map_lambda
end
putx mapc(lambda{|x| x.abs}).call([-10, 2.5, -11.6, 17])
putx mapc(lambda{|x| x * x}).call([1, 2, 3, 4])
def scale_list(factor, items)
mapc(lambda{|x| x * factor}).call(items)
end
putx scale_list(10, [1, 2, 3, 4, 5])
# Exercise 2.17
def last_pair(xs)
[xs[-1]]
end
putx last_pair([23, 72, 149, 34])
# Exercise 2.18
def reverse(xs)
rt = []
(xs.length-1).downto(0) {|i| rt.push(xs[i]) }
rt
end
putx reverse([1, 4, 9, 16, 25])
# Exercise 2.19
def no_more(xs)
xs.length == 0
end
def except_first_denomination(coin_values)
tail = coin_values[1..-1]
tail
end
def first_denomination(coin_values)
head = coin_values[0]
head
end
def cc(amount, coin_values)
if (amount == 0) then
1
elsif ((amount < 0) or (no_more(coin_values))) then
0
else
cc(amount, except_first_denomination(coin_values)) +
cc(amount - first_denomination(coin_values), coin_values)
end
end
us_coins = [50, 25, 10, 5, 1]
uk_coins = [100, 50, 20, 10, 5, 2, 1, 0.5]
puts cc(100, us_coins)
# works but takes a long time based on inefficiency above (tail slicing)
# puts cc(100, uk_coins)
# Exercise 2.20
def filter(predicate, xs)
rt = []
xs.each{|value|
if predicate.call(value) then
rt.push(value)
end}
rt
end
def is_odd(n) n % 2 == 1 end
def is_even(n) not(is_odd(n)) end
def same_parity(xs)
head = xs[0]
tail = xs[1..-1]
predicate = if is_odd(head) then lambda{|n| is_odd(n)} else lambda{|n| is_even(n)} end
filter(predicate, tail)
end
putx same_parity([1, 2, 3, 4, 5, 6, 7])
putx same_parity([2, 3, 4, 5, 6, 7])
# Exercise 2.21
def square_list(xs)
rt = []
xs.each{|value| rt.push(value * value)}
rt
end
putx square_list([1, 2, 3, 4])
def square_list(xs)
map(lambda{|x| x * x}, xs)
end
putx square_list([1, 2, 3, 4])
# Exercise 2.23
def for_each(f, xs)
xs.each{|value| f(value)}
end
# 2.2.2 Hierarchical Data and the Closure Property - Hierarchical Structures
def count_leaves(xs)
n = 0
xs.each{|value|
if value.kind_of?(Array) then
n = n + count_leaves(value)
else
n = n + 1
end}
n
end
x = [[1, 2], [3, 4]]
puts x.length
puts count_leaves(x)
putx [x, x]
puts [x, x].length
puts count_leaves([x, x])
# Mapping over trees
def scale_tree(factor, xs)
rt = []
xs.each{|value|
if value.kind_of?(Array) then
rt.push(scale_tree(factor, value))
else
rt.push(factor * value)
end}
rt
end
putx scale_tree(10, [1, [2, [3, 4], 5], [6, 7]])
def scale_tree(factor, xs)
map(
lambda{|sub_tree|
if sub_tree.kind_of?(Array) then
scale_tree(factor, sub_tree)
else
sub_tree * factor
end},
xs)
end
putx scale_tree(10, [1, [2, [3, 4], 5], [6, 7]])
# Exercise 2.24
putx [1, [2, [3, 4]]]
# Exercise 2.25
putx [1, 3, [5, 7], 9]
putx [[7]]
putx [1, [2, [3, [4, [5, [6, 7]]]]]]
# Exercise 2.26
x = [1, 2, 3]
y = [4, 5, 6]
putx append(x, y)
putx [x, y]
# Exercise 2.27
def deep_reverse(xs)
rt = []
(xs.length-1).downto(0) {|i|
if xs[i].kind_of?(Array) then
rt.push(deep_reverse(xs[i]))
else
rt.push(xs[i])
end}
rt
end
x = [[1, 2], [3, 4]]
putx x
putx reverse(x)
putx deep_reverse(x)
# Exercise 2.28
def fringe(xs)
rt = []
xs.each{|value|
if value.kind_of?(Array) then
fringe(value).each{|fval| rt.push(fval)}
else
rt.push(value)
end}
rt
end
x = [[1, 2], [3, 4]]
putx (fringe(x))
putx (fringe([x, x]))
# Exercise 2.29
# List-based representation
# a.
def make_mobile(left, right) [left, right] end
def make_branch(length, struc) [length, struc] end
def left_branch(mobile) mobile[0] end
def right_branch(mobile) mobile[1] end
def branch_length(branch) branch[0] end
def branch_structure(branch) branch[1] end
# Helpers for b. and c.
def branch_weight(branch)
if len(branch) == 0 then
0
elsif branch.kind_of?(Array) then
branch_weight(branch_structure(branch))
else
branch_structure(branch)
end
end
def total_branch_length(branch)
if len(branch) == 0 then
0
elsif branch.kind_of?(Array) then
branch_length(branch) + total_branch_length(branch_structure(branch))
else
branch_length(branch)
end
end
# b.
def total_weight(mobile)
branch_weight(left_branch(mobile)) + branch_weight(right_branch(mobile))
end
# c. [Not as per specification]
def is_mobile_balanced(mobile)
lmwl = total_branch_length(left_branch(mobile)) * branch_weight(left_branch(mobile))
rmwl = total_branch_length(right_branch(mobile)) * branch_weight(right_branch(mobile))
lmwl == rmwl
end
# Exercise 2.30
def square_tree(xs)
rt = []
xs.each{|value|
if value.kind_of?(Array) then
rt.push(square_tree(value))
else
rt.push(value*value)
end}
rt
end
putx square_tree([1, [2, [3, 4], 5], [6, 7]])
# Exercise 2.31
def tree_map(xs, proc)
rt = []
xs.each{|value|
if value.kind_of?(Array) then
rt.push(tree_map(value, proc))
else
rt.push(proc.call(value))
end}
rt
end
def square_tree(xs)
tree_map(xs, lambda{|x| x * x})
end
putx square_tree([1, [2, [3, 4], 5], [6, 7]])
# Exercise 2.32
def subsets(xs)
if (xs.length == 0) then
[[]]
else
begin
head = xs[0]
tail = xs[1..-1]
rest = subsets(tail)
append(rest, map(lambda{|x| append([head], x)}, rest))
end
end
end
putx subsets([1, 2, 3])
# 2.2.3 Hierarchical Data and the Closure Property - Sequences as Conventional Interfaces
def is_odd(n) n % 2 == 1 end
def is_even(n) not(is_odd(n)) end
def square(x) x * x end
def sum_odd_squares(xs)
sum = 0
xs.each{|value|
if value.kind_of?(Array) then
sum += sum_odd_squares(value)
elsif
is_odd(value) then sum += square(value)
end}
sum
end
def even_fibs(n)
rt = []
for i in 1..n
f = fib(i)
if is_even(f) then
rt.push(f)
end
end
rt
end
putx even_fibs(10)
# Sequence operations
putx map(lambda{|x| square(x)}, [1,2,3,4,5])
# non-curried version of filter
def filter(predicate, xs)
rt = []
xs.each{|value|
if predicate.call(value) then
rt.push(value)
end}
rt
end
putx filter(lambda{|x| is_odd(x)}, [1,2,3,4,5])
# curried version of filter
def filterc(predicate)
filter_lambda = lambda{|xs|
rt = []
xs.each{|value|
if predicate.call(value) then
rt.push(value)
end}
rt}
filter_lambda
end
putx filterc(lambda{|x| is_odd(x)}).call([1,2,3,4,5])
# non-curried version of accumulate (aka foldl)
def accumulate(oper, initial, xs)
rt = initial
xs.each{|value| rt = oper.call(value, rt)}
rt
end
def construct(x, items)
rt = items[0..-1]
rt.push(x)
rt
end
puts accumulate(lambda{|x,y| x+y}, 0, [1,2,3,4,5])
puts accumulate(lambda{|x,y| x*y}, 1, [1,2,3,4,5])
putx accumulate(lambda{|x,y| y.push(x)}, [], [1,2,3,4,5])
# curried version of accumulate (aka foldl)
def accumulatec(oper)
initial_lambda = lambda{|initial|
sequence_lambda = lambda{|xs|
rt = initial
xs.each{|value| rt = oper.call(value, rt)}
rt}
sequence_lambda}
initial_lambda
end
puts accumulatec(lambda{|x,y| x+y}).call(0).call([1,2,3,4,5])
puts accumulatec(lambda{|x,y| x*y}).call(1).call([1,2,3,4,5])
putx accumulatec(lambda{|x,y| y.push(x)}).call([]).call([1,2,3,4,5])
def enumerate_interval(low, high)
rt = []
for i in low..high
rt.push(i)
end
rt
end
putx enumerate_interval(2,7)
def enumerate_tree(xs)
rt = []
xs.each{|value|
if value.kind_of?(Array) then
enumerate_tree(value).each{|value2| rt.push(value2)}
elsif
rt.push(value)
end}
rt
end
putx enumerate_tree([1, [2, [3, 4], 5]])
def sum_odd_squares(tree)
accumulate(lambda{|x,y| x+y},0, map(square, filter(is_odd, enumerate_tree(tree))))
end
def even_fibs(n)
accumulate(
lambda{|x,y| y.push(x)},
[],
filter(lambda{|x| is_even(x)},
map(lambda{|x| fib(x)},
enumerate_interval(0, n))))
end
putx even_fibs(10)
def list_fib_squares(n)
accumulate(
lambda{|x,y| y.push(x)},
[],
map(lambda{|x| square(x)},
map(lambda{|x| fib(x)},
enumerate_interval(0, n))))
end
putx list_fib_squares(10)
def product_of_squares_of_odd_elements(sequence)
accumulate(
lambda{|x,y| x*y},
1,
map(lambda{|x| square(x)},
filter(lambda{|x| is_odd(x)}, sequence)))
end
puts product_of_squares_of_odd_elements([1,2,3,4,5])
class Employee
attr_accessor :empname
attr_accessor :jobtitle
attr_accessor :salary
def initialize(empname, jobtitle, salary)
@empname = empname
@jobtitle = jobtitle
@salary = salary
end
def isProgrammer()
(@jobtitle == "Programmer")
end
def getSalary()
@salary
end
end
def salary_of_highest_paid_programmer(records)
accumulate(
lambda{|x,y| if (x>y) then x else y end},
0,
map(lambda{|x| x.getSalary()},
filter(lambda{|x| x.isProgrammer()}, records)))
end
recs = [Employee.new(empname="Fred", jobtitle="Programmer", salary=180),
Employee.new(empname="Hank", jobtitle="Programmer", salary=150)]
putx salary_of_highest_paid_programmer(recs)
# Nested mappings
n = 5 # book doesn't define n
putx accumulate(lambda{|x,y| append(x, y)},
[],
map(lambda{|i| map(lambda{|j| [i,j]}, enumerate_interval(1, i-1))},
enumerate_interval(1, n)))
def flatmap(proc)
lambda{|seq|
accumulate(
lambda{|x,y| append(x, y)},
[],
map(proc, seq)) }
end
def has_no_divisors(n, c)
if c == 1 then
true
elsif n % c == 0 then
false
else
has_no_divisors(n, c-1)
end
end
def is_prime(n)
has_no_divisors(n, n-1)
end
def prime_sum(pair)
is_prime(pair[0] + pair[1])
end
def make_pair_sum(pair)
[pair[0], pair[1], pair[0] + pair[1]]
end
def prime_sum_pairs(n)
map(lambda{|x| make_pair_sum(x)},
filter(
lambda{|x| prime_sum(x)},
flatmap(lambda{|i| map(lambda{|j| [i,j]}, enumerate_interval(1, i-1))}).call(
enumerate_interval(1, n))))
end
putx prime_sum_pairs(15)
def remove(item, sequence)
filter(lambda{|x| x != item}, sequence)
end
def permutations(xs)
if xs.length == 0 then
[[]]
else
flatmap(lambda{|x| map(lambda{|a| append(a, [x])}, permutations(remove(x, xs)))}).call(xs)
end
end
putx (permutations([1,2,3]))
# Exercise 2.34
# exercise left to reader to define appropriate functions
# def horner_eval(x, coefficient_sequence)
# accumulate(lambda{|this_coeff, higher_terms| ??FILL_THIS_IN??}, 0, coefficient_sequence)
# end
# horner_eval(2, [1,3,0,5,0,1]))
# Exercise 2.36
# exercise left to reader to define appropriate functions
# def accumulate_n(oper, initial, sequence)
# if sequence.length == 0 then
# initial
# else
# [accumulate(oper, init, ??FILL_THIS_IN??),
# accumulate_n(oper, init, ??FILL_THIS_IN??)]
# end
# end
# accumulate_n(lambda{|x,y| x + y}, 0, s)
# Exercise 2.38
def fold_right(oper, initial, xs)
accumulate(oper, initial, xs)
end
def fold_left(oper, initial, xs)
rt = initial
xs.reverse.each{|value| rt = oper.call(rt, value)}
rt
end
puts fold_right(lambda{|x,y| Float(y)/x}, 1, [1,2,3])
puts fold_left(lambda{|x,y| Float(y)/x}, 1, [1,2,3])
putx fold_right(lambda{|x,y| y.push(x)}, [], [1,2,3])
putx fold_left(lambda{|x,y| x.push(y)}, [], [1,2,3])
# Exercise 2.42
# exercise left to reader to define appropriate functions
# def queens(board_size)
# queen_cols = lambda{|k|
# if k == 0 then
# [empty_board]
# else
# filter(
# lambda{|positions| isSafe(k, positions)},
# flatmap(
# lambda{|rest_of_queens|
# map(
# lambda{|new_row| adjoin_position(new_row, k, rest_of_queens)},
# enumerate_interval(1, board_size))},
# queen_cols.call(k-1)))
# end
# }
# queen_cols.call(board_size)
# end
# Exercise 2.43
# exercise left to reader to define appropriate functions
# def queens(board_size)
# queen_cols = lambda{|k|
# if k == 0 then
# [empty_board]
# else
# filter(
# lambda{|positions| isSafe(k, positions)},
# flatmap(
# lambda{|new_row|
# map(
# lambda{|rest_of_queens| adjoin_position(new_row, k, rest_of_queens)},
# queen_cols.call(k-1))},
# enumerate_interval(1, board_size)))
# end
# }
# queen_cols.call(board_size)
# end
# 2.2.4 Hierarchical Data and the Closure Property - Example: a picture language
def draw_line(x, y) end
def wave(xframe) xframe end
class Vect
attr_accessor :x
attr_accessor :y
def initialize(x, y)
@x = x
@y = y
end
end
def make_vect(x, y) Vect.new(x, y) end
def xcor_vect(v) v.x end
def ycor_vect(v) v.y end
def add_vect(v1, v2)
make_vect(xcor_vect(v1) + xcor_vect(v2), ycor_vect(v1) + ycor_vect(v2))
end
def sub_vect(v1, v2)
make_vect(xcor_vect(v1) - xcor_vect(v2), ycor_vect(v1) - ycor_vect(v2))
end
def scale_vect(s, v)
make_vect(s * xcor_vect(v), s * ycor_vect(v))
end
class Frame
attr_accessor :orig
attr_accessor :edge1
attr_accessor :edge2
def initialize(orig, edge1, edge2)
@orig = orig
@edge1 = edge1
@edge2 = edge2
end
end
def make_frame(origin, edge1, edge2)
Frame.new(origin, edge1, edge2)
end
def origin_frame(f) f.orig() end
def edge1_frame(f) f.edge1() end
def edge2_frame(f) f.edge2() end
a_frame = make_frame(make_vect(0.0, 0.0), make_vect(1.0, 0.0), make_vect(0.0, 1.0))
class Segment
attr_accessor :x
attr_accessor :y
def initialize(x, y)
@x = x
@y = y
end
end
def start_segment(seg) seg.x end
def end_segment(seg) seg.x end
# Frames #
def frame_coord_map(xframe, v)
add_vect(
origin_frame(xframe),
add_vect(scale_vect(xcor_vect(v), edge1_frame(xframe)),
scale_vect(ycor_vect(v), edge2_frame(xframe))))
end
frame_coord_map(a_frame, make_vect(0.0, 0.0))
origin_frame(a_frame)
# Painters #
def foreach(f)
foreach_lambda = lambda{|xs|
if (xs == nil) then
()
else
f.call(xs[0])
foreach(f).call(xs[1..-1])
end
}
foreach_lambda
end
def segments_painter(segment_list, xframe)
foreach(
lambda{|segment|
draw_line(frame_coord_map(xframe).call(start_segment, segment),
frame_coord_map(xframe).call(end_segment, segment))}).call(
segment_list)
end
def transform_painter(painter, origin, corner1, corner2)
transform_painter_lambda = lambda{|xframe|
m = frame_coord_map(xframe)
new_origin = m(origin)
painter(
make_frame(
new_origin,
sub_vect(m(corner1), new_origin),
sub_vect(m(corner2), new_origin)))
}
transform_painter_lambda
end
def flip_vert(painter)
transform_painter(
painter,
make_vect(0.0, 1.0),
make_vect(1.0, 1.0),
make_vect(0.0, 0.0))
end
def flip_horiz(painter)
transform_painter(
painter,
make_vect(1.0, 0.0),
make_vect(0.0, 0.0),
make_vect(1.0, 1.0))
end
def shrink_to_upper_right(painter)
transform_painter(
painter,
make_vect(0.5, 0.5),
make_vect(1.0, 0.5),
make_vect(0.5, 1.0))
end
def rotate90(painter)
transform_painter(
painter,
make_vect(1.0, 0.0),
make_vect(1.0, 1.0),
make_vect(0.0, 0.0))
end
def rotate180(painter)
transform_painter(
painter,
make_vect(1.0, 1.0),
make_vect(0.0, 1.0),
make_vect(1.0, 0.0))
end
def squash_inwards(painter)
transform_painter(
painter,
make_vect(0.0, 0.0),
make_vect(0.65, 0.35),
make_vect(0.35, 0.65))
end
def beside(painter1, painter2)
beside_lambda = lambda{|xframe|
split_point = make_vect(0.5, 0.0)
paint_left = (
transform_painter(
painter1,
make_vect(0.0, 0.0),
split_point,
make_vect(0.0, 1.0)))
paint_right = (
transform_painter(
painter2,
split_point,
make_vect(1.0, 0.0),
make_vect(0.5, 1.0)))
paint_left.call(xframe)
paint_right.call(xframe)
}
beside_lambda
end
def below(painter1, painter2)
below_lambda = lambda{|xframe|
split_point = make_vect(0.0, 0.5)
paint_below = (
transform_painter(
painter1,
make_vect(0.0, 0.0),
make_vect(1.0, 0.0),
split_point))
paint_above = (
transform_painter(
painter2,
split_point,
make_vect(1.0, 0.5),
make_vect(0.0, 1.0)))
paint_below(xframe)
paint_above(xframe)
}
below_lambda
end
def up_split(painter, n)
if (n == 0) then
painter
else
smaller = up_split(painter, n-1)
below(painter, beside(smaller, smaller))
end
end
wave2 = beside(lambda{|frame| wave(frame)}, flip_vert(lambda{|frame| wave(frame)}))
wave4 = below(wave2, lambda{|frame| wave(frame)})
def flipped_pairs(painter)
painter2 = beside(painter, flip_vert(painter))
below(painter2, painter2)
end
wave4 = flipped_pairs(lambda{|frame| wave(frame)})
def right_split(painter, n)
if (n == 0) then
painter
else
smaller = right_split(painter, n-1)
beside(painter, below(smaller, smaller))
end
end
def corner_split(painter, n)
if (n == 0) then
painter
else
up = up_split(painter, n-1)
right = right_split(painter, n-1)
top_left = beside(up, up)
bottom_right = below(right, right)
corner = corner_split(painter, n-1)
beside(below(painter, top_left), below(bottom_right, corner))
end
end
def square_limit(painter, n)
quarter = corner_split(painter, n)
half = beside(flip_horiz(quarter), quarter)
below(flip_vert(half), half)
end
# Higher_order operations #
def square_of_four(tleft, tright, bleft, bright)
square_of_four_lambda = lambda{|painter|
top = beside(tleft(painter), tright(painter))
bottom = beside(bright(painter), bright(painter))
below(bottom, top)
}
square_of_four_lambda
end
def flipped_pairs(painter)
combine4 = square_of_four(identity, flip_vert, identity, flip_vert)
combine4.call(painter)
end
# footnote #
flipped_pairs = square_of_four(
lambda{|x| identity(x)},
lambda{|x| flip_vert(x)},
lambda{|x| identity(x)},
lambda{|x| flip_vert(x)})
def square_limit(painter, n)
combine4 = square_of_four(flip_horiz, identity, rotate180, flip_vert)
combine4.call(corner_split(painter, n))
end
# Exercise 2.45 #
# exercise left to reader to define appropriate functions
# right_split = split(lambda{|x,y| beside(x,y)}, lambda{|x,y| below(x,y)})
# up_split = split(below, beside)
# Exercise 2.47 #
def make_frame(origin, edge1, edge2)
[origin, edge1, edge2]
end
def make_frame(origin, edge1, edge2)
[origin, [edge1, edge2]]
end
# 2.3.1 Symbolic Data - Quotation
# To Be Done.
# 2.3.2 Symbolic Data - Example: Symbolic Differentiation
class Sum
attr_accessor :add_end
attr_accessor :aug_end
def initialize(add_end, aug_end)
@add_end = add_end
@aug_end = aug_end
end
def to_s()
"Sum(" + String(@add_end) + ", " + String(@aug_end) + ")"
end
end
class Product
attr_accessor :multiplier
attr_accessor :multiplicand
def initialize(multiplier, multiplicand)
@multiplier = multiplier
@multiplicand = multiplicand
end
def to_s()
"Product(" + String(@multiplier) + ", " + String(@multiplicand) + ")"
end
end
def is_number(x)
x.kind_of?(Numeric)
end
def is_same_number(x, y)
is_number(x) and is_number(y) and (x == y)
end
def is_variable(x)
x.kind_of?(String)
end
def is_same_variable(x, y)
is_variable(x) and is_variable(y) and (x == y)
end
def is_sum(items)
items.kind_of?(Sum)
end
def is_product(items)
items.kind_of?(Product)
end
def make_sum(x, y)
if is_number(x) and is_number(y) then
x + y
else
Sum.new(x, y)
end
end
def make_product(x, y)
if is_number(x) and is_number(y) then
x * y
else
Product.new(x, y)
end
end
def add_end(items)
if is_sum(items) then
items.add_end
else
raise Exception.new("Invalid pattern match " + String(items))
end
end
def aug_end(items)
if is_sum(items) then
items.aug_end
else
raise Exception.new("Invalid pattern match " + String(items))
end
end
def multiplier(items)
if is_product(items) then
items.multiplier
else
raise Exception.new("Invalid pattern match " + String(items))
end
end
def multiplicand(items)
if is_product(items) then
items.multiplicand
else
raise Exception.new("Invalid pattern match " + String(items))
end
end
def deriv(exp, var)
if is_number(exp) then
0
elsif is_variable(exp) then
if is_same_variable(exp, var) then
1
else
0
end
elsif is_sum(exp) then
make_sum(deriv(add_end(exp), var),
deriv(aug_end(exp), var))
elsif is_product(exp) then
make_sum(make_product(multiplier(exp), deriv(multiplicand(exp), var)),
make_product(deriv(multiplier(exp), var), multiplicand(exp)))
else
raise Exception.new("Invalid expression " + str(exp))
end
end
# dx(x + 3) = 1
puts deriv(Sum.new('x', 3), 'x')
# # dx(x*y) = y
puts deriv(Product.new('x', 'y'), 'x')
# dx(x*y + x + 3) = y + 1
puts deriv(Sum.new(Sum.new(Product.new('x', 'y'), 'x'), 3), 'x')
# With simplification
def make_sum(x, y)
if is_number(x) and x == 0 then
y
elsif is_number(y) and y == 0 then
x
elsif is_number(x) and is_number(y) then
x + y
else
Sum.new(x, y)
end
end
def make_product(x, y)
if is_number(x)and x == 0 then
0
elsif is_number(y) and y == 0 then
0
elsif is_number(x) and x == 1 then
y
elsif is_number(y) and y == 1 then
x
elsif is_number(x) and is_number(y) then
x * y
else
Product.new(x, y)
end
end
def deriv(exp, var)
if is_number(exp) then
0
elsif is_variable(exp) then
if is_same_variable(exp, var) then
1
else
0
end
elsif is_sum(exp) then
make_sum(deriv(add_end(exp), var),
deriv(aug_end(exp), var))
elsif is_product(exp) then
make_sum(make_product(multiplier(exp), deriv(multiplicand(exp), var)),
make_product(deriv(multiplier(exp), var), multiplicand(exp)))
else
raise Exception.new("Invalid expression " + String(exp))
end
end
# dx(x + 3) = 1
puts deriv(Sum.new('x', 3), 'x')
# # dx(x*y) = y
puts deriv(Product.new('x', 'y'), 'x')
# dx(x*y + x + 3) = y + 1
puts deriv(Sum.new(Sum.new(Product.new('x', 'y'), 'x'), 3), 'x')
# 2.3.3 Symbolic Data - Example: Representing Sets
# unordered
def is_element_of_set(x, xs)
xs.each{|value|
if x == value then
return true
end}
false
end
def adjoin_set(x, xs)
if is_element_of_set(x, xs) then
xs
else
append([x], xs)
end
end
def intersection_set(xs, ys)
rt = []
xs.each{|value|
if is_element_of_set(value, ys) then
rt.push(value)
end}
rt
end
# ordered
def is_element_of_set(x, xs)
xs.each{|value|
if x == value then
return true
elsif x < value then
return false
end}
false
end
def intersection_set(xs, ys)
rt = []
i = 0
j = 0
while i < xs.length and j < ys.length do
if xs[i] == ys[j] then
rt.push(xs[i])
i = i + 1
j = j + 1
elsif xs[i] < ys[j] then
i = i + 1
else
j = j + 1
end
end
rt
end
class Node
attr_accessor :value
attr_accessor :left
attr_accessor :right
def initialize(value, left, right)
@value = value
@left = left
@right = right
end
def to_s()
"Node(" + String(@value) + ", " + String(@left) + ", " + String(@right) + ")"
end
end
def is_element_of_set(x, node)
if node == () then
false
else
if x == node.value then
true
elsif x < node.value then
is_element_of_set(x, node.left)
else
is_element_of_set(x, node.right)
end
end
end
puts is_element_of_set(3, Node.new(2, Node.new(1, (), ()), Node.new(3, (), ())))
def adjoin_set(x, node)
if node == () then
Node.new(x, (), ())
else
if x == node.value then
node
elsif x < node.value then
Node.new(node.value, adjoin_set(x, node.left), node.right)
else
Node.new(node.value, node.left, adjoin_set(x, node.right))
end
end
end
putx adjoin_set(3, Node.new(4, Node.new(2, (), ()), Node.new(6, (), ())))
# Exercise 2.63
def tree_to_list(node)
if node == () then
[]
else
append(tree_to_list(node.left),
append(
[node.value],
tree_to_list(node.right)))
end
end
putx tree_to_list(Node.new(4, Node.new(2, (), ()), Node.new(6, (), ())))
def tree_to_list(node)
def copy_to_list(node, xs)
if node == () then
xs
else
copy_to_list(node.left, append([node.value], copy_to_list(node.right, xs)))
end
end
copy_to_list(node, [])
end
putx tree_to_list(Node.new(4, Node.new(2, (), ()), Node.new(6, (), ())))
# Exercise 2.64
def partial_tree(elts, n)
if n == 0 then
{"foo"=>(), "bar"=>elts}
else
left_size = ((n-1) / 2.0).floor
right_size = n - (left_size + 1)
left_result = partial_tree(elts, left_size)
left_tree = left_result["foo"]
non_left_elts = left_result["bar"]
this_entry = non_left_elts[0]
right_result = partial_tree(non_left_elts[1..-1], right_size)
right_tree = right_result["foo"]
remaining_elts = right_result["bar"]
{"foo"=>Node.new(this_entry, left_tree, right_tree), "bar"=>remaining_elts}
end
end
def list_to_tree(elements)
result = partial_tree(elements, elements.length)
result["foo"]
end
putx list_to_tree([2, 4, 6])
# information retrieval
def lookup(given_key, items)
items.each{|key,value|
if given_key == key then
return items[given_key]
end}
()
end
puts lookup(2, {1=>'a', 2=>'b', 3=>'c'})
# 2.3.4 Symbolic Data - Example: Huffman Encoding Trees
class Leaf
attr_accessor :symbol
attr_accessor :weight
def initialize(symbol, weight)
@symbol = symbol
@weight = weight
end
def to_s()
"Leaf(" + String(@symbol) + ", " + String(@weight) + ")"
end
end
class Tree
attr_accessor :subsymbols
attr_accessor :weight
attr_accessor :left
attr_accessor :right
def initialize(subsymbols, weight, left, right)
@subsymbols = subsymbols
@weight = weight
@left = left
@right = right
end
def to_s()
"Tree(" + String(@symbol) + ", " + String(@weight) + ", " + String(@left) + ", " + String(@right) + ")"
end
end
def make_leaf(symbol, weight)
Leaf.new(symbol, weight)
end
def is_leaf(node)
node.kind_of?(Leaf)
end
def symbol_leaf(node)
if is_leaf(node) then
node.symbol
else
raise Exception.new("Invalid pattern match " + String(node))
end
end
def weight_leaf(node)
if is_leaf(node) then
node.weight
else
raise Exception.new("Invalid pattern match " + String(node))
end
end
def symbols(node)
if is_leaf(node) then
[node.symbol]
else
node.subsymbols
end
end
def weight(node)
node.weight
end
def make_code_tree(left, right)
return Tree.new(append(symbols(left), symbols(right)), weight(left) + weight(right), left, right)
end
def left_node(node)
if not(is_leaf(node)) then
node.left
else
raise Exception.new("Invalid pattern match " + String(node))
end
end
def right_node(node)
if not(is_leaf(node)) then
node.right
else
raise Exception.new("Invalid pattern match " + String(node))
end
end
def choose_node(n, node)
if n == 0 then
left_node(node)
elsif n == 1 then
right_node(node)
else
raise Exception.new("Invalid pattern match " + String(n))
end
end
# decoding
def decode(bits, tree)
decode_1 = lambda{|bits, current_node|
if bits.length == 0 then
[]
else
head = bits[0]
tail = bits[1..-1]
next_node = choose_node(head, current_node)
if is_leaf(next_node) then
append([symbol_leaf(next_node)], decode_1.call(tail, tree))
else
decode_1.call(tail, next_node)
end
end}
return decode_1.call(bits, tree)
end
# sets
def adjoin_set(x, items)
if node == () then
[x]
else
head = items[0]
if weight(x) < weight(head) then
append([x], items)
else
tail = items[1..-1]
append(head, adjoin_set(x, tail))
end
end
end
def make_leaf_set(node)
head = node[0]
tail = node[1..-1]
if is_leaf(head) then
adjoin_set(make_leaf(symbol_leaf(head), symbol_weight(head)), make_leaf_set(tail))
else
raise Exception.new("Invalid pattern match " + String(node))
end
end
# Exercise 2.67
sample_tree = make_code_tree(
make_leaf('A', 4),
make_code_tree(
make_leaf('B', 2),
make_code_tree(
make_leaf('D', 1),
make_leaf('C', 1))))
sample_message = [0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0]
putx decode(sample_message, sample_tree)
# Exercise 2.68
# exercise left to reader to define appropriate functions
# def encode(message, tree)
# if len(message) == 0 then
# []
# else
# head = message[0]
# tail = message[1..-1]
# append(encode_symbol(head, tree), encode(tail, tree))
# end
# end
# 2.4.1 Multiple Representations for Abstract Data - Representations for Complex Numbers
# Same as above
def square(x) x * x end
class Rectangular
attr_accessor :real
attr_accessor :imag
def initialize(real, imag)
@real = real
@imag = imag
end
def to_s()
"Rectangular(" + String(@real) + ", " + String(@imag) + ")"
end
end
class Polar
attr_accessor :magnitude
attr_accessor :angle
def initialize(magnitude, angle)
@magnitude = magnitude
@angle = angle
end
def to_s()
"Polar(" + String(@magnitude) + ", " + String(@angle) + ")"
end
end
# Rectangular
def real_part_r(z) z.real end
def imag_part_r(z) z.imag end
def magnitude_r(z)
Math.sqrt(square(real_part_r(z)) + square(imag_part_r(z)))
end
def angle_r(z)
Math.atan2(imag_part_r(z), real_part_r(z))
end
def make_from_real_imag_r(x, y)
Rectangular.new(x, y)
end
def make_from_mag_ang_r(r, a)
Rectangular.new(r*Math.cos(a), r*Math.sin(a))
end
# polar
def magnitude_p(z) z.magnitude end
def angle_p(z) z.angle end
def real_part_p(z)
magnitude_p(z) * math.cos(angle_p(z))
end
def imag_part_p(z)
magnitude_p(z) * Math.sin(angle_p(z))
end
def make_from_real_imag_p(x, y)
Polar.new(Math.sqrt(square(x) + square(y)), Math.atan2(y, x))
end
def make_from_mag_ang_p(r, a)
Polar.new(r, a)
end
# using the abstract type
def magnitude(z) magnitude_r(z) end
def angle(z) angle_r(z) end
def real_part(z) real_part_r(z) end
def imag_part(z) imag_part_r(z) end
def make_from_real_imag(x, y) make_from_real_imag_r(x, y) end
def make_from_mag_ang(r, a) make_from_mag_ang_r(r, a) end
z = Rectangular.new(1, 2)
putx make_from_real_imag(real_part(z), imag_part(z))
putx make_from_mag_ang(magnitude(z), angle(z))
def add_complex(z1, z2)
make_from_real_imag(
real_part(z1) + real_part(z2),
imag_part(z1) + imag_part(z2))
end
def sub_complex(z1, z2)
make_from_real_imag(
real_part(z1) - real_part(z2),
imag_part(z1) - imag_part(z2))
end
def mul_complex(z1, z2)
make_from_mag_ang(
magnitude(z1) * magnitude(z2),
angle(z1) + angle(z2))
end
def div_complex(z1, z2)
make_from_mag_ang(
magnitude(z1) / magnitude(z2),
angle(z1) - angle(z2))
end
# 2.4.2 Multiple Representations for Abstract Data - Tagged Data
def type_tag(a)
if a.kind_of?(Rectangular) then
'rectangular'
elsif a.kind_of?(Polar) then
'polar'
else
raise Exception.new("Invalid pattern match " + String(a))
end
end
def contents(a)
a
end
def is_rectangular(a)
a.kind_of?(Rectangular)
end
def is_polar(a)
a.kind_of?(Polar)
end
# Rectangular
def make_from_real_imag_rectangular(x, y)
Rectangular.new(x, y)
end
def make_from_mag_ang_rectangular(r, a)
Rectangular(r*Math.cos(a), r*Math.sin(a))
end
def real_part_rectangular(z)
z.real
end
def imag_part_rectangular(z)
z.imag
end
def magnitude_rectangular(z)
Math.sqrt(square(real_part_rectangular(z)) + square(imag_part_rectangular(z)))
end
def angle_rectangular(z)
Math.atan2(imag_part_rectangular(z), real_part_rectangular(z))
end
# Polar
def make_from_real_imag_polar(x, y)
Polar.new(Math.sqrt(square(x) + square(y)), Math.atan2(y, x))
end
def make_from_mag_ang_polar(r, a)
Polar.new(r, a)
end
def magnitude_polar(z)
z.magnitude
end
def angle_polar(z)
z.angle
end
def real_part_polar(z)
magnitude_polar(z) * Math.cos(angle_polar(z))
end
def imag_part_polar(z)
magnitude_polar(z) * Math.sin(angle_polar(z))
end
# Generic selectors
def real_part_g(a)
if is_rectangular(a) then
real_part_rectangular(a)
elsif is_polar(a) then
real_part_polar(a)
else
raise Exception.new("Invalid pattern match " + String(a))
end
end
def imag_part_g(a)
if is_rectangular(a) then
imag_part_rectangular(contents(a))
elsif is_polar(a) then
imag_part_polar(contents(a))
else
raise Exception.new("Invalid pattern match " + String(a))
end
end
def magnitude_g(a)
if is_rectangular(a) then
magnitude_rectangular(contents(a))
elsif is_polar(a) then
magnitude_polar(contents(a))
else
raise Exception.new("Invalid pattern match " + String(a))
end
end
def angle_g(a)
if is_rectangular(a) then
angle_rectangular(contents(a))
elsif is_polar(a) then
angle_polar(contents(a))
else
raise Exception.new("Invalid pattern match " + String(a))
end
end
# Constructors for complex numbers
def make_from_real_imag_g(x, y)
make_from_real_imag_rectangular(x, y)
end
def make_from_mag_ang_g(r, a)
make_from_mag_ang_polar(r, a)
end
# same as before
def add_complex_g(z1, z2)
make_from_real_imag_g(
real_part_g(z1) + real_part_g(z2),
imag_part_g(z1) + imag_part_g(z2))
end
def sub_complex_g(z1, z2)
make_from_real_imag_g(
real_part_g(z1) - real_part_g(z2),
imag_part_g(z1) - imag_part_g(z2))
end
def mul_complex_g(z1, z2)
make_from_mag_ang_g(
magnitude_g(z1) * magnitude_g(z2),
angle_g(z1) + angle_g(z2))
end
def div_complex_g(z1, z2)
make_from_mag_ang_g(
magnitude_g(z1) / magnitude_g(z2),
angle_g(z1) - angle_g(z2))
end
puts add_complex_g(make_from_real_imag_g(3, 4), make_from_real_imag_g(3, 4))
# 2.4.3 Multiple Representations for Abstract Data - Data-Directed Programming and Additivity
# To Be Done.
# 2.5.1 Systems with Generic Operations - Generic Arithmetic Operations
# To Be Done.
|