viernes, 13 de mayo de 2011

In chapter 1.2.2 you can read about SICP view of tree recursion as a common
pattern of computation.As an example it proposes the computation of Fibonacci numbers.
Below you can check my F# version of the book's method for calculating them.

module FibonacciImplemtation
open System

let  rec  fib n =
  if n = 0  then 0 else
   if n = 1 then 1 else
    fib (n - 1) + fib (n - 2)

// test
let testFib = fib 7

jueves, 21 de abril de 2011

1.1.7 Example:Square roots by Newton's method

In secction 1.1.7 SICP lectures about the diference between
functions and procedures. To SICP´s point of view the
contrast between functions and procedures  is a reflection of
 the general distinction between describing properties of things
and describing how to do things, or the distinction between
declarative knowledge and imperative knowledge.
As a programming example to work on, introduces procedures
as an effective way to describe programatically mathematical functions.
The  problem selected is "Square roots by  Newton's method".
Scheme's implementation define a main body that checks if the
 parameters are good enough (auxiliary funtion) if so recurses using
calculated result of "improve" , a second auxiliary parametrized function.
 I will start my implementation of exercise 1.1.7  writing  F#'s version
 of this small set of auxiliary function:  average , good-enough?
 and improve. After due test of this set, i will implement the main body
 of the procedure, last step would be integrate all in one parametrized
 sqrt procedure with one parameter x.
So , let's start with the simplest auxiliary functions.Implement average
 is quite straightforward , just two algebraic operation, a sum and then
 division.
let average  x   y  =
 ( x + y) / 2
//test on interactive
let testAv = average 2 3
val testAv : int = 2


this test return 2 , I was  especting  2.5 ¿What is the deal?
Retrying with float valued parameters gives the following
error:
Evaluating testAv2 on REPL gives an error FS0001:
 This expression was exepcted to have type in but here
has type float
So, it look like the type inferencer decided int to be expected
type of x y, inference resolved by the parameters of my test
and the type of the divisor.In order to work with floats,
enter "type annotations".This annotation is a way to restrict an
argument type.In this case I should select
float as x & y's type .Also division by integer 2 is replaced by
division by 2.0.
let average ( x : float)   (y : float ) =
 ( x + y) / 2.0
 //Test it
let testAv2 = average 2.0  3.0
 //Results:
val testAv2 : float = 2.5

Now,  let's implement in F# the recursive lower limit auxiliary function:
let good_enough (guess : float)  (x : float) =
    let square x = x * x  
    abs (square guess  -  x) < 0.01


Advice:don't use interrogation sign as last
word of an identificator.It confuses the compiler.
Due test on the interactive compiler:
//Test
let testGood = good_enough 1.0  1.5
//Results:
val testGood : bool = false

The last of our set of auxiliary functions  improves
the guess using average function:
let improve (guess : float )  ( x : float) =
     let average ( x : float)   (y : float ) =
      ( x + y) / 2.0
     average guess (x / guess)

//Test:
let testImp = improve 1.0 1.5 
//Results:
val improve : float -> float -> float

Sqrt_iter has the role of main function
wifh will call the auxiliary ones.
  let rec sqrt_iter ( guess : float ) ( x : float ) =
     if (good_enough guess x) then
          guess
     else sqrt_iter ( improve guess  x)  x

//As test , trying to get the square root of 2:
let testSqrt = sqrt_iter 1.0 2.0
//Results:/
val tesSqrt : float = 1.416666667


Finally, I will refactor all previous snippets
in order to have a well formed , block structured
program:
  let rec sqrt_iter ( guess : float ) ( x : float ) =
      let good_enough (guess : float)  (x : float) =
          let square x = x * x   
          abs (square guess  -  x) < 0.01


      let improve (guess : float )  ( x : float) =
          let average ( x : float)   (y : float ) =
               ( x + y) / 2.0
          average guess (x / guess)


      if (good_enough guess x) then
          guess
          else sqrt_iter ( improve guess  x)  x
  let sqrt x =
       sqrt_iter 1.0 x

  












miércoles, 13 de abril de 2011

1.1.6 defining a procedure that computes the absolute value of a number


Section 1.1.6 of SICP presents the math rule
"absolute value of a number".SICP present
a couple of implementations of it, both using 
case analysis with cond and if-boolean branching.
This exercise should be a case of pattern
matching.I like F# pattern matching a lot.Unlike 
other functional concepts,(e.g: Curried functions)
hadn't any problem understanding matching.
Certainly it's a powerful tool. You can
think of keyword match Foo with as C#'s swich 
statement done the right way.

let abs x =
   match x with
    | x when x > 0 -> x       //match only when x > 0
    | x when x = 0 -> 0       //match only when x = 0
    | x when x < 0 -> (-x)    //match only when x < 0
    ;;

To test it evaluate the following expresions with REPL

let  absTestA = abs -3
let  absTestB = abs  5
let  absTestC = abs  0

And REPL will return:

 val absTestA : int = 3
 val absTestB : int = 5
 val absTestC : int = 0


First post & blog presentation


“Add little to little and there will be a big pile ”

                                                                         Ovid

                                                    

After two years working with C#, i am enjoying delving into F#.My conceptual
 introduction to funcional programming concepts was when i readed Abelson &
Sussman's "Structure and Interpretation of Computer Programs".In this blog
I will redo SICP's exercises as a constructive way of learn F#.