How to Think Like a Functional Programmer

Marc Clifton

4.96/5 (64 votes)

26 Sep 2012CPOL47 min read

87.1K

Lessons learned about FP from the perspective of an Object Oriented programmer

Introduction

When I first encountered F# (and Functional Programming, or FP) my initial reaction was two-fold: so what, and why? I decided to try and answer those questions by writing a few less-than-trivial components in F#. What struck me first was that I could tell that my code still looked imperative - lots of mutable variables, "for" loops instead of recursion, etc. I thought, this is interesting, I have to actually learn how to think differently with FP, which led to deeper questions - why do I have to think differently, how do I think differently, and finally, is thinking more in FP terms actually an improvement in how I architect applications?

These were a more interesting questions to me than the syntactical differences between F# and C#. How to think in FP terms was something that I also found lacking - most of the resources on FP dive right into how great FP is in processing lists, which isn't teaching me anything about why its better and how to think like an FP programmer. Also, I was intrigued because it is rare that I encounter something (at least in technological circles) that requires me to re-evaluate my concepts of programming at a fundamental level. I do not subscribe to the dogmatic "FP is better" evangelizing that goes on (even as I myself evangelize my own ideas!), but I figured that there was probably something of value about FP that could improve my software architecture abilities if brought in balance with practices that I already consider to be fundamental techniques for anything but trivial applets.

Therefore, in this article, I will explore what it is about one's thinking that needs to shift and the balanced benefits of having another way of thinking about application development that can be added to the imperative / object-oriented tool chest, and more to the point, why FP facilitates a different way of thinking. To some, this might be obvious, but it was far from obvious for me, having been mired in OO architecture and working with imperative languages for the last 30 years. Nor will I advocate that FP is fundamentally better - it is different, and when a problem requires something different, FP is another tool to consider. While I will provide examples of OO paradigms supported by F#, I will take the position that this is "bad" FP, and look instead at how, by thinking differently, we can avoid OO constructs and live more in the world of pure FP thinking. All of the examples here are implemented in VS2010. I have not found any code incompatibility issues with VS2008 and the F# plugin, nor with VS2011.

For those that don't want to read the whole article, feel free to skip to the summary for the "leading thoughts" that illustrate the difference between OOP / imperative thinking and FP thinking.

Also, the reader is expected to have some familiarity already with F#, particularly with the way class types are defined and the "match" statement.

Getting Started

The first thing that I decided I needed to figure out was out how to put my toe into the water, and that meant learning how to call F# functions from C#, with which I'm already intimately familiar. Also, I'd read a lot about FP and mutability and words I never encountered before like currying, closures, continuations, and monads. Figuring out how to code in a language that is naturally immutable took me down the first "think differently" rabbit hole with regards to variables, state, and list management. Furthermore, I discovered that anything having to do with lists is typically handled in FP with recursion rather than looping. In imperative languages, recursion always raises the specter of stack overflows (too many recursive calls) and performance issues (exactly how many levels of function calls do I need to return from?), so this was an immediate red flag for me that needed to be closely looked at to see if this made any sense to actually use FP for anything practical, meaning, the processing of sometimes millions of items in a collection. Lastly, when I finally got my head wrapped around FP sufficiently to do something somewhat practical and actually applicable to FP, I encountered some significant gotcha's with another feature of FP, type inference.

Calling F# from C#

Probably 95% of my code base is in C# at this point, so it seemed natural to figure out how to call F# function from C#. This would at least provide a foundation that I am intimately familiar with, from which to springboard into F#.

From a blank solution, create a C# console project and an F# project, and reference the F# project in the C# project's references:

In the default "Module1.fs" file that VS2010 creates, replace the module name and create a simple function two add two parameters:

module FSModule

let Add x y = x + y

In the C# program, call the function and write the result to the console:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace WhyFP
{
  class Program
  {
    static void Main(string[] args)
    {
      int ret = FSModule.Add(1, 2);
      Console.WriteLine(ret);
    }
  }
}

Yay, it worked:

Tool Issue: Intellisense

If you typed in this example instead of copy-pasting from the article, you will discover that FSModule is not highlighted, and because Intellisense doesn't know about the FSModule module, the Add method isn't known, so Intellisense fails you again. So, this is the first thing one encounters - in order for Intellisense to work, the F# library must be compiled first! This behavior is different than occurs working in other .NET OO languages.

Modules and Namespaces

No code is required to define a module. If a codefile does not contain a leading namespace or module declaration, F# code will implicitly place the code in a module, where the name of the module is the same as the file name with the first letter capitalized. To access code in another module, simply use . notation: moduleName.member. Notice that this notation is similar to the syntax used to access static members -- this is not a coincidence. F# modules are compiled as classes which only contain static members, values, and type definitions.¹

Being used to namespaces, and knowing the F# supported namespaces, I wanted to understand the difference between namespaces and modules. This code results in the error "Namespaces cannot contain values.":

namespace FSModuleNS

let Add x y = x + y

Namespaces are used only for hierarchical categorization of modules, classes, and other namespaces¹. Therefore, the F# code has to look like this:

namespace FSModuleNS
  module FSModule =
    let Add x y = x + y

and the C# code would be modified to call the Add function this way:

int ret = FSModuleNS.FSModule.Add(1, 2);

This might seem trivial, but it's a slight shift from how we go about defining things in C# and is work noting.

Forward References

I rapidly discovered two other "problems" with F# code, both involving forward references. These may seem trivial but it is illustrative of the many "WTF?" experiences one can have learning a new language and development environment.

Module Forward References

Add another module, we'll call it "Xyz.fs" and the function:

module Xyz
let MagicNumber = 5

then reference this function in the Add function:

let Add x y = x + y + Xyz.MagicNumber

This will result in a compiler error "The module or namespace 'Xyz' is not defined. This is because F# does not permit forward references in the file listings of the project. The project files:

must be rearranged as follows:

Module Declarations: Top Level vs. Local

While I'm on the subject, notice that the module definition Xyz.fs is not followed by and '='. This is a top level module declaration. This one:

module FSModule =

is a local module declaration. Basically, a top level module declaration applies to the entire contents of a file, whereas local module declarations let you partition the file into different modules. Here is the salient point though with regards to the implementation: A module "...is implemented as a common language runtime (CLR) class that has only static members."²

One uses the "open" keyword (similar to "using") to avoid having to qualify the module name. For example:

namespace FSModuleNS
  open Xyz
  module FSModule =
    let Add x y = x + y + MagicNumber

This keyword applies to F# modules as well as .NET namespaces.

Type Forward References

This is a somewhat contrived example:

type Customer =
  {
    FirstName : Name;
    LastName : Name;
  }

type Name = string

but is illustrative of the fact that F# does not support forward references. The above code will result in the error "The type 'Name' is not defined. To fix this, we need to use the "and" keyword:

