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

(define (add-1 n)
  (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 )

// Hofstadter's Typographical Numbers

val s = (x: CharSequence) => "S" + x //> s : CharSequence => String =

zero(s)("0") //> res0: String = 0

one(s)("0") //> res1: String = S0

two(s)("0") //> res2: String = SS0

three(s)("0") //> res3: String = SSS0

 
I had to look the Scala version elsewhere since Scala definitions needs concrete argument types whereas the argument and result of add-1 can be a function of arbitrary signature (arbitrarily high order). I started to guess that typelessness of Scheme Lisp is not only nicer but also enables truly functional simulating lambda calculus. Yet, Scala adepts do it with type system (metaprogramming) in Scala, which Odersky refuses to unveil. Instead of teaching Church Numerals and Functional purity in Scala, Odersky chooses to demonstrate Peano Numbers and OOP purity (Lecture 4.2). That is, only objects are used, without resorting to primitive types. 

SICP/Odersky exercises helped me to realize what is the common between FP and OOP, regarding the constructors and how do functions carry the data (state), posted in the next part?