# **F\# Tutorial Exercises**
***For CSC 123/252, Hofstra University*** (version 7e9)
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.
------------
## **PART I**
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.
Start the interpreter: `dotnet fsi`.
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 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? Of course it's false! The operator '==' does
not exist in F\#. The `=` operator doesn't mean destructive assignment.
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.
The word 'mutable' means that y can be changed (destructively assigned). Type:
```
> y <- y+1;;
> y;;
```
What is the <- operator? It's the assignment operation. The symbol '='
is NOT assignment, it's only for declarations (let) and for BOOLEAN EQUALITY.
### **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 I1:*** 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;;
```
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);;
```
Notice the "then" in the if-else expression.
### Curried and Uncurried functions
Type and infer 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 the 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 I2:*** 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.
### 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.
**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 needed on y)
printfn "%s" z
System.Console.WriteLine(z);; // java-ish way to print
```
*** EXERCISE I3: 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.
```
//////////////////////////MOVE:::
****** 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 argument is not a mutable variable
```
It is in fact a common trait among many languages that value parameters
can't be changed.
***EXERCISE I3:*** fix the above function. (dont use references or anything
weird - you just need one more line.)
A function with no arguments can be defined as follows:
> let f() = printfn "hello";; // inferred type is unit -> unit
### **Tuples, Lists and Arrays**
F\# has special syntax for Tuples, lists and arrays.
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. However, although you can use the bracket syntax,
accessing an element at an arbitrary index is ***not*** necessarily
an O(1) operation with lists, only with ***arrays:***
```
> let d = [|2;3;5;7|];; // this has type int[] - an array
> d[0] = 2;; // evaluates to true
```
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];;
```
only tuples may contain values of different types, not arrays or lists.
### **Defining Data Structures**
As a typed lambda calculus, F\# supports both product types and *disjuntive*
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:*** 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.
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 stack = function
| Nil -> stack
| Cons(a,b) -> inner 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
```
MOVE::::::::::::::::::::::::::::
*** EXERCISE I5. 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.
Note that you don't need the keyword 'mutable' above, but you can still assign
to an array index, for example, M.[0] <- 'b'; Changing M.[0] is not the same
as changing A (see exercise I5).
Besides tuples, lists and arrays, you can use any .Net data structure
the way they're used in other languages. Sometimes, F\# provides special
syntax so you can use some of them more easily. In fact the 'a list
data structure is based on System.Collections.Generic.List.
> open System.Collections.Generic;;
You can also use a "Dictionary" (aka associative list or HashMap):
> let ID = Dictionary();; // the word "new" is optional
> ID.["Mary"] <- 702345126;;
> ID.["Larz"] <- 701555667;;
> printfn "%d" (ID.["Larz"]);;
So you can write software with some components in F\# and others in C#
or some other .Net language.
***** References (Pointers) *****
Efficient data structures such as trees will still require the use of
pointers (see binary search tree program).
> 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
To exit the interactive interpreter cleanly, do Control-D or
> exit 0;; // like in C
PART II
///////////////////////////////////////////////////////////////////////
3. ***************** Pattern Matching *****************
So far, we haven't seen much about F\# that's not in other languages
(except for more powerful type inference). One of the most important
features of F\# (and similar languages including ML, Haskell and Scala)
is pattern matching. The gcd function above can also be defined as
follows:
>let rec gcd x =
match x with
| (0,b) -> b
| (a,b) -> gcd(b%a,a);;
or
>let rec gcd = function
| (0,b) -> b
| (a,b) -> gcd(b%a,a);; // syntax warning: don't use a tab here
The word "function" is just more convenient syntax for matching the
the (last) argument of gcd against patterns.
In older languages such as C, the term "Data Structure" is a bit of a
misnomer. The "structure" only exists at compile time. Once
compiled, all "structure" disappears and all data are treated as
blocks of bytes. In object-oriented languages, some notion of
"structure" is retained at runtime in the form of the runtime/dynamic
type tag that a piece of data is associated with. In these languages,
we can write "constructors" to construct a data structure from its
components, but there is no corresponding notion of a *deconstructor*,
which is the ability to decompose a data structure back into its
components and subcomponents, and do it in a way that's type safe: we
do not want to deconstruct a double into a char[8]. Just having a
type tag attached to an object is still not sufficient for this kind
of deconstruction. In F\# and similar languages (which includes ML,
Scala, Haskell, Elm, and Rust to a degree), data must be fully
deconstructable. This is possible with so-called "algebraic data
types". The match keyword exposes the structure of data. In the gcd
function, `match x' first exposes x as a tuple of two ints, and then
distinguishes between tuples where the first value is, or is not 0.
The two patterns separated by '|' are tested from top to bottom, so
the second pattern matches all pairs (a,b) where a is not 0.
Some languages (python and perl) have the ability to deconstruct
certain built-in types (in python: (a,(b,c)) = (1,(2,(3,4))) will
assign a to 1, b to 2 and c to (3,4)). Full pattern matching was
recently added to Python but a key difference remains: python is not
statically typed. Statically type-safe features are a major advantage
of typed, functional languages. Static typing also means that the
compiler can generate more efficient code to pattern match.
In F\#, user-defined "algebraic" types are called **discriminated unions**:
*)
type expr = Num of int | Plus of expr*expr | Times of expr*expr | Minus of expr*expr | Neg of expr;;
//This will allow us to form expression trees such as
let t = Plus(Num(2),Times(Num(4),Neg(Num(3))));; // (2 + 4 * -3)
//Function to evaluate an expression:
let rec eval = function
| Num(n) -> n
| Plus(a,b) -> eval(a) + eval(b)
| Minus(a,b) -> eval(a) - eval(b)
| Times(Num(0),a) | Times(a,Num(0)) -> 0 // ***
| Times(a,b) -> eval(a) * eval(b)
| Neg(a) -> eval(a) * -1;;
//Function to convert expression tree to infix string:
let rec tostring = function
| Num(n) -> string(n)
| Plus(a,b) -> "(" + tostring(a) + " + " + tostring(b) + ")"
| Minus(a,b) -> "(" + tostring(a) + " - " + tostring(b) + ")"
| Times(a,b) -> tostring(a) + "*" + tostring(b)
| Neg(Neg(x)) -> tostring(x) // ***
| Neg(x) -> "-" + tostring(x);;
printfn "%s" (tostring t);;
??? How is Pattern Matching Different from If-else or Switch Statements ???
If we only pattern matched variables against simple types such as
integers or strings, and only matched one value at a time, then it would
indeed not be much different from a switch. But there are two
reasons that pattern matching is more than just syntactic sugar for
switch or if-else statements.
1. Deep pattern matching means that we can match against nested
data structures, which is not possible without nested if statements, or
nested switches. The structures that can be matched include tuples of
any length, which means that any number of values can be patterned matched
simultaneously.
2. Try this:
> let rec f = function
| Num(n) -> n
| Plus(x,Neg(y)) -> f(x) - f(y);;
| _ -> 0; // _ is a "wildcard" that matches any pattern
and this:
> let g = function
| "zero" -> 0
| "one" -> 1;;
You should get a warning for g that the patterns are incomplete.
If you were to compile the program (fsharpc/fsc) then you will notice
that the warning is given at compile time. Would you expect such a
warning if you left out a if-else clause or switch case? (No kids,
you shouldn't).
??? How is Pattern Matching Different from Dynamic Dispatch ???
1. Dynamic dispatch, the object oriented approach, entails *subtyping*
(inheritance). Whenever A is a subtype (subclass) of B, there is
always the possibility that downcasting from B to A might be needed,
which means that not all object-oriented code can be statically type
checked. But pattern matching does not rely on inheritance: there is
no dynamic dispatch and no type casting here. Pattern matching in F\#
is statically type safe.
2. Dynamic dispatch only works on one object at a time. In a method call
of the form a.f(b,c,d): dynamic dispatch can only occur on a. But what
about b, c and d? Argument types are only subject to static `overloading`
and not dynamic `overriding`. Only the language Julia does dynamic dispatch
on argument types (multiple dispatch) but Julia is not statically typed.
2b. We can dispatch to the right version of a procedure based on the
type tag on a single object, but not on the structure of nested
objects. In the F\# tostring function above, note the case marked ***:
the tostring function treats a double negative (Neg(Neg x)) as a
positive. This case demonstrates that pattern matching can expose the
entire, nested structure of data at runtime, much more than is
possible with dynamic dispatch (or with the is/instanceof check
combined with if-else), which can only check the structure of data at
the top level. The closest analog of a discriminated union is an
abstract interface called 'expr' and four subclasses, Num, Neg, Plus
and Times. Dynamic dispatch may be able to distinguish between these
four cases, but how could it distinguish between Neg(x) and
Neg(Neg(x))?
Even multiple dispatch in Julia can only look at the surface type of
objects and cannot do deep pattern matching.
??? How is Pattern Matching different from the .match function that
can be defined for type hierarchies in OOP languages (such as
for expression trees, numbers and options in C#).
I defined the .match function in an OOP setting to *simulate* real
functional programming. Just as I simulated OOP in C by implementing,
from scratch, inheritance, dynamic typing and dynamic dispatch, I was
simuating functional programming in C# by defining the .match function
for various inheritance hierarchies. But just as there are
limitations to C with regard to OOP, there are limitations to this
approach in how close it can get to real pattern matching. First,
the .match functions must be redefined for each type hierarchy: it's
not a built-in. Secondly, in order to set up multiple-dispatch (on
more than one object), I had to define rather elaborate, and tidious
functions like match2_commute and match2_upcast. Imagine having to to
do that for functions that can take 3, 4 or more arguments! But real
`match` can match any tuple of values of any type. Even more importantly,
there was no way to match against nested patterns such as Neg(Neg(x))
without calling a nested .match. Finally, there is no wildcard _ that
matches against all other cases.
****EXERCISE C1 (type up in editor and save as a .fs or .fsx file).
Modify the tostring function so that expressions such as 3 + -4 is
printed as (3 - 4). However, (5 + --2) should be printed as (5 + 2)
and not (5 - -2). Make sure your function is recursive so you can
handle nested cases: (1 + ---1) should also print as (1 - 1).
Hint: you need to add two clauses. Pattern matching will execute the
first clause where the match occurs (observe that the special cases for
evaluating 0*n and n*0 occur before the more general case for Times;
the special case for printing --n also appears before the more general
case for Neg).
*)
let t1 = Minus(Num(5),Neg(Num(2))); // 5 - -2
let t2 = Plus(Num(1),Neg(Neg(Neg(Num(1))))); // 1 + ---1
printfn "%s" (tostring t1);; // prints (5- -2) now, but should print (5 + 2)
printfn "%s" (tostring t2);; // prints (1 + -1) now, but should print (1 - 1)
(*
??? Are There Any Disadvantages of Pattern Matching ???
Yes. It would be more difficult to extend the existing definition of
'expr' with another case in a modular way. And it would not be
possible to add such a feature to the language without compromising
some degree of type safety (as in Scala). Compared to object-oriented
programming, pure functional programming is more "tightly coupled." You
must be reasonably sure that you know what an "expression" is before
you write code for it.
Because there are trade-offs between the functional/pattern matching
style of programming and the OOP style, F\# still contains the ability
to define classes, inheritance, and do dynamic dispatch. But with
these come the possibility of losing static type safety along with all the
other limitations of OOP. We will not look at how classes are defined
in F\#, because they're hardly better than C#, and the syntax is esoteric.
It is also possible to import a .dll built with C# and use it in F\#.
--- *)
(* ****** Pattern Matching against List Patterns:
You can pattern match just about any type, including referenced values
and arrays. However, the size of the array must be exact in order for
the match to succeed. Lists are better for pattern matching because they
are equivalent to "cons lists". A list such as [1;2;3] is equivalent
to 1::2::3::[]. Here, :: is "cons" and [] is the empty list. The
:: operator associates to the right so 1::2::3::[] should be read as
1::(2::(3::[])), which you can think of as cons(1,cons(2,cons(3,nil))).
> 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:
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.
************* ERROR HANDLING *************
As F\# is a .Net language designed to be interoperable with C# dll's, it
has exceptions, which can be handled with try-with blocks. It also
has null pointers, but they are discouraged.
*)
let x =
try int("abc")
with _ -> 1;
// This will assign x to 1 because int("abc") raised an exception that was
// caught by the 'with' clause. The with clause must return a value of the
// expected type, or raise another exception.
let x2= if x<>0 then 10/x else raise(System.Exception("division by zero"));
(* ******** Error Handling with the Option And Result Monads ******** *)
open System;
open Option
let safediv a b = if b<>0 then Some(a/b) else None;
// type of safediv inferred as int -> int -> int option
(Some 4)
|> map (fun x -> 4-x)
|> bind (safediv 1) // returns None
|> ignore;;
// The Result monad is similar to Option, but instead of None, a value
// of type Result is either Ok(x) where x is type A, or Error(y)
// where y is of type B. Instead of None, an Error Result carries
// more information about the type of error. map/bind and other
// monadic combinators are available for Result (consult F\# docs).
// Of course, you can always use match. option/result are just
// discriminated unions that we could've defined ourselves:
type myoption<'T> = Nothing | Something of 'T;;
// Demonstrating the result monad:
open Result;
let result= if x<>0 then Ok(10/x) else Error("division of 10 by zero");
// result is of type Result, or (int,string) Result
let res2 =
result |> map (fun x -> x*2)
match res2 with
| Ok(n) -> printfn "result = %A" n
| Error(e) -> printfn "ERROR: %A" e
// output: result = 20
// To distinguish map for option and map for Result, use Option.map or
// Result.map
(* ****** Other Kinds of Data Structures ******
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.
*)
//2. 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 = {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;};;
// Unchecked.defaultof<'t> is often null, unfortunately (blame java).
let s2 = makestack 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 :=.
// Besides records, there are also structs, which are allocated on the STACK
// unless they're part of a heap-allocated record or object.
type KVpair<'A,'B> = // key-value pair
struct
val mutable key:'A
val mutable value:'B
new(x,y) = {key=x; value=y;} // can have constructor of struct
override this.ToString() = sprintf "%A:%A" this.key this.value
end;;
let mutable p1 = KVpair("B",4);
printfn "p1 using ToString is %A" p1;;
// For an example of a full-scale "class", with inheritance and overriding,
// see https://cs.hofstra.edu/~cscccl/csc123/teams.fs
(* *** Sample Program: matching brackets (), [], {} ***
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)
*)