type Customer =
  {
    FirstName : Name;
    LastName : Name;
  }
and 
  Name = string

Mutability

Everything about OO / imperative languages is mutable. I certainly don't usually go about making fields in C# readonly - at best a property might have a protected or private setter (or no setter at all), but which still allows the implementing class to modify the underlying field value. Conversely, everything about FP is about immutability - you have to explicitly use the mutable keyword to make something modifiable. This is the first real mental stumbling block to thinking in functional programming terms, because it begs the question, how do you actually do anything in FP then?

FP Thinking, #1: In functional programming, we must embrace the idea and its implications that, once something is initialized, it cannot be changed.

Let's look at this a little closer. Let's consider a simple traffic light class (please ignore all the casting around the enum usage, it's bad design, but I wanted a short and simple example):

public class TrafficLight
{
  public enum State { Red, Green, Yellow };
  public State LightState { get; protected set; }

  protected int[] stateDurations = { 10, 5, 1 };
  protected DateTime transitionTime;

  public TrafficLight()
  {
    LightState = State.Red;
    InitializeDuration();
  }

  public bool CheckState()
  {
    bool lightChanged = false;

    if (DateTime.Now >= transitionTime)
    {
        LightState = (State)(((int)LightState + 1) % 3);
        InitializeDuration();
        lightChanged = true;
    }

    return lightChanged;
  }

  protected void InitializeDuration()
  {
    int durationAtState = stateDurations[(int)LightState];
    transitionTime = DateTime.Now.AddSeconds(durationAtState);
  }
}

You can verify that this code works (10 seconds of red, 5 seconds of green, 1 second of yellow, etc) by writing a simple looping test case:

TrafficLight tl = new TrafficLight();

for (int i = 0; i < 20; i++)
{
  tl.CheckState();
  Console.WriteLine(tl.LightState);
  System.Threading.Thread.Sleep(1000);
}

The "problem", if you will, with OOP is that classes do not just provide a wrapper for methods (thus addressing issues such as modularity) but they also manage state.

A class, in OOP, once instantiated, is a little package of state and methods (aka functions) that you can call to "compute" something based on the current state, along with functions that will alter the current state. Often you have methods that do both - perform a computation that also alters state, known as a "side-effect" either on itself or another object. In the heyday of imperative languages like C, Pascal, and BASIC, state was effectively a globally accessible thing. OOP "fixed" the scope, visibility and global state management issues by introducing classes, however, state remained associated with the class instance. A few years ago I wrote an article What's Wrong With Objects? and I would have to say at this point that the answer is much simpler: objects are an entanglement of:

state representation
computations (functions) affected by the object's state (and often additional parameter values passed in at the call)
state management
side-effects

What this means is that an object is a mutable, complicated entity that is hard to test and reuse. As a result, all sorts of additional technologies have arisen to support these complex little creatures - unit test engines, design patterns, code generators, ORM's, etc. Immutability (and the lack of side-effects) is something that FP'ers like to point out as being an advantage to FP. Immutability is a fundamental "think differently" principle of FP:

FP Thinking, #2: With FP, there are no side-effects because a state change is represented by a new instance. So, stop thinking in terms of changing state in an existing instance, and start thinking in terms of "this state change means I need a new instance."

Of course, you can write programs in F# that introduce side-effects, which introduces a corollary:

FP Thinking, #3: Even if the language supports mutability, this should be avoided at all cost (except when interfacing to a language like C/C++/C# that requires mutability to do anything useful) as mutability breaks many of the advantages of FP.

For example, the whole class could be poorly written in F#:

module FSTrafficLight

type LightStateEnum =
  | Red
  | Green
  | Yellow

type TrafficLight() as this = 
  let mutable myLightState = Red
  let mutable transitionTime = System.DateTime.Now
  do this.InitializeDuration

  member this.LightState 
    with get() = myLightState
    and set(value) = myLightState <- value

  member this.GetDuration =
    match this.LightState with
    | Red -> 10.0
    | Green -> 5.0
    | Yellow -> 1.0

  member this.NextState =
    match this.LightState with
    | Red -> Green
    | Green -> Yellow
    | Yellow -> Red

  member this.CheckState() =
    let now = System.DateTime.Now
    match now with
    | now when now >= transitionTime ->
      myLightState <- this.NextState
      this.InitializeDuration
      true
    | _ ->
      false

  member this.InitializeDuration =
    let durationAtState = this.GetDuration
    transitionTime <- System.DateTime.Now.AddSeconds(durationAtState)

But this is a poorly written F# class because of the mutable fields. Here's the test code in C#:

static void FSharpTrafficLight()
{
  FSTrafficLight.TrafficLight tl = new FSTrafficLight.TrafficLight();

  for (int i = 0; i < 20; i++)
  {
    tl.CheckState();
    Console.WriteLine((TrafficLight.State)tl.LightState.Tag);
    System.Threading.Thread.Sleep(1000);
  }
}

(As an aside, notice how the F# discriminated union LightStateEnum has a Tag property to get the enum value, which is mapped to a C# enum.)

Whenever you see a construct like this:

myLightState <- this.NextState

you are mutating the state of an existing instance. Stop and realize that this is breaking FP.

Immutability

How then would the above class be written in a more appropriate FP style? First, here's the code:

module FSBetterTrafficLight

type LightStateEnum =
  | Red
  | Green
  | Yellow

type TrafficLight(state, nextEventTime : System.DateTime) = 
  let myLightState = state
  let transitionTime = nextEventTime

  new() = 
    let initialState = LightStateEnum.Red
    let nextEventTime = TrafficLight.GetEventTime initialState
    TrafficLight(initialState, nextEventTime)

  member this.LightState 
    with get() = myLightState

  static member GetDuration state =
    match state with
    | Red -> 10.0
    | Green -> 5.0
    | Yellow -> 1.0

  static member NextState state =
    match state with
    | Red -> Green
    | Green -> Yellow
    | Yellow -> Red

  static member GetEventTime state =
    let now = System.DateTime.Now
    let duration = TrafficLight.GetDuration state
    now.AddSeconds(duration)

  member this.CheckState() =
    let now = System.DateTime.Now
    match now with
    | now when now >= transitionTime -> 
      let nextState = TrafficLight.NextState myLightState
      let nextEventTime = TrafficLight.GetEventTime nextState
      TrafficLight(nextState, nextEventTime)
    | _ -> this

and here's how we use it:

static void FSharpBetterTrafficLight()
{
  FSBetterTrafficLight.TrafficLight tl = new FSBetterTrafficLight.TrafficLight();

  for (int i = 0; i < 20; i++)
  {
    tl = tl.CheckState();
    Console.WriteLine((TrafficLight.State)tl.LightState.Tag);
    System.Threading.Thread.Sleep(1000);
  }
}

Notice this line in the C# code that calls our F# code:

tl = tl.CheckState();

Every time we call call CheckState, we are either assigning a new instance (when the state of the traffic light has changed) or are continuing to use the same instance (if the state does not change.) The astute reader will say "wait a minute, all you've done is push the mutability back onto the caller!" This is correct, but keep in mind that we calling the F# function from a language (C#) that is by nature mutable. Later we will see how to call the CheckState function from within F# (inherently immutable) without using any mutable fields.

Using Classes in F#: Constructors Initialize State

For the record, I am not a proponent of using classes in F#. They support working with the .NET framework and imperative languages, and so far, I haven't encountered anything I can do with classes that I can't do in F# without classes, using functions and features such as partial functions (more on this later.) If you think of a class (even an immutable class) in terms of typical OOD, you will immediately be thinking about inheritance and polymorphism.

FP Thinking #4: Stop thinking about objects. Stop thinking about inheritance and polymorphism. Separate out the fields that the class encapsulates into an FP representation. Separate out the methods that the class encapsulates into discrete static functions. Learn out how to use partial functions to leverage the concept of inheritance. Stop using polymorphism altogether by naming your functions better - polymorphism is actually nothing more than a band-aid for weak thinking.

In order to eliminate side-effects, the constructor of an immutable class in F# must fully initialize its fields. In fact:

FP Thinking #5: Learn how to think about structures (OO classes, FP records) as fully initialized and immutable entities. Figure out how to think in terms of fully initialized implementations. Learn to think purely in terms of initialization and computation. Replace "assignment" with "new instance."

If a field is mutable, it is "assignable", which violates our "no mutable fields" rule as we are changing the state of the current instance. In the above code, I provide a default constructor that will initialize the state of class fully by calling the parameterized constructor. The parameterized constructor simply initializes the fields to the values passed in by the parameters.

Using Classes in F#: Static Members

FP Thinking #6: Classes are a powerful concept in imperative code because they encapsulate mutability--encapsulation was primarily needed to manage instance state changes-- making mutability more manageable. Because FP eliminates mutability, we can return to a non-encapsulated, static method model, because FP functions merely perform a "computation", and there is no reason to encapsulate computations.

Notice that the following methods are static:

GetDuration
NextState
GetEventTime

Notice that these all take a state parameter. Here we have autonomous member methods that don't care about the state of the class, they are, well, autonomous! These become ridiculously simple yet powerful (because seriously, what can go wrong???) methods that are completely decoupled from the class instance and its state. One might argue that the power of a class is that you don't have to pass state parameters to the methods in the class. This is true, however, it also couples the methods to the class state, which then brings us back to the issue of side-effects (one of several issues). By passing everything to a function that it needs to perform its computation, you have instead an autonomous, easily testable function. The parameters of a function fully describe everything that that function requires to perform its computation - there is no guesswork as to what "internal", stateful, mutable, fields that function is also relying upon.

FP Thinking #7: An autonomous function is autonomous because its parameters describe everything it needs to perform its computation. Stop entangling your functions with a mix of parameters and stateful fields. Instead, create functions that have no dependency on anything other than what is being passed to them.

It takes a while to get used to, but the idea is simple: if you have a computation to perform, pass in all the information that the computation requires rather than relying on the state of fields in the class itself. Among other things, this means that your computations are truly re-usable: the class simply becomes a wrapper for the computation - you don't even need to instantiate the class because the computations are static methods. Yes, there are arguments that can be made against this, but remember a couple things:

Implementing classes in F# is a kludge that Microsoft supports because F# compiles down to IL and is compatible with other .NET languages and the .NET framework itself
Classes are really just stateful containers. You don't really need them in an immutable context, and in fact, they make usage, testing and concurrency much more difficult.

Using Classes in F#: Changing State

FP Thinking #8: Eliminate methods that change state by changing field values of the current instance. If you need to change the state of an object, it instead becomes a new instance representing that new state.

In the above code, the member method CheckState does not change the state of the class (it can't because nothing is mutable), instead it creates a new instance with the new state. The method either returns itself if it's not yet time to transition to another state, or it returns a new instance. You can see how this affects the code that calls the class - it now constantly re-assigns the instance as it loops through 20 iterations.

What Then, of Classes?

Using better FP practices in F#, we have achieved a few things that solve the problems mentioned earlier with classes:

We've eliminated side-effects - fields are immutable and the initial state of the class is fully described in the constructors
Computations don't even need to be in a class - the class becomes a container of convenience when we stop using fields and instead use parameters.
We no longer have methods that change the state of the class. Instead, we have methods that return new instances which represent the new state.

However, we can still do better, by entirely eliminating the class, which after all, is nothing more than a convenient container at this point. This is illustrated next.

What Then, Manages State?

FP Thinking #9: Manage your state with parameters and return values (stack-based state management) rather than heap-based management.

Rethinking how state is managed, and particularly, thinking about state as something that is stack-based rather than heap-based, is a fundamentally different way of thinking about programming. This is antithetical to much of the foundation of imperative programming - in early languages (BASIC, Pascal, Fortran, assembly, etc) fields were assigned to physical memory locations, either explicitly, as in early microprocessor programming, or implicitly by the compiler. In languages that support a memory pool (C, C++, etc), the concept of a "heap" came into being to support the dynamic creation and destruction of structures. As OO programmers, we are very entrenched in thinking about objects, which are heap-based. They float out there somewhere in memory, and in the days of C/C++, are easily stepped on and required explicit lifetime management. While .NET creates a safer, more secure, and implicit lifetime management environment (along with the potential pitfalls of automatic memory management and garbage collection), all it really is doing is hiding the problem. With FP, the problem goes entirely away when you start thinking in terms of stack-based state. Let's look at a classless (haha) implementation of the traffic light:

module ClasslessTrafficLight

type LightStateEnum =
  | Red
  | Green
  | Yellow

let GetDuration state =
  match state with
  | Red -> 10.0
  | Green -> 5.0
  | Yellow -> 1.0

let NextState state =
  match state with
  | Red -> Green
  | Green -> Yellow
  | Yellow -> Red

let GetEventTime state (now : System.DateTime) =
  let duration = GetDuration state
  now.AddSeconds(duration)

let CheckState(currentState, transitionTime) =
  let now = System.DateTime.Now
  match now with
  | now when now >= transitionTime -> 
    let nextState = NextState currentState
    let nextEventTime = GetEventTime nextState now
    (nextState, nextEventTime)
  | _ -> (currentState, transitionTime)

let InitialState = LightStateEnum.Red
let InitialEvent = (InitialState, GetEventTime InitialState System.DateTime.Now)

and its usage:

static void FSClasslessTrafficLight()
{
  var state = ClasslessTrafficLight.InitialEvent;

  for (int i = 0; i < 20; i++)
  {
    state = ClasslessTrafficLight.CheckState(state.Item1, state.Item2);
    Console.WriteLine((TrafficLight.State)state.Item1.Tag);
    System.Threading.Thread.Sleep(1000);
  }
}

OK, if you observe carefully, you will notice that I have cheated - I've eliminated the explicit class but I'm actually still managing the state in a class - in this case, a Tuple<>. If you inspect the type "state", which I've conveniently hidden as a "var", you will observe that is of the type:

Tuple<ClasslessTrafficLight.LightStateEnum, DateTime>

The important point here is not that I've merely replaced a specific class with a more general purpose container, but rather that I've completely decoupled the container managing the state (a Tuple in this case) from the computations that change the state. Furthermore, the state change is managed by a new Tuple rather than changing the values of fields in the Tuple. However, as with the earlier example, the caller (C#) is still managing the state in a mutable field. We still have to eliminate this, and we will, soon!

Inheritance as Partial Application / Currying

In the traffic light example, we can construct a simple class inheritance model in C# to construct two kinds of traffic lights - a 3 light version and a 2 light version:

public abstract class TrafficLightBase
{
  public enum State { Red, Green, Yellow };
  public State LightState { get; protected set; }
  protected DateTime transitionTime;

  public TrafficLightBase()
  {
    LightState = State.Red;
    InitializeDuration();
  }

  public abstract bool CheckState();
  protected abstract void InitializeDuration();
}

public class ThreeColorTrafficLight : TrafficLightBase
{
  public override bool CheckState()
  {
    bool lightChanged = false;

    if (DateTime.Now >= transitionTime)
    {
      switch (LightState)
      {
        case State.Red:
          LightState = State.Green;
          break;

        case State.Green:
          LightState = State.Yellow;
          break;

        case State.Yellow:
          LightState = State.Red;
          break;
      }

      InitializeDuration();
      lightChanged = true;
    }

    return lightChanged;
  }

  protected override void InitializeDuration()
  {
    int durationAtState = 0;

    switch (LightState)
    {
      case State.Red:
        durationAtState = 10;
        break;

      case State.Green:
        durationAtState = 5;
        break;

      case State.Yellow:
        durationAtState = 1;
        break;
    }

    transitionTime = DateTime.Now.AddSeconds(durationAtState);
  }
}

public class TwoColorTrafficLight : TrafficLightBase
{
  public override bool CheckState()
  {
    bool lightChanged = false;

    if (DateTime.Now >= transitionTime)
    {
      switch (LightState)
      {
        case State.Red:
          LightState = State.Green;
          break;

        case State.Green:
          LightState = State.Red;
          break;
      }

      InitializeDuration();
      lightChanged = true;
    }

    return lightChanged;
  }

  protected override void InitializeDuration()
  {
    int durationAtState = 0;

    switch (LightState)
    {
      case State.Red:
        durationAtState = 3;
        break;

      case State.Green:
        durationAtState = 3;
        break;
    }

    transitionTime = DateTime.Now.AddSeconds(durationAtState);
  }
}

In the C# code, we have two virtual methods for obtaining the next state and the state duration, depending on whether the traffic light has three colors (red, green, yellow) or just two colors (red and green.)

In the F# code, we first create some functions that are similar to our derived classes override methods:

Similar to TwoColorTrafficLight.InitializeDuration:

let GetDuration2Color state =
  match state with
  | Red -> 3.0
  | Green -> 3.0

Similar to ThreeColorTrafficLight.InitializeDuration:

let GetDuration3Color state =
  match state with
  | Red -> 10.0
  | Green -> 5.0
  | Yellow -> 1.0

Similar to TwoColorTrafficLight.CheckState:

let NextState2Color state =
  match state with
  | Red -> Green
  | Green -> Red

Similar to ThreeColorTrafficLight.CheckState:

let NextState3Color state =
  match state with
  | Red -> Green
  | Green -> Yellow
  | Yellow -> Red

Next, we modify the CheckState function to take two additional parameters, which are themselves functions. The idea is, we will pass in the appropriate function for determining the next state and the state duration, given the type of traffic light we want to simulate:

let CheckState fncNextState fncEventTime (currentState, transitionTime) =
  let now = System.DateTime.Now
  match now with
  | now when now >= transitionTime -> 
    let nextState = fncNextState currentState
    let nextEventTime = GetEventTime fncEventTime nextState now
    (nextState, nextEventTime)
  | _ -> (currentState, transitionTime)

Now, here comes the fun (pun intended) part. We create a couple partial functions that provide these two parameters (notice that they are the first two parameters of the CheckState function):

let CheckState2Color = CheckState NextState2Color GetDuration2Color
let CheckState3Color = CheckState NextState3Color GetDuration3Color

Instead of inheritance with virtual methods, we are taking advantage of a feature of FP called partial application. This concept (along with its cousins currying and closure) are discussed next, particularly with how we think about OO inheritance differently in FP.

Partial Application and Currying

It turns out that there's a lot of confusion regarding the terms "Partial Application" and "Currying". These concepts are fundamental to thinking in FP. For example, inheritance is a fundamental concept in OOP. One feature of inheritance is that it hides from programmer the concrete type that is implementing a behavior. This concrete type can be thought of as a "state instance" of an object graph. Depending on which subclass is instantiated, we can affect the behavior of the application. In FP, we can do the same thing but with partial application of functions and by passing functions as parameters. This requires a different way of thinking about inheritance.

FP Thinking #10: With inheritance, you are taking advantage of a system of virtual function pointers that is hidden from you by the compiler. With FP, you can easily pass functions as parameters and construct functions that are partial applications of other functions. This explicitly defines the usage the concrete function and is similar to instantiating the desired sub-class.

Basically, what you are doing with FP is explicitly implementing the concept of inheritance through the use of what in the OO world would be considered to be function pointers. This is similar to the Action<T, ...> and

Func<T, 
..., TResult>

classes in the .NET 4.5 library.

Partial Application

"[P]artial application ... refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.^"4 Arity is simply a fancy word for "the number of arguments or operands that the function takes."⁶ In the F# code, depending on the "state instance" that we want (a 2 color or 3 color traffic light), we create partial functions:

let CheckState2Color = CheckState NextState2Color GetDuration2Color
let CheckState3Color = CheckState NextState3Color GetDuration3Color

What this means is that CheckState2Color and CheckState3Color are providing the first two parameters, and all that the caller needs to do is provide the last parameter, which is the tuple (currentState, transitionTime).

Then, depending on the traffic light type that we want to "instantiate", we return the desired CheckState partial function, which is similar to a factory pattern that we're used in OOP:

let CheckTrafficLightState trafficLightType =
match trafficLightType with
| Color2 -> CheckState2Color
| Color3 -> CheckState3Color

We then provide the rest of the parameters in the ProcessTrafficLight function:

let ProcessTrafficLight(trafficLightType, currentState, transitionTime) = CheckTrafficLightState trafficLightType currentState transitionTime

In all my other examples, we have been calling the F# code from C#. An example of calling the above F# function from C# would look like this:

for (int i = 0; i < 20; i++)
{
  state = ClasslessTrafficLight.ProcessTrafficLight(trafficLightType, state.Item1, state.Item2);
  Console.WriteLine((TrafficLight.State)state.Item1.Tag);
  System.Threading.Thread.Sleep(1000);
}

This is not ideal, as the the CheckTrafficLightState function is called all the time. Instead, let's move the loop that is in the C# code into the F# code, and we can see a cleaner implementation:

let StartTrafficLight trafficLightType iterations =
  let checkLightState = CheckTrafficLightState trafficLightType
  let startingState = InitialEvent trafficLightType
  RunTrafficLight checkLightState startingState iterations

Here we have a simple function which first assigns the partial function CheckState2Color or CheckState3Color to checkLightState. We then call the function RunTrafficLight to run the traffic light for the number of specified iterations. We'll look at RunTrafficLight in a bit. But first, a word about currying.

Currying

"[C]urrying is the technique of transforming a function that takes multiple arguments (or an n-tuple of arguments) in such a way that it can be called as a chain of functions each with a single argument (partial application.)^"5

This is the correct definition of currying and you can see that currying is a special form of partial application in which the curried function takes only one parameter. In the partial application examples above, these qualify as curried functions because the curried function has only the tuple as the remaining parameter. There is a lot of confusion around currying, as evidenced by this statement: "When a function is curried, it returns another function whose signature contains the remaining arguments.^"3 This is not completely accurate. It is currying if and only if the returned function takes only one parameter. It is considered "partial application" if the return function takes more than one parameter.

Loops and Recursion

In the above code, I did not present the loop that runs the traffic light for the specified number of iterations. Here is the F# code:

let rec RunTrafficLight checkLightState currentState n =
  match n with
  | 0 -> ()
  | _ ->
    let nextState = checkLightState currentState
    printfn "%s" (ParseLightState (fst(nextState)))
    System.Threading.Thread.Sleep(1000)
    RunTrafficLight checkLightState nextState (n-1)

Here we finally see how the traffic light is run (in F#) without the use of a mutable field to handle the return of the checkLightState function. We are instead taking advantage of FP in two ways:

The "let" statement is an initialization, not an assignment. This is important because in FP, we want to be initializing entities rather than making assignments (which would require mutable types.)
By using a recursive function call, we are using the stack rather than a locally defined mutable field to manage the state changes.

FP Thinking #11: Recursion is the way you iteratively (confusing, isn't it?) work with state changes and the new instances of entities created by a state change. The salient point in thinking about recursion is to identify the entity (entities) whose state will change, and to pass those entities as parameters to the function, recursively. In this way, the state changes can be expressed as new instances passed to the function, rather than using mutable fields of the same instance.

While F# supports "for" loops, if we were to write the code imperatively in F#, it would end up looking like this:

let ForLoopTrafficLights trafficLightType iterations =
  let checkLightState = CheckTrafficLightState trafficLightType
  let mutable currentState = InitialEvent trafficLightType
  for i in 1..iterations do
    currentState <- checkLightState currentState
    printfn "%s" (ParseLightState (fst(currentState)))
    System.Threading.Thread.Sleep(1000)

Notice that this requires a mutable field to maintain the traffic light state. We want to eliminate mutable fields, so instead, we use a recursive call. By using a recursive call, nextState is parameterized and we use the stack (theoretically) as a means of managing changing state. Now, the important thing to realize is that the compiler will translate your recursive call into an iterative loop (there's lots of discussions about things like "tail recursion" that you can Google.) Observe the decompiled F# recursive code (using DotPeek), in C#:

public static void RunTrafficLight<a>(FSharpFunc<Tuple<ClasslessTrafficLight.LightStateEnum, a>, 
                                      Tuple<ClasslessTrafficLight.LightStateEnum, a>> checkLightState, 
                                      ClasslessTrafficLight.LightStateEnum currentState_0, 
                                      a currentState_1, 
                                      int n)
{
  while (true)
  {
    Tuple<ClasslessTrafficLight.LightStateEnum, a> func = new Tuple<ClasslessTrafficLight.LightStateEnum, a>(currentState_0, currentState_1);
    switch (n)
    {
      case 0:
        goto label_1;
      default:
        Tuple<ClasslessTrafficLight.LightStateEnum, a> tuple1 = checkLightState.Invoke(func);
        ExtraTopLevelOperators.PrintFormatLine<FSharpFunc<string, Unit>>((PrintfFormat<FSharpFunc<string, Unit>, TextWriter, Unit, Unit>) 
             new PrintfFormat<FSharpFunc<string, Unit>, TextWriter, Unit, Unit, string>("%s"))
             .Invoke(ClasslessTrafficLight.ParseLightState(Operators.Fst<ClasslessTrafficLight.LightStateEnum, a>(tuple1)));
        Thread.Sleep(1000);
        FSharpFunc<Tuple<ClasslessTrafficLight.LightStateEnum, a>, Tuple<ClasslessTrafficLight.LightStateEnum, a>> fsharpFunc = checkLightState;
        Tuple<ClasslessTrafficLight.LightStateEnum, a> tuple2 = tuple1;
        ClasslessTrafficLight.LightStateEnum lightStateEnum = tuple2.Item1;
        a a = tuple2.Item2;
        --n;
        currentState_1 = a;
        currentState_0 = lightStateEnum;
        checkLightState = fsharpFunc;
        continue;
    }
  }
  label_1:;
}

Note that the recursive call is implemented as an infinite loop which case 0 breaks out of. Also note how the parameters, which would normally be pushed onto the stack for each recursive call, are handled by the parameters currentState_0 and currentState_1. It is interesting to note that the IL code creates mutable variables, but then again, one would expect this as microprocessors have very imperative-based instruction sets, mutable registers, and of course work with mutable memory. We certainly do not want to implement a recursive call as true recursion in the IL or assembly language--imagine the amount of memory needed and the performance degradation of pushing values onto the stack if we were to recursively process a list of 10 million items!

Lists

Lists illustrate another way to think about iteration using recursion. One of the common examples one almost immediately encounters when learning about F# (or any FP language) deals with lists. Certainly, what I was left with was wondering, why would I want to work with lists recursively rather than iteratively? The answer to this is fairly straight forward:

FP Thinking #12: When working with lists, consider three things: the work item itself, which is usually the head of the list, the rest of the list, which is usually the tail, and the work that you want to do on the work item--the head. Teasing apart list processing into these three separate concepts brings clarity to the iterative work.

Consider how we might want to initialize a list of traffic lights in C#:

static List<TrafficLightBase> InitializeList()
{
  List<TrafficLightBase> lights = new List<TrafficLightBase>();

  for (int i = 0; i < 20; i++)
  {
    lights.Add(new ThreeColorTrafficLight());
  }

  return lights;
}

And how we iterate through the list:

static void IterateLights(List<TrafficLightBase> lights)
{
  foreach (TrafficLightBase tl in lights)
  {
    tl.CheckState();
  }
}

This looks very clean, from a imperative perspective, but from an FP perspective, the thinking needs to be different:

The list is itself being mutated every time the Add method is called
There is no clear separation of the work item (a traffic light instance) from the rest of the list (the collection of other traffic lights)
Because there is no separation, there is an implicit "do nothing" when all the work is done. This implicit behavior does not exist in FP - we explicitly state what should be done (even if it's nothing) when we're done with the work items.

Granted, except for the first issue (mutable lists), this reads like I'm trying to invent problems. Even mutable lists isn't really an issue as long as we're not manipulating the list in multiple threads. However, what I'm illustrating here is not that one way is better than the other but that, when you are working with lists in FP, you have to literally think differently.

Let's look at the above code implemented in F#. The first thing we change is that we're not instantiating a class - rather, we're creating a list of states, which is just one thing that a class provides us:

let rec InitializeTrafficLights trafficLightType iterations lights =
  match iterations with
  | 0 -> lights
  | _ -> InitializeTrafficLights trafficLightType (iterations-1) (InitialEvent trafficLightType :: lights)

This creates a list of "iterations" items using a recursive function call, and is typical of list operations, a match statement describes what is done when all the iterations are processed (the "0" case) as compared to when there are some iterations left (the "_", or "any", case). To call this function in C#, we would write:

var list = ClasslessTrafficLight.InitializeTrafficLights(
  ClasslessTrafficLight.TrafficLightType.Color2, 
  20, 
  FSharpList<Tuple<ClasslessTrafficLight.LightStateEnum, DateTime>>.Empty);

Notice that we need to pass in an empty list. Also note that the above F# code is only one option for initializing a list. Another option is (similar to the C# code):

let InitializeTrafficLights2 trafficLightType iterations = [for i in 1 .. iterations -> InitialEvent trafficLightType]

Both examples illustrate initializing an immutable list. In the first example, we recursively create a new list by prepending a "work item" to the original list. In the second F# example, we initialize the list with a "for" loop. Because the more common operation on lists involves working with the head and tail of the list, let's look at the generated code for the recursive function:

public static FSharpList<Tuple<ClasslessTrafficLight.LightStateEnum, DateTime>> InitializeTrafficLights(
     ClasslessTrafficLight.TrafficLightType trafficLightType, 
     int iterations, 
     FSharpList<Tuple<ClasslessTrafficLight.LightStateEnum, DateTime>> lights)
{
  while (true)
  {
    switch (iterations)
    {
      case 0:
        goto label_1;
      default:
        ClasslessTrafficLight.TrafficLightType trafficLightType1 = trafficLightType;
        int num = iterations - 1;
        lights = FSharpList<Tuple<ClasslessTrafficLight.LightStateEnum, DateTime>>.Cons(ClasslessTrafficLight.InitialEvent(trafficLightType), lights);
        iterations = num;
        trafficLightType = trafficLightType1;
        continue;
    }
  }
label_1:
  return lights;
}

We note a couple things about this method:

The recursion has been converted to iteration. This is a good thing, as it avoids true stack recursion.
The F# "::" operator is actually a call to the Cons method of the FSharpList

The Cons Method

F# lists are immutable linked lists. "The important thing to understand is that cons executes in constant, O(1), time. To join an element to an immutable linked list all you need to do is put that value in a list node and set its 'next list node' to be the first element in the existing list. Everything 'after' the new node is none the wiser."⁷ This "trick" ensures that the original list has not changed, we are simply creating a new list that consists of the new item node prepended (its "next node" points to the first item) to the existing list. If we were to append the item to an existing list, we would need to copy the original list and link the last node to the new item, requiring O(n) operations.

FP Thinking #13: When manipulating lists, you want to try to preserve (not mutate) the original list if possible. Think of a list as an entity in and of itself, rather than a collection of items. If you change the list entity, FP makes a copy of the list, and odd as it may sound, changing the "next node" entry of a list, even the last node of the list, is a change to the "entity" that is the list. This of course ensures that the original list is not mutated, which means that the original list is safe for other concurrent processes to continue to use, independent of what other processes are doing to the list.

Tail Recursion

Microsoft provides this example⁸ as a true recursive call:

let rec sum list =
  match list with
  | [] -> 0
  | head :: tail -> head + sum tail

and indeed, when we use DotPeek to inspect this code, we see that it is truly recursive:

public static int sum(FSharpList<int> list)
{
  FSharpList<int> fsharpList1 = list;
  if (fsharpList1.get_TailOrNull() == null)
    return 0;
  FSharpList<int> fsharpList2 = fsharpList1;
  FSharpList<int> tailOrNull = fsharpList2.get_TailOrNull();
  return fsharpList2.get_HeadOrDefault() + ClasslessTrafficLight.sum(tailOrNull);
}

To avoid this, we use a technique called "tail recursion" by employing an accumulator:

let rec sum2 list acc =
  match list with
  | [] -> acc
  | head :: tail -> sum2 tail (head + acc)

and we see that indeed, the recursion has now been converted to iteration in the IL:

public static int sum2(FSharpList<int> list, int acc)
{
  while (true)
  {
    FSharpList<int> fsharpList1 = list;
    if (fsharpList1.get_TailOrNull() != null)
    {
      FSharpList<int> fsharpList2 = fsharpList1;
      FSharpList<int> tailOrNull = fsharpList2.get_TailOrNull();
      int headOrDefault = fsharpList2.get_HeadOrDefault();
      FSharpList<int> fsharpList3 = tailOrNull;
      acc = headOrDefault + acc;
      list = fsharpList3;
    }
  else
    break;
  }
return acc;
}

Notice though, in the F# code, the parenthesis in the this line:

| head :: tail -> sum2 tail head + acc

The parenthesis around (head + tail) tells the compiler that we are defining a function that takes two parameters, adds them, and returns the sum, and it is this computed value that is passed as the second parameter to sum2. If we omit the parenthesis, we are back to a true recursive function!

public static int sum3(FSharpList<int> list, int acc)
{
  FSharpList<int> fsharpList1 = list;
  if (fsharpList1.get_TailOrNull() == null)
    return acc;
  FSharpList<int> fsharpList2 = fsharpList1;
  return ClasslessTrafficLight.sum3(fsharpList2.get_TailOrNull(), fsharpList2.get_HeadOrDefault()) + acc;
}

Why is this? Essentially, from the compiler's perspective, without the parenthesis, the call to sum3 is being made with the list's head item and, when sum3 returns, the accumulator value is added to the return value of sum3. Note how the parenthesis in the call are lined up:

return ClasslessTrafficLight.sum3(fsharpList2.get_TailOrNull(), fsharpList2.get_HeadOrDefault()) + acc;
                                 ^                                                             ^

and that "acc" is added to the return of sum3 rather than the sum being passed in to sum3. Therefore, it is not enough to say "we are using an accumulator", you must use the accumulator correctly!

FP Thinking #14: To ensure tail recursion you need to explicitly create a "function" as a parameter that performs the accumulating operation. If you forget this, the compiler will treat your code quite literally as a "call with the head value then perform the accumulator operation on the result." This flies in the face of what traditional "operator precedence" thinking would lead you to believe. Put another way, a function call will operate very strictly from left to right unless you explicitly state that an evaluation should occur, by using parenthesis around the evaluation.

Another way to look at this is illustrated by explicitly creating an Add function:

let Add a b = a + b

let rec sum4 list acc =
match list with
| [] -> acc
| head :: tail -> sum4 tail Add head acc

This code will not compile. It generates the error "Type mismatch. Expecting a 'a -> 'b -> 'c but given a 'c The resulting type would be infinite when unifying ''a' and ''b -> 'c -> 'a'". This is a very confusing error message, but we can basically reduce it to "sum4 tail Add" doesn't have the same signature as the definition. If we write the code like this:

let rec sum4 list acc =
  match list with
  | [] -> acc
  | head :: tail -> sum4 tail (Add head acc)

Explicitly saying that the result of the computation "Add head acc" is the second parameter, then everything works great.

Conversely, consider this code:

let rec Accumulate list f acc =
  match list with
  | [] -> acc
  | head :: tail -> Accumulate tail f (f head acc)

let Adder = Accumulate [1;2;3] Add 0

Here, we explicitly pass in the accumulator function (Add in this case) and we can see how the accumulator function is passed in as an argument to the Accumulate function and is itself used in tail recursion form to perform the accumulation operation.

List Iteration

Basic list iteration, without using all the complicated recursive functions described above, can be achieved rather simply using the "iter" method of the F# List class, but it's easy to do it the wrong way. First, let's look at this code, which doesn't compile:

let AddMe =
  let acc = 0
  List.iter(fun x -> acc <- acc + x) [1;2;3]
  acc

The astute reader will figure out that the reason it doesn't compile is that "acc" is not mutable. So let's fix that. This code, however, also does not compile:

let AddMe =
  let mutable acc = 0
  List.iter(fun x -> acc <- acc + x) [1;2;3]
  acc

The compiler gives us a very interesting error:

"The mutable variable 'acc' is used in an invalid way. Mutable variables cannot be captured by closures. Consider eliminating this use of mutation or using a heap-allocated mutable reference cell via 'ref' and '!'."

Well yes, we already know how to avoid mutation by using recursion. But what is this thing "closure"? According to Microsoft⁹:

"Closures are local functions that are generated by certain F# expressions, such as lambda expressions, sequence expressions, computation expressions, and curried functions that use partially applied arguments. The closures generated by these expressions are stored for later evaluation. This process is not compatible with mutable variables. Therefore, if you need mutable state in such an expression, you have to use reference cells."

which means that we have to write the code like this:

let AddMe =
  let acc = ref 0
  List.iter(fun x -> acc := !acc + x) [1;2;3]
  acc

and if we run this in F# Interactive, we get the desired result:

val AddMe : int ref = {contents = 6;}

FP Thinking #15: The List.iter method should not be used for accumulator operations. This is different from our thinking in C#, especially with regards to extension methods on lists which provide nice ways of iterating through a list and performing some sort of an accumulation operation. If you're not already familiar with LINQ in .NET OO languages like C#, you should become so now, because many of the operations in LINQ are similar to those provided in F# (and FP languages in general) that are more appropriate to use than simple list iteration.

What I mean by the above leading thought is, poke around and look at what is a better solution, and you will discover the List.fold method (in LINQ, it's the Aggregate method). For example, in C#, you can write this without any problem:

static int ListTest()
{
  int acc=0;
  new List<int>() { 1, 2, 3 }.ForEach(t => acc = acc + t);

  return acc;
}

But in FP, instead of doing this nasty iteration with references, we can instead write an elegant:

let AddMe2 = List.fold(fun acc i -> acc + i) 0 [1;2;3]

and in C#, it could be written as:

static int ListAggregate()
{
  return new List<int>() { 1, 2, 3 }.Aggregate((n, acc) => acc += n);
}

Of course, one would normally just use the Sum extension method.

Notice how the F# Iter.fold provides an accumulator for us! Here we have a nice function that takes the initial accumulator value (0 in our case) and the list, and iterates over the list, applying the function over each item and feeding the result of the function into the computation for the next time.

Type Inference

One of the nice things about FP is also something that will bite you: type inference. Consider this code, in which we define two record types:

type Rec1 =
{
  Count : int;
}

type Rec2 = 
{
  Count : int;
  Sum : int;
}

let Foo = {Count = 1}

This code generates the error "No assignment given for field 'Sum' of type 'ClasslessTrafficLight.Rec2'." Wait, are you telling me that the compiler is too stupid to figure out that, based on the fact that I'm only initializing Count, I want an instance of Rec1? Yes, that is exactly what I am telling you. And this can lead to some rather confusing and difficult to understand errors with functional programming. In fact, you can create code that will compile and run just fine but will give you the wrong type! Consider this code:

type Rec1 =
{
Count : int;
}

type Rec2 = 
{
Count : int;
}

let Foo = {Count = 1}

If we throw this into FSI (F# Interactive), we get:

val Foo : Rec2 = {Count = 1;}

Foo evaluates as a type Rec2! This may not be what we want, and we certainly do not get a compiler error indicating that Rec1 and Rec2 are exactly the same type! To resolve this, you would have to explicitly define Foo's type:

let Foo : Rec1 = {Count = 1}

or, give unique names to the record fields:

type Rec1 =
{
  CountA : int;
}

type Rec2 = 
{
  CountB : int;
}

let Rec1 = {CountA = 1}

FP Thinking #16: When defining record types, the type inference engine will use only the first field of the record to determine type. It will make your life a lot easier if you give fields unique names to help the type inference engine. This also makes the code more readable for a person, because they can easily figure out what record type is being initialized or used, even if it should be obvious.

What About all the Hoopla Around Functional Programming ?

A Better Glue?

John Hughes has written an excellent paper on Why Functional Programming Matters. In the introduction, he makes a very important statement:

"The special characteristics and advantages of functional programming are often summed up more or less as follows. Functional programs contain no assignment statements, so variables, once given a value, never change. More generally, functional programs contain no side-effects at all. A function call can have no effect other than to compute its result. This eliminates a major source of bugs, and also makes the order of execution irrelevant — since no side-effect can change an expression’s value, it can be evaluated at any time. This relieves the programmer of the burden of prescribing the flow of control. Since expressions can be evaluated at any time, one can freely replace variables by
their values and vice versa — that is, programs are “referentially transparent”. This freedom helps make functional programs more tractable mathematically than their conventional counterparts.

Such a catalogue of “advantages” is all very well, but one must not be surprised if outsiders don’t take it too seriously. It says a lot about what functional programming isn’t (it has no assignment, no side effects, no flow of control) but not much about what it is. The functional programmer sounds rather like a medieval monk, denying himself the pleasures of life in the hope that it will make him virtuous. To those more interested in material benefits, these “advantages” are totally unconvincing."

Obviously, because F# supports mutable variables, it contains assignment statements, so side-effects are just as easily accomplished with F# as they are with imperative / OO languages. Hence my strong recommendation that you should avoid mutable entities when programming in F#. Also, flow control is important, especially when dealing with user interactions. It actually becomes a problem in FP when you have an I/O stream that you want to present in a particular order. Realistically, "the burden of flow of control" is something that we have to deal with whenever the program interfaces with the outside world. However, we should also "loosen" our thinking with regards to control flow. For example, in a imperative language, we will typically get all the data into some sort of container and then hand off that container to a method that processes it. In FP thinking, we might pass to the processing function the function to load the data. However, this probably causes some other unintentional side-effects of the application itself: what if the data needs to be processed by two different algorithms? We certainly don't want to load the data twice - this may be very inefficient! Hence, and quite realistically, the author points out that "outsiders don't take [those advantages] too seriously."

The paper takes the position that instead of these usually touted benefits, the importance of functional programming is that it provides improved modularity and two completely new ways of gluing together programs that enhances modularity, and that this enhanced modularity is the main benefit of functional programming. These two types of glue can be described as:

Simple functions can be glued together to create more complex functions
Whole functional programs can themselves be glued together

I don't particularly buy into this reasoning very much, as it reminds me of the reasons touted for why object oriented programming is better: reusability. Except for general purpose operations, I don't find that classes in the an OO paradigm are particularly re-usable, and in my (albeit limited) experience with F#, most of the functions that I write solve very domain-specific problems and are not particularly re-usable either. Still, John Hughes' paper is worth reading.

Eliminates Patterns?

Slava Akhmechet, in his excellent blog entry Functional Programming For The Rest Of Us, writes:

"Most people I've met have read the Design Patterns book by the Gang of Four. Any self respecting programmer will tell you that the book is language agnostic and the patterns apply to software engineering in general, regardless of which language you use. This is a noble claim. Unfortunately it is far removed from the truth.

Functional languages are extremely expressive. In a functional language one does not need design patterns because the language is likely so high level, you end up programming in concepts that eliminate design patterns all together."

Eugene Wallingford, in his also excellent paper Functional Programming Patterns and Their Role in Instruction, writes:

"Functional programming is a powerful style for writing programs, yet many students never fully appreciate it. After programming in an imperative style, where state and state changes are central, the idioms of the functional style can feel uncomfortable. Further, many functional programming ideas involve abstractions beyond what other styles allow, and often students do not fully understand the reasons for using them. ...

Software patterns began as an industry phenomenon, an attempt to document bits of working knowledge that go beyond what developers learned in their academic study. They have become a standard educational device both in industry and in object-oriented (OO) design and programming instruction at universities. Given their utility in industry and in OO instruction, patterns offer a promising approach to help students and faculty learn to write functional programs. Such patterns will document the common techniques and program structures used by functional programmers, and pattern languages will document the process of using functional programming patterns in the construction of larger programs—ideally, complete programs that solve problems of real interest."

I would concur with this, and hopefully in this article have also illustrated that FP patterns do exist and that they are considerably different than OO patterns. There is some overlap (for example, using partial functions instead of inheritance in a factory method) and there are new patterns to be discovered in FP.

Another good read on FP patterns in Brian's Inside F#.

Easier to Unit Test?nn

Tomas Petricek writes here:

"...there are some aspects of functional programming that make testing of functional programs a lot easier.

Functional programs are composed from functions and guarantee that the function will behave the same in all contexts. This means that when you test a function in unit test, you know that it will always work this way. You don't have to test whether it works if you plug it into some other environment.
Functions take arguments and return results and that's the only thing they do. This means that you can usually avoid mocking and similar tricks, because you don't need to verify whether a function does some call on some object. You only need to verify that it returns the expected result for given arguments.
Finally, there are some nice automatic tools for testing functional programs. For F#, we have FsCheck (which is based on QuickCheck known from Haskell). These benefit from various properties of functional programs."

I would have to add that immutability significantly reduces the complexity of unit testing. Furthermore, by teasing apart a typical OO class into its constituents - state, computations, and state change methods - unit testing FP code is also considerably easier. And if unit testing is simplified, then the likelihood of bugs is also reduced, in my opinion.

Personal View

In my experience, programming in F#:

Results in smaller, simpler functions. They are easier to test and easier to understand what they do.
Immutable code eliminates side-effects, again improving testability and facilitating multi-threaded work, but there is a cost of additional code complexity to manage state changes
Partial application of functions is a powerful feature, reducing / eliminating the need for object inheritance
Separation of state, state management, and computation improves code quality
Passing functions as values is trivial - considerably easier than work with Action<> and Func<> generics.
The code is more concise, which is both good (more readable) and bad (often less readable unless you're a seasoned FP'er)
Type inference is great when it works, and it is annoying when it doesn't

Most of these "benefits" can be fairly easily accomplished in OO / imperative code as well. In fact, my experiences with FP have resulted in my being a better OO programmer, and my learning "FP thinking" has improved my software architecture abilities as well. Overall however, FP is, in my opinion, a very useful tool that solves certain architecture / programming problems better than OO paradigms, and other problems it does not do so well.

Summary

Functional programming requires a different way of thinking. What I have attempted to explore here are some fundamental concepts regarding core concepts of FP: immutability, recursion / iteration, and list operations, and how they require a fundamental different way of thinking in order to become a successful FP programmer. There's a lot more that can be said on this topic - I feel in many ways that I have just skimmed the surface. I have also probably made a number of errors that I hope experienced FP'ers will point out for the benefit of all!

Leading Thoughts In Functional Programming

FP Thinking, #1: In functional programming, we must embrace the idea and its implications that, once something is initialized, it cannot be changed.

FP Thinking #9: Manage your state with parameters and return values (stack-based state management) rather than heap-based management.

FP Thinking #12: When working with lists, consider three things: the work item itself, which is usually the head of the list, the rest of the list, which is usually the tail, and the work that you want to do on the work item--the head. Teasing apart list processing into these three separate concepts brings clarity to the iterative work.

FP Thinking #15: The List.iter method should not be used for accumulator operations. This is different from our thinking in C#, especially with regards to extension methods, which provide nice ways of iterating through a list and performing some sort of a accumulation operation. If you're not already familiar with LINQ, you should do so now, because many of the operations in LINQ are available in F# (and FP languages in general) that are more appropriate to use than simple list iteration.