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
Learning F# by resolving SICP exercises
After a while working with C#, i am enjoying delving into F#.My conceptual introduction to Funcional programming concepts was when read Abelson & Sussman's "Structure and Interpretation of Computer Programs".In this blog I will redo some of SICP's programs and exercises as a constructive way of learn F#.
viernes, 13 de mayo de 2011
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:
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) =
Advice:don't use interrogation sign as lastword of an identificator.It confuses the compiler.
Due test on the interactive compiler:
//Test
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.
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
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 expectedThis expression was exepcted to have type in but here
has type float
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
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
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 improvesval testGood : bool = false
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) thenguess
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#.
Suscribirse a:
Entradas (Atom)