Ex. 1.12 Structure and Interpretation of Computer Programs

January 23, 2010

Generating Pascal’s Triangle. Not the most optimal implementation.

; Ex 1.12
(define bin-coeffs
  (lambda (n k)
    (cond ((= k 0 ) 1)
          ((= k n ) 1)
          (else (+ (bin-coeffs (- n 1) (- k 1))
                   (bin-coeffs (- n 1) k))))))

(define pascals-triangle-row
  (lambda (n)
    (define pascals-triangle-row-iter
      (lambda (k coeff-list)
        (cond ((> k n ) coeff-list)
              (else (pascals-triangle-row-iter (+ k 1)
                                               (cons (bin-coeffs n k) coeff-list))))))
    (pascals-triangle-row-iter 0 ‘())))

(define pascals-triangle
  (lambda (d)
    (define pascals-triangle&co
      (lambda (i col)
        (cond ((= i -1) col)
              (else (pascals-triangle&co (- i 1)
                                         (cons (pascals-triangle-row i) col
                                               ))))))
    (pascals-triangle&co d ‘())))



Flash and other virtual machines on the iPhone

January 19, 2010

I think it’s pretty lame that apple does not allow any other runtimes other than it’s own. It means that if a site makes heavy use of flash or java or silverlight it’s functioanlity is off limits to an iPhone use surfing the web.

Having said that I hate flash and I can’t wait for the day when HTML css and JavaScript finally makes that proprietay framework obsolete.


Flash and other virtual machines on the iPhone

January 19, 2010

I think it’s pretty lame that apple does not allow any other runtimes other than it’s own. It means that if a site makes heavy use of flash or java or silverlight it’s functioanlity is off limits to an iPhone use surfing the web.

Having said that I hate flash and I can’t wait for the day when HTML css and JavaScript finalllyakes that proprietay framework obsolete.


Excercise 1.11 Structure and Interpretation of Computer Programs (SICP)

January 16, 2010

I’m going through the “Structure and Interpretation of Computer Programs” as a way of compensating for my lack of geek cred.
I was having some problem with wrapping my head around the iterative solution of this exercise (hey it was after a long day at work), so I cheated a bit and looked it up on the internet and found a solution here. So in order to come up with my own solution, I decided to implement a solution using the collector function  or continuation technique for recursion shown or taught in the “Little Schemer” in chapter 8. Below is what I came up with

; Ex 1.11
; recursive solution
(define f-r
  (lambda (n)
    (cond ((< n 3) n)
          (else ( + (f-r (- n 1))
                    (* 2 (f-r (- n 2)))
                    (* 3 (f-r (- n 3))))))))

; Iterative Solution
(define f&co
  (lambda (n col)
    (cond ((< n 3) (col n 1 0))
          ( else (f&co (- n 1)
                       (lambda (a b c)
                         (col (+ a (* 2 b) (* 3 c))
                              a
                              b)))))))

(define f-i
  (lambda (n)
    (f&co n (lambda (a b c) a))))
(display “Recursive Solution”)
(newline)
(map f-r ‘(0 1 2 3 4 5 6))
(display “Iterative Solution using collector function”)
(newline)
(map f-i ‘(0 1 2 3 4 5 6))
                                


Learning OCAML: A Circular Double Link List Implementation.

January 9, 2010

I’m learning OCAML these days. I just finished reading the chapter on imperative programming in OCAML so I thought I could implement a circular double link list.

This is a first attempt, and its not quite what I wanted, but I think it’ll work.

(* Ch03 Doubly Linked Lists *)

(* 3.1 *) 

type 'a cell = 
    {
      data : 'a;
      mutable prev : 'a dlinklist;
      mutable next : 'a dlinklist
    }
and 
  'a dlinklist = Empty | Cell of 'a cell
;;

(* 3.2 Circular link list *)

let add_head x cll = 
  match cll with 
    | Empty -> 
    let new_cell = 
      { data = x; prev = Empty ; next = Empty} in
    let new_cll = Cell new_cell in
    new_cell.prev <- new_cll;
    new_cell.next <- new_cll;
    new_cll
    | Cell head_cell ->
    let new_cell = 
      { data = x ; prev = Empty; next = Empty } in
    let new_list = Cell new_cell in
    let tail_cell = head_cell.prev in
    (match tail_cell with
      | Empty -> ()
      | Cell pl -> pl.next <- new_list);
    new_cell.next <- cll;
    new_cell.prev <- head_cell.prev;
    head_cell.prev <- new_list;
    new_list


;;

let add_tail x cll = 
  match cll with
    | Empty -> add_head x Empty
    | Cell head_cell ->
    let tail_cell = 
      match head_cell.prev with
        | Empty -> failwith "Incorrect State"
        | Cell tc -> tc
    in
    let new_cell = { data = x ; prev = Empty ; next = Empty } in
    let new_list = Cell new_cell in
    tail_cell.next <- new_list;
    new_cell.prev <- head_cell.prev ;
    head_cell.prev <- new_list;
    cll
;;


let get_head_cell (cll:'a dlinklist) = 
  match cll with 
    | Empty -> failwith "Empty List"
    | Cell head_cell -> head_cell
;;

let get_tail_cell cll = 
  get_head_cell ((get_head_cell cll).prev)
;;

let remove_head cll = 
  let head_cell = get_head_cell cll in
  let tail_cell = get_tail_cell cll in
  let new_head_cell = get_head_cell (head_cell.next) in
  let new_list = Cell new_head_cell in
  if head_cell.prev = Empty 
    && head_cell.next = Empty 
  then
    Empty
  else
    begin
      new_head_cell.prev <- Cell tail_cell;
      tail_cell.next <- new_list;
      new_list
    end
;;

let remove_tail cll = 
  let head_cell = get_head_cell cll in
  let tail_cell = get_tail_cell cll in
  let new_tail_cell = get_head_cell (tail_cell.prev) in
  let new_list = Cell head_cell in
  new_tail_cell.next <- new_list;
  head_cell.prev <- Cell new_tail_cell;
  new_list
;;
      


SuperFreakonomics

December 25, 2009

Just finished reading SuperFreakonomics. Was’nt as explosive as the book cover suggested. It was’nt as mind-bending as the original was but then that’s how sequels go. I might have to reread the original and then come back to this again. It might help me appreciate this more.


Moving from Scheme to OCAML

December 20, 2009

So I started learning OCAML and I’m already missing Scheme …