Partager via

A Little on Generalization, Reuse and Parameterization in F#

  • Article

In this post I want to briefly touch on one of the main ways in which F# makes routine programming tasks simple.  One of the most common forms of code reuse involves taking existing code and making it more general, that is, reusing a basic algorithm or coding pattern by configuring essentially the same code in different ways.  This "code factoring" and "code reuse" is at the heart of much day-to-day programming.

In F# this is typically achieved by having your code accept one or more functions (perhaps ones that cause side-effects) as arguments, and also by having your code accept additional type parameters whose values are manipulated by these functions.  This is so easy to arrange that most F# programmers transform, factor and reuse their code as a routine part of programming without needing to really think about the constructs they are using to do this: you can achieve a lot of reuse without even needing to think "class", "interface" or "abstract" - and not having to explicitly design your reuse mechanisms can save a considerable amount of time and reduce the conceptual burden of your programming language.  Furthermore a good number of "extensibile architectures" can be expressed by parameterization of generic code by generic functions (perhaps ones that cause side-effects). 

In this post I want to indicate how syntactically simple it is to take existing F# code and generalize it, and how type inference typically chooses the most general possible type for a piece of code as you add extra function parameters.  This means that the process of transforming your code to be configurable and reusable is very simple, predictable and reliable, and requires almost no effort at all.

For example, the code

let buildTable (ns: List<int>) = List.fold_left (fun m n -> Map.add n (n*n) m) Map.empty ns

builds a Map<int,int> from a list of integers where the map takes integers to their squares.  I've added the type annotations "List<int>" to help beginners read the code - the Visual Studio mode would show this to you if you hover the mouse, and advnaced users would not normally write them.  You can write this as "int list" if you like, and F# will often print the type like this.  Also if you're not familiar with it the "fold_left" function is a way of specifying a comprehension, i.e. iterate the list and perform the "add" action specified by the "fun" lambda expression.  You could also write the code in many other ways, e.g. as:

 let rec buildTableAux (ns: List<int>) acc =
   match ns with
| [] -> acc
| n :: t -> buildTableAux t (Map.add n (n*n) acc)

 let buildTable ns acc = buildTableAux ns Map.empty

Anyway, the point of this blog is that either version of this code can be transformed into a generic implementation simply by taking appropriate arguments. For example,

let buildTable f (ns: List<'a>) = List.fold_left (fun m n -> Map.add n (f n) m) Map.empty ns

The type inferred for the return type of buildTable is now "Map<'a,'b>", where the input function "f" has type "'a -> 'b".  That is, type inference has automatically generalized the code to have the most general type possible!  Note how simple it was to produce an extensible, generalized version of our original code - if you ignore the type annotations, only a few characters changed.  The whole type signature is

 val buildTable: ('a -> 'b) -> List<'a> -> Map<'a,'b>

At the call site the

 buildTable [3;4;5]

becomes a call taking an appropriate function:

 buildTable (fun n -> n*n) [3;4;5]

 buildTable (fun n -> String.length(n)) ["James";"Byron";"Don"]

Here "extensibility" means "parameterization" - this is the kind of extensibility that F# and languages such as ML and Haskell excel at.  You can achieve a lot of reuse and factorization through these techniques, even to the extent of building useful products.  All F# programmers should know how to turn existing code into parameterized code, and to recognise patterns like the above.  Parameterization via functions and types can be taken too far, but it is an essential technique when used correctly.

Comments

  • Anonymous
    May 07, 2007
    I'm completely new to F#, but have a background in C++ template programming. The first thing I tried in F# was: let f x y = x + y let t1 = f 1 2 let t2 = f 1.0 2.0 This however, does not compile; once the type of f is determined to be int, it cannot be used as a float: "test.fs(3,10): error: FS0001: This expression has type int but is here used with type float" I explicitly tried to make f generic, like: let f : 'a -> 'a -> 'a = fun x y -> x + y let a = f 1.0 2.0 let b = f 1 2 but I got the same error. From a C++ point of view this is very bizarre.   I'm sure this is a beginners mistake, and a solution must exist?

  • Anonymous
    May 07, 2007
    Hi Zirax, Take a look at Chapter 5 of the draft "Expert F#" chapters. It's got a section on "making things generic".  It works differntly to C++, because dictionaries of functions are passed explicitly, but type inference normally makes that palatable.