## Sunday, June 22, 2014

### 2.1.3 What Is Meant by Data (in Scala)?

It seems that Oderski have decided to stand up on the shoulders of giants and spend time designing a great language instead of inventing new fancy usages and programming concepts. At least this comes to mind when watching his online course and reading the referenced SICP book by Hal Abelson's, Jerry Sussman's and Julie Sussman's. In chapter 2 they abstract data with rational number and finally come to the question: what it means to be data?

Since language is functional, they manage to give a purely functional definition of the couple
(a basic data structure, they can build anything from it)

### (define (cons x y)  (define (dispatch m)    (cond ((= m 0) x)          ((= m 1) y)          (else (error "Argument not 0 or 1 -- CONS" m))))  dispatch)(define (car z) (z 0))(define (cdr z) (z 1))

Here is my Scala translation

def cons[T](x: T, y: T) = {
(m: Boolean) => if (m) x else y
} //                                    > cons: [T](x: T, y: T)Boolean => T
def car[T](z: Boolean => T) = z(true) //> car: [T](z: Boolean => T)T
def cdr[T](z: Boolean => T) = z(false) /> cdr: [T](z: Boolean => T)T

val z = cons("nominator", "denominator") //> z : Boolean => String =
car(z) //> res0: String = nominator
cdr(z) //> res1: String = denominator
But that is not functional enough.

Take that

(define (cons x y)
(lambda (m) (m x y)))

(define (car z)
(z (lambda (p q) p)))

In the Exercise 2.4 they ask to provide a corresponding implementation of cdr. Here it is in Scala

def cons[T](x: T, y: T) = {
(m: (T,T) => T) => m (x,y)
} //                                  > cons: [T](x: T, y: T)((T, T) => T) => T
def car[T](z: ((T, T) => T) => T) = {
z((x: T, y: T) => x)
} //                                  > car: [T](z: ((T, T) => T) => T)T
def cdr[T](z: ((T, T) => T) => T) = {
z((x: T, y: T) => y)
} /                                  /> cdr: [T](z: ((T, T) => T) => T)T

val z= cons(1,2) //  > z : ((Int, Int) => Int) => Int =
car(z) //> res0: Int = 1
cdr(z) //> res1: Int = 2

How do you like this? Booleans are eliminated. To blow out the mind completely, they ask to implement all numbers in terms of functions, Ex 2.6

(define zero (lambda (f) (lambda (x) x)))

(lambda (f) (lambda (x) (f ((n f) x)))))

// Scala

type NUM[A] = (A => A) => A => A
def succ [A]: NUM[A] => NUM[A] = m => n => x => n(m(n)(x))
//> succ: [A]=> _ChurchNumbers.NUM[A] => _ChurchNumbers.NUM[A]

// check
def zero[A]: NUM[A] = f => x => x //> zero: [A]=> _ChurchNumbers.NUM[A]
def one[A]: NUM[A] = succ(zero) //> one: [A]=> _ChurchNumbers.NUM[A]
def two[A]: NUM[A] = succ(one) //> two: [A]=> _ChurchNumbers.NUM[A]
def three[A]: NUM[A] = f => x => f(f(f(x))) //> three: [A]=> _ChurchNumbers.NUM[A]
val f: Int => Int = (x: Int) => x+1 //> f : Int => Int =
assert( zero(f)(0) == 0 )
assert( one(f)(0) == 1 )
assert( two(f)(0) == 2 )