Further down the rabbit hole

I was just reading Ben Hutchison's blog post on functional programming:
study-functional-programming-or-be-ignorant/

and I've come to a very similar realisation, with one notable additional point

lisp.

After watching some of the Structure and Interpretation of Computer Programs lectures,
my ideas about software, programming, data and computation have all been significantly changed.
The lectures focus on the theory of computer science using lisp.

In lisp, everything is (can be) represented as a list. This includes the source code, the interpreter, the environment, as well as data structures. The biggest change to my thinking occurred when they showed that something as fundamental as the list can be defined using closures and no other data structure. Something that I thought was an atom, built in, written in assembler; was actually definable in the language using other constructs.

This actually blew my mind.
It meant that all you needed was closures, and function application.
In the scheme example they showed in the lecture, it looked something like this:

(define (cons a b) (lambda (x) (x a b)))

(define (car x) (x (lambda (a b) a)))

(define (cdr x) (x (lambda (a b) b)))

The key is returning a when you call car(head), and b when calling cdr(tail).

I was so excited by this, I decided to implement it in a language I actually understood. ie NOT lisp.
I've been playing a bit with clojure and elisp, as well as haskell and I've been reading about F# and OCaml; But I keep coming back to scala, so I implemented it in that:

type consT[H, T] = ((H,T) => Any) => Any

def cons[H,T](a:H, b:T) : consT[H,T] = x => x(a,b)

def car[H,T](x:consT[H,T]) : H = x((a:H,b:T) => a).asInstanceOf[H]

def cdr[H,T](x:consT[H,T]) : T = x((a:H, b:T) => b).asInstanceOf[T]

 Most of which is actually type annotations, which ensure that the methods are completely generic. This is in contrast to lisps dynamic typing.

Some simplification is possible, but it's still not really the scala way:

type consT[H, T] = ((H, T) => Any) => Any

def cons[H, T](a: H, b: T): consT[H, T] = _(a, b)

def car[H, T](x: consT[H, T]) = x((a, _) => a).asInstanceOf[H]

def cdr[H, T](x: consT[H, T]) = x((_, b) => b).asInstanceOf[T]

If scala were to have some more advanced type inference or dynamic typing, it might look something like:

def cons(a, b) = _(a,b)

def car(x) = x((a,_) => a)

def cdr(x) = x((_,b) => b)

But it's pretty clear that that's not likely.

The beauty of it is, the lisp and scala uses of the above code is pretty similar.
something like this in clojure/lisp:

(def a (cons 1 (cons 2 3)))

(car a)

(car (cdr a))

(cdr (cdr a))

in scala:

val a = cons(1, cons(2, 3))

car(a)

car(cdr(a))

cdr(cdr(a))

So while the library side of things may be more complicated in scala, (also type safe), the actually usage is no more complicated at all.