For CSC 123/252, Hofstra University (version 7e9)
This tutorial will teach you F#, a language with syntax
a bit different from what you're used to. As you read this tutorial,
type out all the lines marked with > in the F# interpreter and carry
out the required exercises. After you type something, record how the
interpreter responded.
Type up the answers to the exercises in a separate file so it can be submitted.
Follow Instructions on fsharp.org to install .Net SDK for your operating system. On Debian-compatible Linux (e.g Ubuntu) this can be done with
sudo add-apt-repository ppa:dotnet/backports
sudo apt install dotnet-sdk-9.0
Follow .Net SDK instructions for other systems.
This will make available the dotnet command-line tool.
The first part of this tutorial will introduce F# as a purely functional
programming language consistent with typed lambda calculus.
F# has an interactive interpreter. Start the interpreter with
dotnet fsi
Fsharp programs work like scripts (a main function is not required unless you're using Visual Studio), but unlike many scripting languages it is strongly and statically typed. Static typing means that the interpreter will type check each expression before evaluating it.
You can also use an editor to type up a F# program with a .fsx suffix
and execute it with the interpreter with dotnet fsi program1.fsx.
You can also load a program inside the interpreter with
#load "program1.fsx";;
open Program1;;
open Program1 allows access to the program's definitions. Note that
the module name Program1 must begin with an upper-case letter.
To compile a program with a .fs suffix, you will have to create a .Net project:
dotnet new console --language F# .
This will create a skeleton "hello world" Program.fs file, which
you can edit. dotnet build compiles the program and dotnet run
executes it, if compilation is successful. It's essential that you
are able to distinguish between what happens at compile time from
runtime events.FirstFS.fsproj xml file, which
can be edited to include other programs to compile, and references
to other projects and .dll files (more on that later).Another way to run F# is with a system called "Mono" but you won't get the latest version of .Net or F# with that system.
We will begin with the interpreter, which is started with dotnet fsi and
terminated with control-d. Start it in a terminal.
At the > prompt, type
> open System;;
The ;; at the end tells the interpreter that the command is complete and it
should be executed. A single ; separates multiple statements on
the same line. Try the following:
> printfn "a"; printfn "b";;
The ;; is only needed when writing programs inside the interpreter, not when
a program is compiled.
The heart of F# is typed lambda calculus. Although mutations (destructive assignments) are possible, we shall start with only immutable variables. Type the following:
> let x = 1;;
> let y = 1.0;;
Notice that F# inferred the types of x and y as int and float
respectively (don't worry, float is actually a 'double'). F# is very
strict when it comes to types, and is one of the most statically type
safe languages. But unlike other languages, you usually don't have
to declare what type you're using: it uses type inference aggressively.
However, there are also some unpleasant aspects of this type system:
it will not convert ints automatically to floats: (1+1.0) will give you
an error: you have to write 'float(1)+1.0' or 1+int(1.0).
The = symbol is used in declaring a variable in a let statement.
Independently, = means boolean equality (== in other languages).
> x = x+1;;
What do you expect here? It did not increment x, but evaluated to false,
because = means boolean equality! The operator == does
not exist in F#.
Most other common arithmetic and boolean operators such as &&, ||, <=,
%, etc. are the same in F#, but there are a couple of other differences:
<> represents inequality (!= in C/Java)not(a) represents boolean negation (!a in C/Java).The ! operator dereferences a reference in F#, thus the differences.
Equality and inequality on strings are ok: "abc" = "ab"+"c" returns true.
Functions are just lambda terms and you can bind them to variables: that's one way to define functions:
> let I = fun x -> x;; // this is lambda x.x in F# syntax
> let K = fun x y -> x;; // lambda x.lambda y.x
Note that it inferred the type of I as x:'a -> 'a. Here, 'a is a
generic (polymorphic) type variable. F# inferred the most general type
for I. Most other languages (like java) can infer simple types,
like for var x = "abc", but functional language in the
class of ML, such as F#, can infer the generic type of functions.
Applying functions:
> I 3;;
> I(3);; // same as above
Except for built-in infix operators such as +, F# uses lambda calculus
syntax: application associates to the left and application binds tighter
than abstraction. The parentheses on the second line above are not
necessary, but they are in K (K I).
EXERCISE 1: define the combinator
S = lambda x.lambda y.lambda z. x z (y z).
Note that the polymorphic types inferred for these terms correspond to
propositional tautologies (read 'a -> 'a as "a implies a").
Quicker way to define functions:
> let f x = x+1;;
> f 3;;
Recall that typed lambda calculus requires a special fixedpoint operator
for recursive definitions. In F#, this operator is indicated with
let rec instead of just let:
> let rec gcd(a,b) = if a=0 then b else gcd(b%a,a);;
> gcd(8,12);; // returns 4
> System.Console.WriteLine(gcd(27,18));; // java-ish way to print
Notice the "then" in the if-else expression.
Type and think about the difference between
> let f x y = x+y;;
and
> let g(x,y) = x+y;;
Note the types inferred for these functions: Both functions take a
single argument. g takes a pair of ints (type int*int)
and returns an int and f takes one int and returns a function that
expects the other int. F is a "Curried" function (after the logician
Haskell Curry). In lambda calculus without built-in pairs,
all functions are Curried.
Another example of Curried functions are those that can take an
undetermined number of arguments, like printf/printfn:
> printfn "%d %d" 1 2;;
> printfn "%d %d" 1 g(2,4);; // what do you expect here?
Didn't get what you expect? Got an error instead? (Get over it!) The reason you got an error is that you tried to pass to printfn THREE arguments instead of the two expected: the int 1, the function g, and the pair (2,4). You would get the same error if you typed
> f 3 g(2,3) or > f g(2,3) 4
Every F# function is a lambda term that expects one argument, though that argument can be a tuple. You can also define g as
> let g = fun (x,y) -> x+y;;
Note that fun x y -> .. is equivalent to fun x -> fun y -> .. but not
to fun (x,y) -> ...
EXERCISE 2: figure out how to apply printfn to 1 and g(2,4)
correctly. And in general, the proper way to apply curried functions.
The hint is in the error message.
Like in lambda calculus, functions can take other functions as arguments. The following functions convert any function between its Curried and Uncurried form.
let Curry g = fun x -> fun y -> g(x,y)
let Uncurry f = fun (x,y) -> f x y
Both functions take a function as argument and returns a function.
Given f and g as defined above, Curry g behaves like f and Uncurry f
behaves like g. For example, given the gcd function defined earlier, which
takes a pair as argument, Curry gcd 12 8 will return the same value
as gcd(12,8).
EXERCISE 3: Define a function that takes a function and "squares" it by
applying it twice. For example, square System.Math.Sqrt should return
a function that computes the 4th root of a value.
The following should work with your function
> let quadruple = square (fun x -> 2*x);;
> quadruple 3;; // should return 12 (2*2*3)
> let root4 = square Math.Sqrt;; // assuming `open System`
> root4 16.0;; // should return 2.0
A function with no arguments can be defined as follows:
> let f() = printfn "hello";;
Although the lambda calculus does not technically contain functions without
arguments, it's easily simulated using some dummy (vacuous) argument. In
F# this hidden dummy argument has type unit, which you can think of as
void. The f function above also does not return a value, so its type is
unit -> unit. The expression () also have type unit.
We can simulate loops easily with recursive functions that take other functions as arguments.
> let rec forloop a b action =
if a<b then
action a
forloop (a+1) b action;;
> forloop 0 10 (fun x -> printfn "x is %d" x);; // prints x is 0 to 9
Here, action is a function that takes an integer argument and returns nothing
(type int -> unit). Note that
indentation indicates the scope of the function definition as well as
the body of the if statement and other constructs. This is similar to
Python.
There is another way to apply a function to an argument, written
arg |> f as in
> 3 |> (4 |> f);; // same as (f 3 4)
> (3,4) ||> f;; // also same as (f 3 4), uncurries f internally
The |> and ||> operators associate to the left. These extra ways of
applying functions to arguments may appear redundant at first, but they
can give a cleaner syntax when composing a series of functions: instead
of h(g(f(arg))) one can write arg |> f |> g |> h. For example, sometimes
we call functions that return values, but don't do anything with the
return value. This is fine in Java, C and many other languages but FSharp
will give you a warning. To avoid the warning, instead of calling
g(2,3), we can call g(2,3) |> ignore. Expressions that do not return values
are of type "unit" (void). The ignore built-in discards whatever value passed
to in and returns unit.
Type annotations
Type inference works well most of the time, but sometimes you have to give it a hint, specifically when an operator like '+' works on multiple types:
> let h(x:float,y:float) = x+y;;
without the type annotation, the types of x,y will be inferred as ints.
EXERCISE 4: devise an experiment to verify that F# uses static as opposed to dynamic scoping (the world will end if it's dynamic).
Just to remind you, here's such a program in C:
int x = 1;
int f() { return x; } // f must refer to an external (free) variable
int main() {
int x = 2;
printf("%d", f()); // prints 1 if static, 2 if dynamically scoped
return 0;
} // C, like virtually all languages, is STATICALLY scoped.
F# contains built-in tuples and lists. Type the following in the interactive interpreter
> let a = (1,2,4.1);; // This is a tuple of type int*int*float
> let b = [1;2;4];; // This is a 'int list'
> let c = [1,2,4];; // before hitting return, what do you expect here?
c is a list of tuples, in this case just one tuple: (1,2,4).
> b.Length;; // returns length
> b[0];; // returns the first element in b
Sometimes you will also see the syntax b.[0], which reminds you that
b is an object.
To extract the individual values from a tuple you can deconstruct it by pattern matching:
> let (x,y,z) = a;;
This will set x to 1, y to 2 and z to 4.1.
Only tuples may contain values of different types, not lists.
EXERCISE 5: Modify the forloop function defined above into a
for-each loop. It should take a function and apply it to every value in
the list.
> foreach ["a";"b";"c"] (fun x -> printf "x is %d " x);;
should print a b c. Can you figure out a way to define foreach
using the forloop?
As a typed lambda calculus, F# supports both product types and disjunctive types, which are called discriminated unions. A union specifies that a type can be constructed (and deconstructed) with a number of discriminants. Here's a very simple union:
> type Direction = | North | East | South | West;;
This type is distinguished by one of the four discriminants. In some languages these are called enums, but F# unions are much more than the simple enums found in C.
> type Number =
| Integer of int
| Rational of int*int
| Real of float
| Complex of float*float;;
This type definition states that a "number" can either be an integer,
represented by a 32 bit signed int, a rational represented by a pair of
ints (numerator and demoninator), a real represented by a float, or
a complex number with a pair of floats (real and imaginary parts). An
expression such as Rational(1,3) will have type Number. The four
discriminants, Integer, Rational, Real and Complex, may look like constructors,
but in fact they're much more. They are also deconstructors. Types
defined this way are called algebraic types. They allow a distinctive
feature of typed functional languages called pattern matching. Suppose
we want to define an equality predicate between any pairs of numbers:
for example, Rational(1,2) should be considered "equal" to Real(0.5).
If you think this is a simple problem, just try to write an equivalent
program in C++ or Python first.
We can write it this way in F#:
> let rec equals a b =
match (a,b) with
| (Integer x, Integer y) -> x = y
| (Integer x, Rational(a,b)) -> x*b = a
| (Integer x, Real a) -> float(x) = a
| (Integer x, Complex(a,i)) -> i=0.0 && float(x) = a
| (Rational(a,b), Rational(c,d)) -> a*d = b*c
| (Rational(a,b), Real c) -> float(a) = float(b)*c
| (Rational(a,b), Complex(r,i)) -> i=0.0 && float(a) = float(b)*r
| (Real a, Real b) -> a = b
| (Real a, Complex(r,i)) -> i=0.0 && a = r
| (Complex(a,b), Complex(c,d)) -> a=c && b=d
| (x,y) -> equals y x;;
> equals (Rational (2,4)) (Rational (1,2));; // evaluates to true
The function is Curried, and recursive because the last clause covers the remaining six cases.
EXERCISE 6: Write a function that multiplies any two numbers. You must also keep precision as much as possible. For example, Integer(2) multiplied by Rational(1,3) should not be a Real but a Rational(2,3). Only when an Integer (or Rational) is multiplied by a Real should the result be a Real.
The rules of rational and complex multiplication are: a/b * c/d = a*c / b*d, and (a+bi) * (c+di) = (a*c-b*d) + (a*d+b*c)i. An integer, rational or real can be considered a complex number with zero imaginary part (a+0i). You will need clauses like
| (Integer x, Rational(a,b)) -> Rational(x*a, b)
For this exercise you may want to type up the solution with an editor first and then copy it into the interpreter. Make sure the lines are properly aligned.
EXERCISE 6b: Write a function that returns a string
representation for each type of Number. Represent Rational(a,b) as
"a/b". Represent Complex(a,b) as "a + bi". To convert a number
(float or int) to a string, call the string function: string(12)
returns "12". String concatenation is done with the + operator. A
useful function for creating strings is sprintf, which works just
like printf but will return a formated string instead of printing it
to stdout. For example, (sprintf "%s-%d" "abc" 123) will return
"abc-123".
User Defined linked list
Although F# supports linked lists natively, we can also define it ourselves.
> type LList<'T> = | Nil | Cons of 'T * LList<'T>;;
Notice that this type definition is recursive. We cannot define lists as
we did in the untyped lambda calculus without the built-in ability to define
recursive types. This definition also uses a generic type variable, which in
F# is preceded by a single quote. LList defines lists of elements of type
'T as either the empty list Nil or Cons(x,m) where x is of type 'T and
m is of type LList<'T>.
We can write lines such as
> let m = Cons(2,Cons(4,Cons(6,Cons(8,Nil))));;
> let (Cons(a,b)) = m;
The first line should look ordinary, but the second line may surprise you.
When Cons is on the right-hand side of the = symbol, it stands for
constructor. But when it's on the left-hand side of =, it becomes
a deconstructor. This is what pattern matching does.
The second line has the consequence of assigning
a to 2 and b to Cons(4,Cons(6,Cons(8,Nil))).
Note that extra ()s are required to distinguish the second line from a function definition.
Let's add some useful operations to accompany the type LList. The
function keyword simplifies the notation for defining functions that pattern
match on its argument:
let car = function // simplifies syntax for let car m = match m with ...
| Cons(a,_) -> a;; // _ is the "wildcard pattern"
let cdr = function
| Cons(_,b) -> b
| Nil -> Nil;;
let empty = function
| Nil -> true
| _ -> false;;
let rec length = function
| Cons(a,b) -> 1 + length(b)
| Nil -> 0;;
You will get a warning that there's missing Nil clause for car. When you
call car on Nil the system will throw an exception.
You might not like the recursive definition of the length function, and indeed
it's not efficient if written this way. Although F# has loops, for now
we stay within typed lambda calculus by rewriting the length function this way:
let length m =
let rec inner m cx =
match m with
| Nil -> cx
| Cons(a,b) -> inner b (cx+1)
// end of inner function
inner m 0 // body of outer function initializes cx counter to 0.
// end of outer function length
The length function now calls a local, inner recursive function, which takes an extra argument (cx is the counter). However, this inner function is tail recursive. That is, there is no additional operation required after the recursive call to inner. In contrast, the first length function still had to add 1 to the result of the recursive call afterwards, and is therefore not tail-recursive. An optimizing compiler can recognize tail recursion and compile it into something equally efficient as a loop by eliminating multiple stack frames for the recursive calls. Memory is used more efficiently underneath, but the high-level language remains pure lambda calculus. I will give more examples and explanations of tail recursion in a separate document. This is a critical idea to understand for a variety of reasons.
EXERCISE 7: Write a function doubleup that takes a list such as
Cons(2,Cons(4,Cons(7,Nil))) and returns a list containing
Cons(2,Cons(2,Cons(4,Cons(4,Cons(7,Cons(7,Nil)))))). That is, each
value should be repeated. Your first attempt may be non-tail recursive
but you must ultimately provide a tail recursive version.
Some more functions: the following can do much more because it accepts another function (f) as an argument:
let map f m =
let rec inner n stack =
match n with
| Nil -> stack
| Cons(a,b) -> inner b (Cons(f a, stack))
inner m Nil;
This function applies the function f to each element of the list and returns the resulting list. The resulting list will be reversed because the extra argument to the inner tail-recursive function is used like a stack.
let reverse m = map (fun x -> x) m
let squares = reverse (map (fun x -> x*x) m)
And an even more powerful function:
> let reduce op id m =
match m with
| Nil -> id
| Cons(a,b) -> reduce op (op id a) b;;
> reduce (+) 0 m;; // returns sum of numbers in list m
> reduce (*) 1 m;; // returns product of numbers in list m;
> reduce (fun x,y -> System.Math.Max(x,y)) 0 m;; // largest positive num in m
The reduce function takes an (Curried) function op that takes two
arguments and successively updates the id by applying id to each
successive argument. The expression (+) converts the (uncurried) infix
operator into a Curried function (equivalent to fun x y -> x+y).
Notice that reduce assumes that the operator op is left-associative
Can you (as a challenge) write a version where the op is right-associative?
Forall and there-exists:
let rec forall predicate m =
match m with
| Nil -> true
| Cons(a,b) -> (predicate a) && (forall predicate b);;
let there_exists predicate m = not(forall (fun x -> not(predicate x)) m)
The && operator is short-circuited like in other languages, and therefore
the above function is already tail-recursive.
The there_exists function uses a logical equivalence and is defined in terms
of forall.
EXERCISE 8: Write a function howmany that takes a list and a
predicate (a function that returns a bool) and returns how many values in
the list satisfy the predicate. For example,
> howmany (fun x -> x%2=1) (Cons(2,Cons(3,Cons(5,Cons(6,Cons(9,Nil))))))
should return 3, because there are three odd numbers in the list.
EXERCISE 9: Write a function filter that takes a predicate and
a list and returns a list with just those values for which the predicate
holds.
> howmany (fun x -> x%2=1) (Cons(2,Cons(3,Cons(5,Cons(6,Cons(9,Nil))))))
should return a list containing 3, 5, and 9. The ordering of the values is not important (don't have to reverse list).
EXERCISE 10: Write a function subset that determines if the values
in one list also appear in another list. The order and number of occurrences
of the values do not matter. For example,
> subset (Cons(2,Cons(4,Nil))) (Cons(4,Cons(2,Cons(3,Cons(4,Nil)))))
should return true. Try to define the relation logically: A is a subset of B if for all x in A there exists a y in B such that x=y
Native Lists
F# already contains native support for Lists. The syntax [2;3;4;5] is
equivalent to 2::3::4::5::[]. [] is equivalent to our Nil and
:: is an infix version of our Cons. The :: operator associates
to the right, so a::b::c should be read as a::(b::c).
EXERCISE 11: Write a function that converts a LList<'T> to a native
list. Here's the opposite conversion:
let toLList m =
let rec inner m stack =
match m with
| [] -> stack
| (a::b) -> inner b (Cons(a,stack))
reverse (inner m Nil)
Library functions like the ones we're defined are also available for native lists. For example,
> List.forall (fun x-> x%2=0) [2;4;6;8]
returns true. Consult online documentation for built-in operations that can be called on lists.
More on Pattern Matching
You can pattern match just about any type, including lists.
> let x = [2;3;4;5] //(or some list)
> match x with
| [] -> "none"
| [y] -> "exactly one" // [y] is same as pattern y::[]
| (a::b::rest) when a=b -> "the first two values are the same"
| (a::b::c::rest) as y -> string(y)+" has at least three values";;
| _ -> "two different values"
There are several points to note here about pattern matching, for lists and in general:
It is possible that a value could match multiple patterns: only the first clause that it matches will execute: so the above cannot print both "the first two are the same" and "... at least three".
Note the use of the "when" condition to further discriminate the
pattern: this is not exactly the same as using an if-else after the
->: if you wrote the third match clause as:
| (a::b::c) -> if a=b then "the first two are the same"
it would not try to match against the fourth pattern if the "if" failed.
(in fact, it won't compile without an else clause, since it must always
return a string)
You (unfortunately) cannot use a variable more than once in a pattern,
so | (a::a::c) -> ... would be invalid.
The as y is used on the last line so the entire pattern can referenced
more easily (and efficiently, without recreating the structure).
The last clause uses the _ wildcard: in this example, this case will
only match for lists that contain exactly two different values, because
all other possibilities are covered by the previous cases.
We will often need pattern matching on lists in our programs.
The core of F# is typed lambda calculus, but to create a practical language we cannot always rely on automatic optimizations such as for tail-recursion. We still need the ability to change memory directly in order to implement all algorithms as efficiently as possible. For example, quicksort is not only time- but memory efficient because values can be swapped in place. Without the ability to swap values in memory we would not be able to implement quicksort without additional memory overhead. F# in fact contains most of the typical tools you'll find in ordinary programming languages. We start with destructive assignment, or mutation:
> let mutable x = 1;;
> x <- x+1;;
> x = 2;; // evaluates to true
While = is only used in a let-declaration clause, the operator for changing
the value of an existing variable in F# is <-. Only variables declared
mutable can be changed.
A function's formal arguments are not mutable variables:
The following won't work:
> let f x =
while x>0 do
printfn "%d" x
x <- x-1;; // a function's argument is not a mutable variable
In C++ terminology, every formal argument to a function must be const.
EXERCISE II.1: fix the above function. (dont use references or anything weird - you just need one more line.)
With mutation we also have loops
while x<10 do
printfn "x is now %d" x
x <- x+1
for x in 0..9 do
printfn "x is now %d" x
for x in [2;4;5;6] do
printfn "%A" x
Note that the range syntax 0..9 in the for loop includes 9. This is
a little different from the convention adopted by most other languages.
The for-each loop is easily mimicked with tail-recursion, but the built-in
one is more convenient. Unfortunately F# doesn't contain a break statement
and you also cannot "return" from within a loop. You will just have to write
the boolean condition carefully.
Arrays are different from lists because they're contiguous in memory
and they're always mutable. Although you can use the bracket syntax
A[i] with lists, accessing an element at an arbitrary index is only
guaranteed to be O(1) with arrays.
> let d = [|2;3;5;7|];; // this has type int[] - an array
> d[0] = 4;; // evaluates to false
> d[0] <- 4;; // changes d[0] to 4
You might wonder why we didn't need the mutable keyword this time. That's
because we technically didn't change d but d[0]. Perhaps the next
exercise will clarify why this makes sense.
Arrays can also be created this way:
> let M:char[] = Array.create 10 'a';; // what kind of array does this create?
When defining a function with an array argument, a type annotation is often needed because the syntax for using arrays clashes with those of other structures: for example, if you write:
> let f x = x.[0];; // we wouldn't know if x is a list or an array.
Define it like this instead:
> let f (x:'a []) = x.[0];;
EXERCISE II.2: Devise an experiment to test if, when an array is
passed to a function as an argument, whether a reference (pointer) is
passed, or is the entire array is copied. Your function just need to
change some value in the array, and you need to test if the change is
just local. This exercise should also explain why changing d[0] is
not the same as changing d.
Efficient data structures such as trees will still require references.
> let x = 1;;
> let px = ref x;; // creates a "reference cell" with 1
> px := 5;; // change referenced value to 5
> !px;; // dereferences pointer (returns 5)
F# references don't work the same way as pointers in C. In C we can have:
int x = 1;
int *px = &x; // assigns p to memory address where x is located
*px = 5; // changes memory contents, THEREFORE CHANGES x also!
x==5 && x==*px; // this is now true. x has been changed through px.
But in the F# code, x is still 1 after px:=5. !px=x is false. This is
because the expression ref x copies the value of x into a new memory
location before returning the reference. It doesn't matter if x is
declared mutable or not. This is argued to be safer because it's less
likely that something's changed that shouldn't be through pointers.
To have the same effect in F#, use two references:
> let qx = px; // qx and px reference the same contents
> qx := 6; // this will also change what px points to. !px and !qx are both now 6
Algebraic data types in the form of discriminated unions are the primary reason that we're studying the ML family of languages. But F# also have more conventional data structures. I sometimes use "records". Records are like light-weight classes and are allocated on the heap.
// Record type for a stack using a fixed-size array.
type Stack<'T> =
{
S : 'T[];
mutable tos : int; // integer index "top of stack"
}
member this.push x = //returns bool indicating if push was successful
if this.tos<0 || this.tos >= this.S.Length then false
else
this.S.[this.tos] <- x
this.tos <- this.tos+1;
true
member this.pop() = // returns 'T option to prevent stack underflow
if this.tos>0 then
this.tos <- this.tos-1
Some(this.S.[this.tos])
else
None;
member this.pop_unchecked() = this.tos<-this.tos-1; this.S.[this.tos];
member this.size() = this.tos;
let stack:Stack<int> = {S=Array.zeroCreate 1024; tos=0;};;
//There's no constructor, but you can define a function to create a stack:
let makestack<'t> n = {S=Array.create n Unchecked.defaultof<'t>; tos=0;};;
// unfortuantely, Unchecked.defaultof<'t> is often null (blame java).
let s2 = makestack<string> 10;
match s2.pop() with
| Some(x) -> printfn "got an %A" x
| None -> ();; // () is "unit", does nothing
for i in [2;4;6;8;10] do stack.push i |> ignore;; // ignores returned value
while stack.size()>0 do
System.Console.WriteLine(stack.pop_unchecked());;
In fact, F# references are actually just records with a field called
contents. The only differences are the special operators ! and :=.
Records can be considered lightweight classes. F# also contain full-scale classes but we will skip those for now.
Records are stored on the Heap, and only references to the actual records are stored on the stack. This means that, when we pass a record to a function, we're actually passing a reference (pointer). This usage of stack/heap is very similar to Java and many other languages that rely on garbage collectors to manage memory. However, F# also have structs, which are allocated on the STACK unless they're part of a heap-allocated object.
type KVpair<'A,'B> = // key-value pair
struct
val mutable key:'A
val mutable val:'B
new(x,y) = {key=x; val=y;} // can have constructor of struct
override this.ToString() = sprintf "%A:%A" this.key this.val
member this.changeVal v = this.val <- v
end;;
let mutable p1 = KVpair("B",4);
printfn "p1 using ToString is %A" p1;;
Being stack allocated also means that when a struct is passed to a function, it's passed by value: a copy of the struct is passed. Structs cannot define recursive structures. They usually represent small collections of simple data. They are less flexible but are more efficient than records because stack-allocation is much quicker than heap allocation and there's no need for the garbage collector.
It's also possible to pattern match against records and structs, as will be demonstrated with other programs.
The flagship language of .Net is considered to be C#, which is very
similar to Java. F# interoperates with C# and share many
structures. You can create applications using a combination of
different .Net languages. You can write a class in C# and use it in
F#. In particular, the data structures in
System.Collections.Generic are all available to F#.
> open System.Collections.Generic;;
> let ID = Dictionary<string,int>();; // HashMap
> ID["Mary"] <- 702345126;;
> ID["Larz"] <- 701555667;;
> printfn "%d" (ID.["Larz"]);;
Although arrays elements are mutable, their sizes cannot change. For that
(the equivalent of a vector), we need a ResizeArray<'T>, which is
equivalent to System.Collections.Generic.List<'T>.
> let vector = ResizeArray<int>();;
> vector.Add(4);;
> vector.Count;; // returns 1, the size of vector.
> v[0] <- 5;; // indexed access still possible.