#   **F\# Tutorial Exercises**

***For CSC 123/252, Hofstra University***   (version 7e9)

<br>
This tutorial will try to 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](https://fsharp.org/) to install
.Net SDK for your operating system.  This will make available the
`dotnet` command-line tool.

------------
<br>

## **PART I: Functional F\#**

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.  The first part of these exercises
will require you to use the 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.

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:

  1.  create a folder for your project, such as "FirstFs"
  2.  inside the folder, type `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.
  3.  Inside the folder, you will find a `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.


### **Declaring Variables**

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.


### **Defining Functions**

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 (C#, java, kotlin) can infer simple types,
like for 'var x = "abc"', but only a truly functional language in the
class of ML (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 ways to define functions:**
```
  > let f x = x+1;;
  > f 3;;
```

#### **Recursive Functions**

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
```
Notice the "then" in the if-else expression.

#### **Curried and Uncurried functions**

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;;
```

***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
```

We can simulate loops easily with recursive functions that take other
functions as arguments.
```
  > let rec forloop a b body =
      if a<b then 
        body a
        forloop (a+1) b body;;
  > forloop 0 10 (fun x -> printfn "x is %d" x);; // prints x is 0 to 9	
```
Here, `body` is a function that takes an integer argument.  Note also that
indentation is used to indicate the boy of the if statement.  This is similar
to Python.


### Alternative Ways to Pass Arguments to Functions

  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.


A function with no arguments can be defined as follows:
```
  > let f() = printfn "hello";;  // inferred type is unit -> unit
```
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`.

Scoping of functions, if-else cases, etc can be done by
indentation like in Python:
```
  > let f x (y:int) =
      let z = string(y)   // convert x to string  (type annotation required on y)
      printfn "%s" z
      System.Console.WriteLine(z);;  // java-ish way to print
```

***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.
```


### **Tuples and Lists

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).
Tuples share a lot of syntax with lists and arrays:
```
> 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.

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 [2;4;6;8] (fun x -> printf "x is %d " x);;
```
should print 2 4 6 8.  Challenge: can you figure out a way to define `foreach`
using the `forloop`?


### **Defining Data Structures**

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.

**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`.  We
use a simplified notation for defining functions using pattern matching.
```
  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
to 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 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 number 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`).

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.
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,
```
  > sublist (Cons(2,Cons(4,Nil))) (Cons(4,Cons(2,Cons(3,Cons(4,Nil)))))
```
should return true.


**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`.  Note 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


**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 in general:

1. 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".

2. 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)

3.  You (unfortunately) cannot use a variable more than once in a pattern,
    so `| (a::a::c) -> ... `would be invalid.  

4.  The `as y` is used on the last line so the entire pattern can referenced
    more easily (and efficiently, without recreating the structure).

5.  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.


----------------
<br>

## **Part II: Imperitive F\#**

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
```      

It is in fact a common trait among many languages that value parameters
can't be changed.

***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

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`.

### ***References***

Efficient data structures such as trees will still require the use of
pointers.
```
  > let x = 1;;
  > let px = ref x;; // sets px to point to x 
  > px := 5;;        // change referenced value to 5 
  > !px;;            // dereferences pointer (returns 5)
```
F\#'s pointers don't work the same way as C pointers.  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
```

### Conventional Data Structures: Records and Structs

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;
  // oh yes, and for lovers of zero-overhead abstraction:
  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 a garbage
collector.

It's still possible to pattern match against records and structs, as will
be demonstrated with other programs.


### .Net Integration

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.
```


----------------

###  **Sample Program**: matching brackets `()`, `[]`, and `{}`

   We end this tutorial with a classic program that matches brackets of
 types (), {}, and [].  For example, in "([])" all brackets match, but
 in "([)]" there is a mismatch, in "({}" there's an unmatched left (
 and in "()}" there's an unmatched right }.  The algorithm uses a
 stack that's initially empty and looks at each character in the input
 and do the following:
    
  if the next character is:
   
     (, [ or { : push this char on the stack

     ), ] or } : if the stack is empty, report this as an unmatched right
                 bracket and continue.  Otherwise, pop the stack and check
		 the popped char with this bracket: if they're a match,
		 such as [ and ], then continue, otherwise, report a
		 mismatch and continue
    all other characters are ignored
    
  Finally, at the end of the input, any characters still on the stack
  are reported as unmatched left brackets.  If we start and end with
  an empty stack, then all brackets match.

  There are two tail-recursive functions defined simultaneously using
  the `and` keyword.  The main function, match_brackets, takes a
  string, a position (i) in the string indicating the next character,
  a stack represented by a (char list) and an integer counting the
  number of errors.  The other function, check_stack, is called at the
  end of input to see if there are still brackets left on the stack.

  The function `match_all_brackets` just calls match_brackets and pass
  it the input string, 0 as initial position, [] as initial stack and
  0 as initial number of errors.  The boolean result is ignored (will
  get a compiler warning without the `|> ignore`.
*)
```
let rec match_brackets (input:string) i stack errors =
  if i>=input.Length then (check_stack stack errors)
  else
    match (stack,input.[i]) with
      | (s,'(') | (s,'[') | (s,'{') ->
        // push left brackets on stack:
        match_brackets input (i+1) (input.[i]::s) errors
      | ('('::s, ')')  |  ('['::s, ']')  |  ('{'::s, '}') ->
        // successful match, pop stack and continue:
        match_brackets input (i+1) s errors
      | (b::s, ')')  |  (b::s, ']')  |  (b::s, '}') ->
        // mismatched bracket types, report, pop and continue:
        printfn "Mismatched %A and %A at position %d" b (input.[i]) i
        match_brackets input (i+1) s (errors+1)
      | ([], ')')  |  ([], ']')  |  ([], '}') ->
        printfn "Unmatched right %A at position %d " (input.[i]) i
        match_brackets input (i+1) stack (errors+1)
      | (s,_) ->
        // ignore non-bracket characters
        match_brackets input (i+1) s errors
and

  check_stack stack errors =
    match (stack,errors) with
      | ([],0) ->
        printfn "All brackets match"
        true
      | ([],n) ->
        printfn "Match failed, there are %d errors" n
        false
      | (br::s,stat) ->
        printfn "Unmatched left %A" br
        check_stack s (errors+1);;

let match_all_brackets input = match_brackets input 0 [] 0  |>  ignore
// ignore is required when function returns a value that's not used

///// testing
match_all_brackets "(()(([[{}]])){{[]()}})"
match_all_brackets "([)]{}"
match_all_brackets "([]))}]"
match_all_brackets "({[]"

// Bonus: non-recursive version of match_brackets:
let match_bracks (input:string) =
  let mutable i = 0
  let mutable stack = []
  let mutable errors = 0
  while i < input.Length do
    match (stack,input.[i]) with
      | (s,'(') | (s,'[') | (s,'{') ->
        stack <- input.[i]::s // push on stack
      | ('('::s, ')')  |  ('['::s, ']')  |  ('{'::s, '}') ->
        stack <- s  // pop stack
      | (b::s, ')')  |  (b::s, ']')  |  (b::s, '}') ->
        printfn "Mismatched %A and %A at position %d" b (input.[i]) i
        stack <- s
        errors <- errors + 1
      | ([], ')')  |  ([], ']')  |  ([], '}') ->
        printfn "Unmatched right %A at position %d " (input.[i]) i
        errors <- errors+1
      | (s,_) -> () // do nothing
    i <- i+1 // always for each iteration of loop
  //while loop
  check_stack stack errors
// non-recursive match_bracks

match_bracks "(){}[[]]"  |>  ignore
```

(*    EXERCISE C2:
  The above program can only report the positions of the unmatched or
  mismatched right brackets, but not the positions of the left brackets.
  Modify the program so it can also report the positions of unmatched
  or mismatched left brackets.  You should either use a parallel stack
  that records the positions of the corresponding left brackets, or
  push a (char,int) pair onto the stack instead of just the char.

  EXERCISE C2.5: Make check_stack non-recursive (for your version that
  records the positions of left brackets)
*)