F Sharp Programming The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at https://en.wikibooks.org/wiki/F_Sharp_Programming Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License. Note to contributors: normally a preface is written by the author of a book. Since this book might have several authors, feel free to write your own preface. Written by Awesome Princess: Normally, authors choose to write a preface to a book about the book itself. But, just because I'm an egomaniac, I want to write about myself instead. Not because I'm an especially interesting person, but because my experiences with functional programming are relevant to the creation of this book. So, in 2006, I was becoming bored with my job. The only kind of software I've ever written has been software that puts a GUI interface on top of a database, and I just became tired with it. I wanted to find an interesting programming job. Just for fun, I started looking at job openings at different high tech companies (Google, eBay, Microsoft, Amazon, etc.). I noticed that all of the boring jobs—CRUD apps, simple web development—wanted programmers with Java, C#, or C++ experience. The interesting jobs—compiler programming, digital circuit verification, massively parallel computing, biometrics—sought programmers with experience in weird and unfamiliar languages. In particular: I read in Paul Graham's article Beating the Averages that the first version of Yahoo! Store was written largely in Lisp I came across job postings for Google looking for programmers with Haskell or Python experience in addition to C++. I read in an Erlang FAQ that the Erlang programming language is the tool of choice for telecommunications providers like T-Mobile. I've heard for years that Lisp was a niche language during the Golden Age of AI research. I ran across numerous Microsoft job postings in the area of driver verification looking for OCaml programmers. The most remarkable applications in the world aren't written in Java; they're written in these weird, obscure languages. More interestingly, the languages in the highest demand—Erlang, Haskell, Lisp, OCaml—were all functional programming languages, a wholly alien programming paradigm from my vantage point deep in C#-Land. I decided to supplement my programming wisdom by learning one of these obscure functional programming languages. The choice between one language or another wasn't too hard to make. If I'm going to learn a new language, it needs to satisfy a few conditions: it should be practical enough for personal use, relatively speedy, useful to employers, and impress my friends when I tell them I learned a weird new language. Haskell was quite scary to me at the time, and I can't really exploit Erlang's concurrency with the tiny scope of the apps I write for myself. The choice came down to Lisp and OCaml; based on these comparisons of different languages, I decided that OCaml's static-typing, speedy native code, tiny compiled binaries, and established niche in the financial market made it a good choice for me. I learned OCaml and it completely changed my way of thinking. After using the language and keeping up with OCaml newsgroups, I heard about a .NET port of OCaml called F#. I figured I already knew the .NET BCL inside and out, and I was already familiar with OCaml, I could probably learn this language pretty quickly. In August 2007, I took the time to get familiar with the F# language. While I picked up most of it fairly well, one thing I noticed about the language was how completely inaccessible it was to people trying to learn the language. The complete dearth of F# material out there just makes it impossible for beginners to learn F# as their first language. Even today, November 2008, there are only a handful of publications, but even as a person with many years of programming experience, I struggled to follow along and comprehend the language. For a long time, I wanted to write something that would actually be useful to F# neophytes, something that would contain everything anyone needs to know about the language into a single comprehensive resource. This book was originally started by a fellow Wikibookian in 2006, but no one had written any substantial content for it for nearly 2 years. I found this book and decided that, for the sake of people wanting to learn F#, I'd compile everything I knew about the language into a format that would be acceptable for first-time programmers. I am happy with the way the book has been progressing. Ultimately, I'd like people to link to this book as the preferred, definitive F# tutorial on the Internet. The F# programming language is part of Microsoft's family of .NET languages, which includes C#, Visual Basic.NET, JScript.NET, and others. As a .NET language, F# code compiles down to Common Language Infrastructure (CLI) byte code or Microsoft Intermediate Language (MSIL) which runs on top of the Common Language Runtime (CLR). All .NET languages share this common intermediate state which allows them to easily interoperate with one another and use the .NET Framework's Base Class Library (BCL), that is part of Standard Libraries. In many ways, it's easy to think of F# as a .NET implementation of OCaml, a well-known functional programming language from the ML family of functional programming languages. Some of F#'s notable features include type inference, pattern matching, interactive scripting and debugging, higher order functions, and a well-developed object model which allows programmers to mix object-oriented and functional programming styles seamlessly. There are three dominant programming paradigms used today: functional, imperative, and object-oriented programming. Functional programming is the oldest of the three, beginning with Information Processing Language in 1956 and made popular with the appearance of Lisp in 1958. Of course, in the highly competitive world of programming languages in the early decades of computing, imperative programming established itself as the industry norm and preferred choice of scientific researchers and businesses with the arrival of Fortran in 1957 and COBOL in 1959. While imperative languages became popular with businesses, functional programming languages continued to be developed primarily as highly specialized niche languages. For example, the APL programming language, developed in 1962, was developed to provide a consistent, mathematical notation for processing arrays. In 1973, Robin Milner at the University of Edinburgh developed the ML programming language to develop proof tactics for the LCF Theorem prover. Lisp continued to be used for years as the favored language of AI researchers. ML stands out among other functional programming languages; its polymorphic functions made it a very expressive language, while its strong typing and immutable data structures made it possible to compile ML into very efficient machine code. ML's relative success spawned an entire family of ML-derived languages, including Standard ML, Caml, its most famous dialect called OCaml which unifies functional programming with object-oriented and imperative styles, and Haskell. F# was developed in 2005 at Microsoft Research. In many ways, F# is essentially a .Net implementation of OCaml, combining the power and expressive syntax of functional programming with the tens of thousands of classes which make up the .NET class library. Functional programming is often regarded as the best-kept secret of scientific modelers, mathematicians, artificial intelligence researchers, financial institutions, graphic designers, CPU designers, compiler programmers, and telecommunications engineers. Understandably, functional programming languages tend to be used in settings that perform heavy number crunching, abstract symbolic processing, or theorem proving. Of course, while F# is abstract enough to satisfy the needs of some highly technical niches, its simple and expressive syntax makes it suitable for CRUD apps, web pages, GUIs, games, and general-purpose programming. Programming languages are becoming more functional every year. Features such as generic programming, type inference, list comprehensions, functions as values, and anonymous types, which have traditionally existed as staples of functional programming, have quickly become mainstream features of Java, C#, Delphi and even Fortran. We can expect next-generation programming languages to continue this trend in the future, providing a hybrid of both functional and imperative approaches that meet the evolving needs of modern programming. F# is valuable to programmers at any skill level; it combines many of the best features of functional and object-oriented programming styles into a uniquely productive language. http://research.microsoft.com At the time of this writing, its possible to run F# code through Visual Studio, through its interactive top-level F# Interactive (fsi), and compiling from the command line. This book will assume that users will compile code through Visual Studio or F# Interactive by default, unless specifically directed to compile from the command line. F# is included with Visual Studio 2019. Alternatively, users can download Visual Studio Express or Community for free, which will provide an F# pioneer with everything one needs to get started, including interactive debugging, breakpoints, watches, Intellisense, and support for F# projects. Make sure all instances of Visual Studio and Visual Studio Shell are closed before continuing. To get started, users should download and install the latest version of the .NET Framework from Microsoft. After successful installation, users will notice an additional folder in their start menu, "Microsoft F# 2.0.X.X." Additionally, users will notice that an entry for "F# Projects" has been added to the project types menu in Visual Studio. From here, users can create and run new F# projects. It is a good idea to add the executable location (e.g. c:\fsharp\bin\) to the %PATH% environment variable, so you can access the compiler and the F# interactive environment (FSI) from any location. As of Visual Studio 2019 the easiest way to get going is to install Visual Studio 2019 for Web at [1] (even if you want to do desktop solution). You can then select F# language support from within the installer. Once this is done you can create F# projects. Search Nuget for additional F# project types. Lets create the Hello World standalone application. Create a text file called hello.fs containing the following code: (* filename: hello.fs *) let _ = printf "Hello world" The underscore is used as a variable name when you are not interested in the value. All functions in F# return a value even if the main reason for calling the function is a side effect. Save and close the file and then compile this file: fsc -o hello.exe hello.fs Now you can run hello.exe to produce the expected output. Open a command-line console (hit the "Start" button, click on the "Run" icon and type cmd and hit ENTER). Type fsi and hit ENTER. You will see the interactive console: Microsoft F# Interactive, (c) Microsoft Corporation, All Rights Reserved F# Version 1.9.6.2, compiling for .NET Framework Version v2.0.50727 Please send bug reports to fsbugs@microsoft.com For help type #help;; > We can try some basic F# variable assignment (and some basic maths). > let x = 5;; val x : int > let y = 20;; val y : int > y + x;; val it : int = 25 Finally we quit out of the interactive environment > #quit;; Go to the Control Panel and choose System. The System Properties dialog will appear. Select the Advanced tab and click the "Environment Variables...". In the System Variables section, select the Path variable from the list and click the "Edit..." button. In the Edit System Variable text box append a semicolon (;) followed by the executable path (e.g. ;C:\fsharp\bin\) Click on the "OK" button Click on the "OK" button Click on the "Apply" button Now any command-line console will check in this location when you type fsc or fsi. F# runs on Mac OSX, Linux and other Unix versions with the latest Mono. This is supported by the F# community group called the F# Software Foundation. The F# Software Foundation give latest instructions on getting started with F# on Linux and Mac. Once built and/or installed, you can use the "fsharpi" command to use the command-line interpreter, and "fsharpc" for the command-line compiler. The F# Software Foundation also give instructions for installing the Monodevelop support for F#. This comes with project build system, code completion, and syntax highlighting support. The F# Software Foundation also give instructions for using F# with other editors. An emacs mode for F# is also available on Github. F# runs on Mac OSX and Windows with the latest Xamarin Studio. This is supported by Microsoft. Xamarin Studio is an IDE for developing cross-platform phone apps, but it runs on Mac OSX and implements F# with an interactive shell. Now that we have a working installation of F# we can explore the syntax of F# and the basics of functional programming. We'll start off in the Interactive F Sharp environment as this gives us some very valuable type information, which helps get to grips with what is actually going on in F#. Open F# interactive from the start menu, or open a command-line prompt and type fsi. In computer programming, every piece of data has a type, which, predictably, describes the type of data a programmer is working with. In F#, the fundamental data types are: F# is a fully object-oriented language, using an object model based on the .NET Common Language Infrastructure (CLI). As such, it has a single-inheritance, multiple interface object model, and allows programmers to declare classes, interfaces, and abstract classes. Notably, it has full support for generic class, interface, and function definitions; however, it lacks some OO features found in other languages, such as mixins and multiple inheritance. F# also provides a unique array of data structures built directly into the syntax of the language, which include: Unit, the datatype with only one value, equivalent to void in C-style languages. Tuple types, which are ad hoc data structures that programmers can use to group related values into a single object. Record types, which are similar to tuples, but provide named fields to access data held by the record object. Discriminated unions, which are used to create very well-defined type hierarchies and hierarchical data structures. Lists, Maps, and Sets, which represent immutable versions of a stack, hashtable, and set data structures, respectively. Sequences, which represent a lazy list of items computed on-demand. Computation expressions, which serve the same purpose as monads in Haskell, allowing programmers to write continuation-style code in an imperative style. All of these features will be further enumerated and explained in later chapters of this book. F# is a statically typed language, meaning that the compiler knows the datatype of variables and functions at compile time. F# is also strongly typed, meaning that a variable bound to ints cannot be rebound to strings at some later point; an int variable is forever tied to int data. Unlike C# and VB.Net, F# does not perform implicit casts, not even safe conversions (such as converting an int to a int64). F# requires explicit casts to convert between datatypes, for example: > let x = 5;; val x : int = 5 > let y = 6L;; val y : int64 = 6L > let z = x + y;; let z = x + y;; ------------^ stdin(5,13): error FS0001: The type 'int64' does not match the type 'int' > let z = (int64 x) + y;; val z : int64 = 11L The mathematical operators +, -, /, *, and % are overloaded to work with different datatypes, but they require arguments on each side of the operator to have the same datatype. We get an error trying to add an int to an int64, so we have to cast one of our variables above to the other's datatype before the program will successfully compile. Unlike many other strongly typed languages, F# often does not require programmers to use type annotations when declaring functions and variables. Instead, F# attempts to work out the types for you, based on the way that variables are used in code. For example, let's take this function: let average a b = (a + b) / 2.0 We have not used any type annotations: that is, we have not explicitly told the compiler the data type of a and b, nor have we indicated the type of the function's return value. If F# is a strongly, statically typed language, how does the compiler know the datatype of anything beforehand? That's easy, it uses simple deduction: The + and / operators are overloaded to work on different datatypes, but it defaults to integer addition and integer division without any extra information. (a + b) / 2.0, the value in bold has the type float. Since F# doesn't perform implicit casts, and it requires arguments on both sides of a math operator to have the same datatype, the value (a + b) must return a float as well. The + operator only returns float when both arguments on each side of the operator are floats, so a and b must be floats as well. Finally, since the return value of float / float is float, the average function must return a float. This process is called type-inference. On most occasions, F# will be able to work out the types of data on its own without requiring the programmer to explicitly write out type annotations. This works just as well for small programs as large programs, and it can be a tremendous time-saver. On those occasions where F# cannot work out the types correctly, the programmer can provide explicit annotations to guide F# in the right direction. For example, as mentioned above, math operators default to operations on integers: > let add x y = x + y;; val add : int -> int -> int In absence of other information, F# determines that add takes two integers and returns another integer. If we wanted to use floats instead, we'd write: > let add (x : float) (y : float) = x + y;; val add : float -> float -> float F#'s pattern matching is similar to an if... then or switch construct in other languages, but is much more powerful. Pattern matching allows a programmer to decompose data structures into their component parts. It matches values based on the shape of the data structure, for example: type Proposition = // type with possible expressions ... note recursion for all expressions except True | True // essentially this is defining boolean logic | Not of Proposition | And of Proposition * Proposition | Or of Proposition * Proposition let rec eval x = match x with | True -> true // syntax: Pattern-to-match -> Result | Not(prop) -> not (eval prop) | And(prop1, prop2) -> (eval prop1) && (eval prop2) | Or(prop1, prop2) -> (eval prop1) || (eval prop2) let shouldBeFalse = And(Not True, Not True) let shouldBeTrue = Or(True, Not True) let complexLogic = And(And(True,Or(Not(True),True)), Or(And(True, Not(True)), Not(True)) ) printfn "shouldBeFalse: %b" (eval shouldBeFalse) // prints False printfn "shouldBeTrue: %b" (eval shouldBeTrue) // prints True printfn "complexLogic: %b" (eval complexLogic) // prints False The eval method uses pattern matching to recursively traverse and evaluate the abstract syntax tree. The rec keyword marks the function as recursive. Pattern matching will be explained in more detail in later chapters of this book. F# is a mixed-paradigm language: it supports imperative, object-oriented, and functional styles of writing code, with heaviest emphasis on the latter. The first mistake a newcomer to functional programming makes is thinking that the let construct is equivalent to assignment. Consider the following code: let a = 1 (* a is now 1 *) let a = a + 1 (* in F# this throws an error: Duplicate definition of value 'a' *) On the surface, this looks exactly like the familiar imperative pseudocode: a = 1 // a is 1 a = a + 1 // a is 2 However, the nature of the F# code is very different. Every let construct introduces a new scope, and binds symbols to values in that scope. If execution escapes this introduced scope, the symbols are restored to their original meanings. This is clearly not identical to variable state mutation with assignment. To clarify, let us desugar the F# code: let a = 1 in ((* a stands for 1 here *); (let a = (* a still stands for 1 here *) a + 1 in (* a stands for 2 here *)); (* a stands for 1 here, again *)) Indeed the code let a = 1 in (printfn "%i" a; (let a = a + 1 in printfn "%i" a); printfn "%i" a) prints out 1 2 1 Once symbols are bound to values, they cannot be assigned a new value. The only way to change the meaning of a bound symbol is to shadow it by introducing a new binding for this symbol (for example, with a let construct, as in let a = a + 1), but this shadowing will only have a localized effect: it will only affect the newly introduced scope. F# uses so-called 'lexical scoping', which simply means that one can identify the scope of a binding by simply looking at the code. Thus the scope of the let a = a + 1 binding in (let a = a + 1 in ..) is limited by the parentheses. With lexical scoping, there is no way for a piece of code to change the value of a bound symbol outside of itself, such as in the code that has called it. Immutability is a great concept. Immutability allows programmers to pass values to functions without worrying that the function will change the value's state in unpredictable ways. Additionally, since value can't be mutated, programmers can process data shared across many threads without fear that the data will be mutated by another process; as a result, programmers can write multithreaded code without locks, and a whole class of errors related to race conditions and dead locking can be eliminated. Functional programmers generally simulate state by passing extra parameters to functions; objects are "mutated" by creating an entirely new instance of an object with the desired changes and letting the garbage collector throw away the old instances if they are not needed. The resource overheads this style implies are dealt with by sharing structure. For example, changing the head of a singly-linked list of 1000 integers can be achieved by allocating a single new integer, reusing the tail of the original list (of length 999). For the rare cases when mutation is really needed (for example, in number-crunching code which is a performance bottleneck), F# offers reference types and .NET mutable collections (such as arrays). Imperative programming languages tend to iterate through collections with loops: void ProcessItems(Item[] items) { for(int i = 0; i < items.Length; i++) { Item myItem = items[i]; proc(myItem); // process myItem } } This admits a direct translation to F# (type annotations for i and item are omitted because F# can infer them): let processItems (items : Item []) = for i in 0 .. items.Length - 1 do let item = items. [i] in proc item However, the above code is clearly not written in a functional style. One problem with it is that it traverses an array of items. For many purposes including enumeration, functional programmers would use a different data structure, a singly linked list. Here is an example of iterating over this data structure with pattern matching: let rec processItems = function | [] -> () // empty list: end recursion | head :: tail -> // split list in first item (head) and rest (tail) proc head; processItems tail // recursively enumerate list It is important to note that because the recursive call to processItems appears as the last expression in the function, this is an example of so-called tail recursion. The F# compiler recognizes this pattern and compiles processItems to a loop. The processItems function therefore runs in constant space and does not cause stack overflows. F# programmers rely on tail recursion to structure their programs whenever this technique contributes to code clarity. A careful reader has noticed that in the above example proc function was coming from the environment. The code can be improved and made more general by parameterizing it by this function (making proc a parameter): let rec processItems proc = function | [] -> () | hd :: tl -> proc hd; processItems proc tl // recursively enumerate list This processItems function is indeed so useful that it has made it into the standard library under the name of List.iter. For the sake of completeness it must be mentioned that F# includes generic versions of List.iter called Seq.iter (other List. * functions usually have Seq. * counterparts as well) that works on lists, arrays, and all other collections. F# also includes a looping construct that works for all collections implementing the System.Collections.Generic.IEnumerable: for item in collection do process item Traditional OO uses implementation inheritance extensively; in other words, programmers create base classes with partial implementation, then build up object hierarchies from the base classes while overriding members as needed. This style has proven to be remarkably effective since the early 1990s, however this style is not contiguous with functional programming. Functional programming aims to build simple, composable abstractions. Since traditional OO can only make an object's interface more complex, not simpler, inheritance is rarely used at all in F#. As a result, F# libraries tend to have fewer classes and very "flat" object hierarchies, as opposed to very deep and complex hierarchies found in equivalent Java or C# applications. F# tends to rely more on object composition and delegation rather than inheritance to share snippets of implementation across modules. F# is a functional programming language, meaning that functions are first-order data types: they can be declared and used in exactly the same way that any other variable can be used. In an imperative language like Visual Basic, there has traditionally been a fundamental difference between variables and functions. Function MyFunc(param As Integer) MyFunc = (param * 2) + 7 End Function ' The program entry point; all statements must exist in a Sub or Function block. Sub Main() Dim myVal As Integer ' Also statically typed as Integer, as the compiler (for newer versions of VB.NET) performs local type inference. Dim myParam = 2 myVal = MyFunc(myParam) End Sub Notice the difference in syntax between defining and evaluating a function and defining and assigning a variable. In the preceding Visual Basic code we could perform a number of different actions with a variable we can: create a token (the variable name) and associate it with a type assign it a value interrogate its value pass it into a function or subroutine (a function that returns no value) return it from a function Functional programming makes no distinction between values and functions, so we can consider functions to be equal to all other data types. That means that we can: create a token (the function variable name) and associate it with a type assign it a value (the actual calculation) interrogate its value (perform the calculation) pass a function as a parameter of another function or subroutine return a function as the result of another function A simple, non-trivial F# program has the following parts: open System (* This is a multi-line comment *) // This is a single-line comment let rec fib = function | 0 -> 0 | 1 -> 1 | n -> fib (n - 1) + fib (n - 2) [] let main argv = printfn "fib 5: %i" (fib 5) 0 Most F# code files begin with a number of open statements used to import namespaces, allowing programmers to reference classes in namespaces without having to write fully qualified type declarations. This keyword is functionally equivalent to the using directive in C# and Imports directive in VB.Net. For example, the Console class is found under the System namespace; without importing the namespace, a programmer would need to access the Console class through its fully qualified name, System.Console. The body of the F# file usually contains functions to implement the business logic in an application. Finally, many F# application exhibit this pattern: [] let main argv = // Code to be executed 0 The entry point of an F# program is marked by the [] attribute, and following it must be a function that accepts an array of strings as input and returns an integer (by default, 0) Compared to other .NET languages such as C# and VB.Net, F# has a somewhat terse and minimalistic syntax. To follow along in this tutorial, open F# Interactive (fsi) or Visual Studio and run the examples. The most ubiquitous, familiar keyword in F# is the let keyword, which allows programmers to declare functions and variables in their applications. For example: let x = 5 This declares a variable called x and assigns it the value 5. Naturally, we can write the following: let x = 5 let y = 10 let z = x + y z now holds the value 15. A complete program looks like this: let x = 5 let y = 10 let z = x + y printfn "x: %i" x printfn "y: %i" y printfn "z: %i" z The statement printfn prints text out to the console window. As you might have guessed, the code above prints out the values of x, y, and z. This program results in the following: x: 5 y: 10 z: 15 Note to F# Interactive users: all statements in F# Interactive are terminated by ;; (two semicolons). To run the program above in fsi, copy and paste the text above into the fsi window, type ;;, then hit enter. In F#, "variable" is a misnomer. In reality, all "variables" in F# are immutable; in other words, once you bind a "variable" to a value, it's stuck with that value forever. For that reason, most F# programmers prefer to use "value" rather than "variable" to describe x, y, and z above. Behind the scenes, F# actually compiles the "variables" above as static read-only properties. There is little distinction between functions and values in F#. You use the same syntax to write a function as you use to declare a value: let add x y = x + y add is the name of the function, and it takes two parameters, x and y. Notice that each distinct argument in the functional declaration is separated by a space. Similarly, when you execute this function, successive arguments are separated by a space: let z = add 5 10 This assigns z the return value of this function, which in this case happens to be 15. Naturally, we can pass the return value of functions directly into other functions, for example: let add x y = x + y let sub x y = x - y let printThreeNumbers num1 num2 num3 = printfn "num1: %i" num1 printfn "num2: %i" num2 printfn "num3: %i" num3 printThreeNumbers 5 (add 10 7) (sub 20 8) This program outputs: num1: 5 num2: 17 num3: 12 Notice that I have to surround the calls to add and sub functions with parentheses; this tells F# to treat the value in parentheses as a single argument. Otherwise, if we wrote printThreeNumbers 5 add 10 7 sub 20 8, its not only incredibly difficult to read, but it actually passes 7 parameters to the function, which is obviously incorrect. Unlike many other languages, F# functions do not have an explicit keyword to return a value. Instead, the return value of a function is simply the value of the last statement executed in the function. For example: let sign num = if num > 0 then "positive" elif num < 0 then "negative" else "zero" This function takes an integer parameter and returns a string. As you can imagine, the F# function above is equivalent to the following C# code: string Sign(int num) { if (num > 0) return "positive"; else if (num < 0) return "negative"; else return "zero"; } Just like C#, F# is a strongly typed language. A function can only return one datatype; for example, the following F# code will not compile: let sign num = if num > 0 then "positive" elif num < 0 then "negative" else 0 If you run this code in fsi, you get the following error message: > let sign num = if num > 0 then "positive" elif num < 0 then "negative" else 0;; else 0;; ---------^ stdin(7,10): error FS0001: This expression was expected to have type string but here has type int The error message is quite explicit: F# has determined that this function returns a string, but the last line of the function returns an int, which is an error. Interestingly, every function in F# has a return value; of course, programmers don't always write functions that return useful values. F# has a special datatype called unit, which has just one possible value: (). Functions return unit when they don't need to return any value to the programmer. For example, a function that prints a string to the console obviously doesn't have a return value: let helloWorld () = printfn "hello world" This function takes unit parameter and returns (). You can think of unit as the equivalent to void in C-style languages. All functions and values in F# have a data type. Open F# Interactive and type the following: > let addAndMakeString x y = (x + y).ToString();; F# reports the data type using chained arrow notation as follows: val addAndMakeString : x:int -> y:int -> string Data types are read from left to right. Before muddying the waters with a more accurate description of how F# functions are built, consider the basic concept of Arrow Notation: starting from the left, our function takes two int inputs and returns a string. A function only has one return type, which is represented by the rightmost data type in chained arrow notation. We can read the following data types as follows: int -> string takes one int input, returns a string float -> float -> float takes two float inputs, returns another float int -> string -> float takes an int and a string input, returns a float This description is a good introductory way to understand Arrow Notation for a beginner—and if you are new to F# feel free to stop here until you get your feet wet. For those who feel comfortable with this concept as described, the actual way in which F# is implementing these calls is via currying the function. While the above description of Arrow Notation is intuitive, it is not entirely accurate due to the fact that F# implicitly curries functions. This means that a function only ever has a single argument and a single return type, quite at odds with the previous description of Arrow Notation above where in the second and third example two arguments are passed to a function. In reality, a function in F# only ever has a single argument and a single return type. How can this be? Consider this type: float -> float -> float since a function of this type is implicitly curried by F#, there is a two step process to resolve the function when called with two arguments a function is called with the first argument that returns a function that takes a float and returns a float. To help clarify currying, lets call this function funX (note that this naming is just for illustration purposes—the function that gets created by the runtime is anonymous). the second function ('funX' from step 1 above) is called with the second argument, returning a float So, if you provide two floats, the result appears as if the function takes two arguments, though this is not actually how the runtime behaves. The concept of currying will probably strike a developer not steeped in functional concepts as very strange and non-intuitive—even needlessly redundant and inefficient, so before attempting a further explanation, consider the benefits of curried functions via an example: let addTwoNumbers x y = x + y this type has the signature of int -> int -> int then this function: let add5ToNumber = addTwoNumbers 5 with the type signature of (int -> int). Note that the body of add5ToNumber calls addTwoNumbers with only one argument—not two. It returns a function that takes an int and returns an int. In other words, add5toNumber partially applies the addTwoNumbers function. > let z = add5ToNumber 6;; val z : int = 11 This partial application of a function with multiple argument exemplifies the power of curried functions. It allows deferred application of the function, allowing for more modular development and code re-use—we can re-use the addTwoNumbers function to create a new function via partial application. From this, you can glean the power of function currying: it is always breaking down function application to the smallest possible elements, facilitating greater chances for code-reuse and modularity. Take another example, illustrating the use of partially applied functions as a bookkeeping technique. Note the type signature of holdOn is a function (int -> int) since it is the partial application of addTwoNumbers > let holdOn = addTwoNumbers 7;; val holdOn : (int -> int) > let okDone = holdOn 8;; val okDone : int = 15 Here we define a new function holdOn on the fly just to keep track of the first value to add. Then later we apply this new 'temp' function holdOn with another value which returns an int. Partially applied functions—enabled by currying—is a very powerful means of controlling complexity in F#. In short, the reason for the indirection resulting from currying function calls affords partial function application and all the benefits it supplies. In other words, the goal of partial function application is enabled by implicit currying. So while the Arrow Notation is a good shorthand for understanding the type signature of a function, it does so at the price of oversimplification, for a function with the type signature of f : int -> int -> int is actually (when taking into consideration the implicit currying): // curried version pseudo-code f: int -> (int -> int) In other words, f is a function that takes an int and returns a function that takes an int and returns an int. Moreover, f: int -> int -> int -> int is a simplified shorthand for // curried version pseudo-code f: int -> (int -> (int -> int)) or, in very difficult to decode English: f is a function that takes an int and returns a function that takes an int and returns a function that takes an int and returns an int. Yikes! F# allows programmers to nest functions inside other functions. Nested functions have a number of applications, such as hiding the complexity of inner loops: let sumOfDivisors n = let rec loop current max acc = if current > max then acc else if n % current = 0 then loop (current + 1) max (acc + current) else loop (current + 1) max acc let start = 2 let max = n / 2 (* largest factor, apart from n, cannot be > n / 2 *) let minSum = 1 + n (* 1 and n are already factors of n *) loop start max minSum printfn "%d" (sumOfDivisors 10) (* prints 18, because the sum of 10's divisors is 1 + 2 + 5 + 10 = 18 *) The outer function sumOfDivisors makes a call to the inner function loop. Programmers can have an arbitrary level of nested functions as need requires. In programming, a generic function is a function that returns an indeterminate type t without sacrificing type safety. A generic type is different from a concrete type such as an int or a string; a generic type represents a type to be specified later. Generic functions are useful because they can be generalized over many different types. Let's examine the following function: let giveMeAThree x = 3 F# derives type information of variables from the way variables are used in an application, but F# can't constrain the value x to any particular concrete type, so F# generalizes x to the generic type 'a: 'a -> int this function takes a generic type 'a and returns an int. When you call a generic function, the compiler substitutes a function's generic types with the data types of the values passed to the function. As a demonstration, let's use the following function: let throwAwayFirstInput x y = y Which has the type 'a -> 'b -> 'b, meaning that the function takes a generic 'a and a generic 'b and returns a 'b. Here are some sample inputs and outputs in F# interactive: > let throwAwayFirstInput x y = y;; val throwAwayFirstInput : 'a -> 'b -> 'b > throwAwayFirstInput 5 "value";; val it : string = "value" > throwAwayFirstInput "thrownAway" 10.0;; val it : float = 10.0 > throwAwayFirstInput 5 30;; val it : int = 30 throwAwayFirstInput 5 "value" calls the function with an int and a string, which substitutes int for 'a and string for 'b. This changes the data type of throwAwayFirstInput to int -> string -> string. throwAwayFirstInput "thrownAway" 10.0 calls the function with a string and a float, so the function's data type changes to string -> float -> float. throwAwayFirstInput 5 30 just happens to call the function with two ints, so the function's data type is incidentally int -> int -> int. Generic functions are strongly typed. For example: let throwAwayFirstInput x y = y let add x y = x + y let z = add 10 (throwAwayFirstInput "this is a string" 5) The generic function throwAwayFirstInput is defined again, then the add function is defined and it has the type int -> int -> int, meaning that this function must be called with two int parameters. Then throwAwayFirstInput is called, as a parameter to add, with two parameters on itself, the first one of type string and the second of type int. This call to throwAwayFirstInput ends up having the type string -> int -> int. Since this function has the return type int, the code works as expected: > add 10 (throwAwayFirstInput "this is a string" 5);; val it : int = 15 However, we get an error when we reverse the order of the parameters to throwAwayFirstInput: > add 10 (throwAwayFirstInput 5 "this is a string");; add 10 (throwAwayFirstInput 5 "this is a string");; ------------------------------^^^^^^^^^^^^^^^^^^^ stdin(13,31): error FS0001: This expression has type string but is here used with type int. The error message is very explicit: The add function takes two int parameters, but throwAwayFirstInput 5 "this is a string" has the return type string, so we have a type mismatch. Later chapters will demonstrate how to use generics in creative and interesting ways. Pattern matching is used for control flow; it allows programmers to look at a value, test it against a series of conditions, and perform certain computations depending on whether that condition is met. While pattern matching is conceptually similar to a series of if ... then statements in other languages, F#'s pattern matching is much more flexible and powerful. In high level terms, pattern matching resembles this: match expr with | pat1 -> result1 | pat2 -> result2 | pat3 when expr2 -> result3 | _ -> defaultResult Each | defines a condition, the -> means "if the condition is true, return this value...". The _ is the default pattern, meaning that it matches anything, sort of like a wildcard. Using a real example, it's easy to calculate the nth Fibonacci number using pattern matching syntax: let rec fib n = match n with | 0 -> 0 | 1 -> 1 | _ -> fib (n - 1) + fib (n - 2) We can experiment with this function in fsi: fib 1;; val it : int = 1 > fib 2;; val it : int = 1 > fib 5;; val it : int = 5 > fib 10;; val it : int = 55 It's possible to chain together multiple conditions which return the same value. For example: > let greeting name = match name with | "Steve" | "Kristina" | "Matt" -> "Hello!" | "Carlos" | "Maria" -> "Hola!" | "Worf" -> "nuqneH!" | "Pierre" | "Monique" -> "Bonjour!" | _ -> "DOES NOT COMPUTE! ";; val greeting : string -> string > greeting "Monique";; val it : string = "Bonjour!" > greeting "Pierre";; val it : string = "Bonjour!" > greeting "Kristina";; val it : string = "Hello!" > greeting "Sakura";; val it : string = "DOES NOT COMPUTE!" Pattern matching is such a fundamental feature that F# has a shorthand syntax for writing pattern matching functions using the function keyword: let something = function | test1 -> value1 | test2 -> value2 | test3 -> value3 It may not be obvious, but a function defined in this way actually takes a single input. Here's a trivial example of the alternative syntax: let getPrice = function | "banana" -> 0.79 | "watermelon" -> 3.49 | "tofu" -> 1.09 | _ -> nan (* nan is a special value meaning "not a number" *) Although it doesn't appear as if the function takes any parameters, it actually has the type string -> float, so it takes a single string parameter and returns a float. You call this function in exactly the same way that you'd call any other function: > getPrice "tofu";; val it : float = 1.09 > getPrice "banana";; val it : float = 0.79 > getPrice "apple";; val it : float = nan You can add additional parameters to the definition: let getPrice taxRate = function | "banana" -> 0.79 * (1.0 + taxRate) | "watermelon" -> 3.49 * (1.0 + taxRate) | "tofu" -> 1.09 * (1.0 + taxRate) | _ -> nan (* nan is a special value meaning "not a number" *) val getPrice : taxRate:float -> _arg1:string -> float Calling this gives: > getPrice 0.10 "tofu";; val it : float = 1.199 Note that the added parameters in the call come before the implicit parameter against which the match is made. F#'s pattern matching syntax is subtly different from "switch statement" structures in imperative languages, because each case in a pattern has a return value. For example, the fib function is equivalent to the following C#: int Fib(int n) => n switch { 0 => 0, 1 => 1, _ => Fib(n - 1) + Fib(n - 2) }; Like all functions, pattern matches can only have one return type. Pattern matching is not a fancy syntax for a switch structure found in other languages, because it does not necessarily match against values, it matches against the shape of data. F# can automatically bind values to identifiers if they match certain patterns. This can be especially useful when using the alternative pattern matching syntax, for example: let rec factorial = function | 0 | 1 -> 1 | n -> n * factorial (n - 1) The variable n is a pattern. If the factorial function is called with a 5, the 0 and 1 patterns will fail, but the last pattern will match and bind the value to the identifier n. Note to beginners: variable binding in pattern matching often looks strange to beginners, however it is probably the most powerful and useful feature of F#. Variable binding is used to decompose data structures into component parts and allow programmers to examine each part; however, data structure decomposition is too advanced for most F# beginners, and the concept is difficult to express using simple types like ints and strings. This book will discuss how to decompose data structures using pattern matching in later chapters. Occasionally, it's not enough to match an input against a particular value; we can add filters, or guards, to patterns using the when keyword: let sign = function | 0 -> 0 | x when x < 0 -> -1 | x when x > 0 -> 1 The function above returns the sign of a number: -1 for negative numbers, +1 for positive numbers, and '0' for 0: > sign -55;; val it : int = -1 > sign 108;; val it : int = 1 > sign 0;; val it : int = 0 Variable binding is useful because it's often required to implement guards. Note that F#'s pattern matching works from top to bottom: it tests a value against each pattern, and returns the value of the first pattern which matches. It is possible for programmers to make mistakes, such as placing a general case above a specific (which would prevent the specific case from ever being matched), or writing a pattern which doesn't match all possible inputs. F# is smart enough to notify the programmer of these types of errors. Example With Incomplete Pattern Matches > let getCityFromZipcode zip = match zip with | 68528 -> "Lincoln, Nebraska" | 90210 -> "Beverly Hills, California";; match zip with ----------^^^^ stdin(12,11): warning FS0025: Incomplete pattern matches on this expression. For example, the value '0' will not be matched val getCityFromZipcode : int
{'wiki_source': 'wikibooks', 'other_info': "{'content_model': 'wikitext', 'language': 'en', 'title': 'F Sharp Programming/Print version', 'type': 'text'}"}