Topics:SICP in other languages:Scala:Chapter 2
From CTMWiki
| Table of contents |
[edit]
About SICP
The following Scala code is derived from the examples provided in the book:
"Structure and Interpretation of Computer Programs, Second Edition"
by Harold Abelson and Gerald Jay Sussman with Julie Sussman.
http://mitpress.mit.edu/sicp/
[edit]
SICP Chapter #02 Examples in Scala
object SICP02 {
def main(args: Array[String]): unit = {
/* Functions defined in previous chapters */
def fib(n: long): long =
n match {
case 0 => 0;
case 1 => 1;
case n => fib(n - 1) + fib(n - 2);
};
def gcd(a: long, b: long): long =
b match {
case 0 => a;
case b => gcd(b, a % b);
};
[edit]
/* 2 Building Abstractions with Data */
def linear_combination(a: long, b: long, x: long, y: long): long =
a * x + b * y
def mul(x: long,y: long) = (x*y)
def linear_combination_(a: long, b: long, x: long, y: long): long =
mul(a,x) + mul(b,y)
[edit]
/* 2.1.1 Introduction to Data Abstraction - Example: Arithmetic Operations for Rational Numbers */
def make_rat(n: long, d: long) = List(n,d)
def numer(n: List[long]) = n.head
def denom(n: List[long]) = n.tail.head
def add_rat(x: List[long], y: List[long]) =
make_rat((numer(x) * denom(y)) + (numer(y) * denom(x)), denom(x) * denom(y))
def sub_rat(x: List[long], y: List[long]) =
make_rat((numer(x) * denom(y)) - (numer(y) * denom(x)), denom(x) * denom(y))
def mul_rat(x: List[long], y: List[long]) =
make_rat(numer(x) * numer(y), denom(x) * denom(y))
def div_rat(x: List[long], y: List[long]) =
make_rat(numer(x) * denom(y), denom(x) * numer(y))
def equal_rat(x: List[long], y: List[long]) =
((numer(x) * denom(y)) == (numer(y) * denom(x)))
def cons[A] = List(_: A, _: A)
def car[A] = (_: List[A]).head
def cdr[A] = (_: List[A]).tail
def cadr[A] = car[A].compose(cdr[A])
def cadr_[A](x : List[A]) = car(cdr(x))
val x = cons(1,2)
car(x)
cdr(x)
val x_ = cons(1, 2)
val y = cons(3, 4)
val z = cons(x_, y)
car(car(z))
car(cdr(z))
/* footnote -- alternative definitions */
def make_rat_[A](x: A, y: A) = cons(x,y)
def numer_[A](x: List[A]) = car(x)
def denom_[A](x: List[A]) = cdr(x)
def print_rat(x: List[long]) = {
println()
print(numer(x))
print("/")
print(denom(x))
}
val one_half = make_rat(1, 2);
print_rat(one_half);
val 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: long, d: long) = {
val g = gcd(n,d)
List(n / g, d / g)
}
def add_rat_(x: List[long], y: List[long]) =
make_rat_((numer(x) * denom(y)) + (numer(y) * denom(x)), denom(x) * denom(y))
print_rat(add_rat_(one_third, one_third));
/* end Literal Translation */
[edit]
// Exercise 2.1
def make_rat (n:Long, d:Long) = {
val g = gcd(n, d)
(n/g, d/g)
}
// println(make_rat ( 10, 15)) // answer is: (2,3)
// println(make_rat (-10, 15)) // answer is: (-2,3)
// println(make_rat ( 10, -15)) // answer is: (-2,3)
// println(make_rat (-10, -15)) // answer is: (2,3)
[edit]
// Exercise 2.2
def point (x:Long, y:Long) = (x,y)
def x_point (point:(Long,Long)) = point._1
def y_point (point:(Long,Long)) = point._2
def make_segment (x:(Long,Long),y:(Long,Long)) = (x,y)
def start_segment (segment:((Long,Long),(Long,Long))) = segment._1
def end_segment (segment:((Long,Long),(Long,Long))) = segment._2
def midpoint_segment (segment:((Long,Long),(Long,Long))) = {
val start_seg = start_segment (segment)
val end_seg = end_segment (segment)
def average_through_dimension (dimension:((Long,Long))=>Long) =
average(dimension(start_seg), dimension(end_seg))
point (average_through_dimension(x_point), average_through_dimension(y_point))
}
def print_point (point:(Long,Long)) =
println("(" + (x_point(point)) + "," + (y_point(point)) + ")")
// print_point (midpoint_segment (make_segment (point (1,2), point(5,10)))) // result is: (3,6)
[edit]
// Exercise 2.3
// Representation 1: stores the two opposing points
def make_rect (point1:(Long,Long),point2:(Long,Long)) = (point1,point2)
def rect_width (rect:((Long,Long),(Long,Long))) =
Math.abs (x_point(rect._1) - x_point(rect._2))
def rect_height (rect:((Long,Long),(Long,Long))) =
Math.abs (y_point(rect._1) - y_point(rect._2))
//Representation 2: stores the diagonal segment
// ToDo..
def rect_perimeter (rect:((Long,Long),(Long,Long))) =
2 * rect_width(rect) + 2 * rect_height(rect)
def rect_area (rect:((Long,Long),(Long,Long))) =
rect_width(rect) * rect_height(rect)
// val rect = make_rect (point(1,1), point(3,4))
// println(rect_perimeter(rect)) // result is: 10
// println(rect_area(rect)) // result is: 6
[edit]
// Exercise 2.4
def my_cons (x:Long,y:Long) = (m:(Long,Long)=>Long)=>m(x,y) def my_car (z:((Long,Long)=>Long)=>Long) = z((x:Long,y:Long)=>x) def my_cdr (z:((Long,Long)=>Long)=>Long) = z((x:Long,y:Long)=>y) // println(my_car (my_cons (2,3))) // result is: 2 // println(my_cdr (my_cons (2,3))) // result is: 3
[edit]
// Exercise 2.5
def my_cons1 (a:Long,b:Long) = pow(2,a) * pow(3,b)
def extract_power (num:Long,base:Long,acc:Long) : Long =
if (num % base == 0) extract_power(num/base, base, acc+1)
else acc
def my_car1 (c:Long) = extract_power(c,2,0)
def my_cdr1 (c:Long) = extract_power(c,3,0)
// println(my_car1 (my_cons1 (12,8))) // result is: 12
// println(my_cdr1 (my_cons1 (12,8))) // resula is: 8
[edit]
// Exercise 2.6
def zero = (f:(Long)=>Long)=>((x:Long)=>x)
def one = (f:(Long)=>Long)=>((x:Long)=>f(x))
def two = (f:(Long)=>Long)=>((x:Long)=>f(f(x)))
def three = (f:(Long)=>Long)=>((x:Long)=>f(f(f(x))))
def four = (f:(Long)=>Long)=>((x:Long)=>f(f(f(f(x)))))
def add_1 (n:((Long)=>Long)=>((Long)=>Long)) =
(f:(Long)=>Long)=> ( (x:Long)=>f (n (f) (x)) )
def plus (a:((Long)=>Long)=>((Long)=>Long),b:((Long)=>Long)=>((Long)=>Long)) =
(f:(Long)=>Long)=> ( (x:Long)=> b(f) (a(f) (x)) )
// println( ((add_1(zero )) ((x:Long)=>x*x) ) (3)) // result is: 9 = sqr(3)
// println( ((add_1(one )) ((x:Long)=>x*x) ) (3)) // result is: 81 = sqr(sqr(3))
// println( ((add_1(two )) ((x:Long)=>x*x) ) (3)) // result is: 6561 = sqr(sqr(sqr(3)))
// println( ((add_1(three)) ((x:Long)=>x*x) ) (3)) // result is: 43046721 = sqr(sqr(sqr(sqr(3))))
// println( ((add_1(four )) ((x:Long)=>x*x) ) (3)) // result is: 1853020188851841 = sqr(sqr(sqr(sqr(sqr(3)))))
// println( ((plus(two,one)) ((x:Long)=>x*x)) (3)) // result is: 6561 = sqr(sqr(sqr(3))) - 2+1 sqr-composition
[edit]
// Exercise 2.7
def make_interval (lower:Double,upper:Double) = (lower,upper) def upper_bound (interval:(Double,Double)) = interval._2 def lower_bound (interval:(Double,Double)) = interval._1
[edit]
// Exercise 2.8
def add_interval (interval1:(Double,Double),interval2:(Double,Double)) = {
val lower_ = lower_bound(interval1) + lower_bound(interval2)
val upper_ = upper_bound(interval1) + upper_bound(interval2)
make_interval(lower_,upper_)
}
def sub_interval (interval1:(Double,Double),interval2:(Double,Double)) = {
val lower_ = lower_bound(interval1) - lower_bound(interval2)
val upper_ = upper_bound(interval1) - upper_bound(interval2)
make_interval(lower_,upper_)
}
// val interval1 = make_interval(7,6)
// val interval2 = make_interval(5,4)
// println( add_interval(interval1,interval2) ) // result is: (12,10)
// println( sub_interval(interval1,interval2) ) // result is: (2,2)
[edit]
// Exercise 2.10
def mul_interval (x:(Double,Double),y:(Double,Double)) = {
val p1 = lower_bound(x) * lower_bound(y)
val p2 = lower_bound(x) * upper_bound(y)
val p3 = upper_bound(x) * lower_bound(y)
val p4 = upper_bound(x) * upper_bound(y)
val lower = (p1 /: List(p2,p3,p4)) (Math.min(_,_))
val upper = (p1 /: List(p2,p3,p4)) (Math.max(_,_))
make_interval (lower,upper)
}
def div_interval (x:(Double,Double),y:(Double,Double)) = {
if (upper_bound(y)>=0 && lower_bound(y)<=0) throw new Exception("Divisor spans zero")
else mul_interval( x, make_interval(1.0 / upper_bound(y).toDouble, 1.0 / lower_bound(y).toDouble ) )
}
// println(mul_interval( make_interval(3,4), make_interval(5,6) )) // result is: (15,24)
// println(div_interval( make_interval(3,4), make_interval(5,6) )) // result is: (0.5,0.8)
// println(div_interval( make_interval(3,4), make_interval(-5,6) )) // result is: java.lang.Exception: Divisor spans zero ...
[edit]
// Exercise 2.11
def mul_interval_advanced (x:(Double,Double),y:(Double,Double)) = {
val x_upper = upper_bound(x)
val x_lower = lower_bound(x)
val y_upper = upper_bound(y)
val y_lower = lower_bound(y)
if (x_lower>=0 && x_upper>=0 && y_lower>=0 && y_upper>=0)
make_interval (x_lower*y_lower, x_upper*y_upper)
else if (x_lower>=0 && x_upper>=0 && y_lower< 0 && y_upper>=0)
make_interval (x_upper*y_lower, x_upper*y_upper)
else if (x_lower>=0 && x_upper>=0 && y_lower< 0 && y_upper< 0)
make_interval (x_upper*y_lower, x_lower*y_upper)
else if (x_lower< 0 && x_upper>=0 && y_lower>=0 && y_upper>=0)
make_interval (x_lower*y_upper, x_upper*y_upper)
else if (x_lower< 0 && x_upper>=0 && y_lower< 0 && y_upper>=0) {
val p1 = x_lower * y_lower
val p2 = x_lower * y_upper
val p3 = x_upper * y_lower
val p4 = x_upper * y_upper
val lower = (p1 /: List(p2,p3,p4)) (Math.min(_,_))
val upper = (p1 /: List(p2,p3,p4)) (Math.max(_,_))
make_interval (lower,upper)
}
else if (x_lower< 0 && x_upper>=0 && y_lower< 0 && y_upper< 0)
make_interval (x_upper*y_lower, x_lower*y_lower)
else if (x_lower< 0 && x_upper< 0 && y_lower>=0 && y_upper>=0)
make_interval (x_lower*y_upper, x_upper*y_lower)
else if (x_lower< 0 && x_upper< 0 && y_lower< 0 && y_upper>=0)
make_interval (x_lower*y_upper, x_lower*y_lower)
else if (x_lower< 0 && x_upper< 0 && y_lower< 0 && y_upper< 0)
make_interval (x_upper*y_upper, x_lower*y_lower)
else throw new Exception("Impossible intervals")
}
// println(mul_interval (make_interval ( 10, 20), make_interval ( 3, 40))) // result is: (30.0,800.0)
// println(mul_interval (make_interval ( 10, 20), make_interval ( -3, 40))) // result is: (-60.0,800.0)
// println(mul_interval (make_interval ( 10, 20), make_interval (-40, -3))) // result is: (-800.0,-30.0)
// println(mul_interval (make_interval (-10, 20), make_interval ( 3, 40))) // result is: (-400.0,800.0)
// println(mul_interval (make_interval (-10, 20), make_interval ( -3, 40))) // result is: (-400.0,800.0)
// println(mul_interval (make_interval (-10, 20), make_interval (-40, -3))) // result is: (-800.0,400.0)
// println(mul_interval (make_interval (-10, 20), make_interval ( 3, 40))) // result is: (-400.0,800.0)
// println(mul_interval (make_interval (-20, -10), make_interval ( -3, 40))) // result is: (-800.0,60.0)
// println(mul_interval (make_interval (-20, -10), make_interval (-40, -3))) // result is: (30.0,800.0)
// println()
// println(mul_interval_advanced (make_interval ( 10, 20), make_interval ( 3, 40))) // result is: (30.0,800.0)
// println(mul_interval_advanced (make_interval ( 10, 20), make_interval ( -3, 40))) // result is: (-60.0,800.0)
// println(mul_interval_advanced (make_interval ( 10, 20), make_interval (-40, -3))) // result is: (-800.0,-30.0)
// println(mul_interval_advanced (make_interval (-10, 20), make_interval ( 3, 40))) // result is: (-400.0,800.0)
// println(mul_interval_advanced (make_interval (-10, 20), make_interval ( -3, 40))) // result is: (-400.0,800.0)
// println(mul_interval_advanced (make_interval (-10, 20), make_interval (-40, -3))) // result is: (-800.0,400.0)
// println(mul_interval_advanced (make_interval (-10, 20), make_interval ( 3, 40))) // result is: (-400.0,800.0)
// println(mul_interval_advanced (make_interval (-20, -10), make_interval ( -3, 40))) // result is: (-800.0,60.0)
// println(mul_interval_advanced (make_interval (-20, -10), make_interval (-40, -3))) // result is: (30.0,800.0)
[edit]
// Exercise 2.12
def make_center_width (c:Double,w:Double) = make_interval (c-w,c+w)
def center (i:(Double,Double)) = (lower_bound(i)+upper_bound(i))/2
def width (i:(Double,Double)) = (upper_bound(i)-lower_bound(i))/2
def make_center_percent (center:Double, percentage_tolerance:Double) =
make_center_width (center, Math.abs(center)*(percentage_tolerance/100))
def percent (i:(Double,Double)) = width(i) / (100*Math.abs(center(i)))
[edit]
// Exercise 2.14
def par1(r1:(Double,Double), r2:(Double,Double)) =
div_interval (mul_interval(r1,r2), add_interval(r1,r2))
def par2(r1:(Double,Double), r2:(Double,Double)) = {
val one = make_interval(1,1)
div_interval (one, (add_interval( div_interval(one,r1), div_interval(one,r2) )))
}
// val A = make_interval(7,8)
// val B = make_interval(5,10)
// println(par1(A,B)) // result it: (1.9444444444444444,6.666666666666666)
// println(par2(A,B)) // result it: (2.9166666666666665,4.444444444444445)
![[Main Page]](/wiki/stylesheets/images/wiki.png)