Design Patterns in F#

Steve Goguen

Who am I?



Contact Info

…if thought corrupts language, language can also corrupt thought.
George Orwell

Does it really?

Read All Files From a Folder

Comparing Apples to Oranges

Functional F#

let ReadFolder = Directory.GetFiles >> Array.map File.ReadAllText

Imperative C#

string[] ReadFolder(string path) {
  var filenames = Directory.GetFiles(path);
  var results = new string[filenames.Length];
  for(var i = 0; i < results.Length; i++) {
    var filename = filenames[i];
    var text = File.ReadAllText(filename);
    results[i] = text;
  }
  return results;
}

Could ceremony and painstaking attention to the details corrupt your thinking and distract you from solving your problem?

Read All Files From a Folder

A Better Comparison

Functional C#

string[] ReadFolder(string path) {
  return Directory.GetFiles(path).Select(f => File.ReadAllText(f)).ToArray();
}

Functional F#

let ReadFolder = Directory.GetFiles >> Array.map File.ReadAllText

Read All Files From a Folder

A Better Comparison

Functional C# with LINQ

string[] ReadFolder(string path) {
  return (from f in Directory.GetFiles(path)
          select File.ReadAllText(f)).ToArray();
}

Functional F#

let ReadFolder = Directory.GetFiles >> Array.map File.ReadAllText

The F# Version - Looking under the hood

Let's Talk About Patterns and Names



...but first, which square is a different color?

One is clearly dumbu and the others are borou.


Don't feel too bad, this test stumps the Himba people.

Do names define rigid mental boundaries?

One Theory

Let's train our brains to distort our vision


Hierarchical Temporal Memory


Design Patterns and Names

Design Patterns

  • A general reusable solution to a commonly occurring problem
  • A recipe - not a finished design that can be transformed directly into code
  • Description or template for how to solve a problem that can be used in many different situations

Peter Norvig noted that many of the 23 design patterns were significantly simplified or eliminated with higher level languages.

Do these names distort our perspective?

  • Factory Method
  • Interpreter
  • Adaptor
  • Singleton
  • Lazy Initialization
  • Prototype
  • Abstract Factory
  • Multiton
  • Decorator
  • Builder
  • Composite
  • Façade
  • Chain of Responsibility
  • Command
  • Front Controller
  • Flyweight
  • Proxy
  • Blackboard
  • Iterator
  • Mediator
  • Memento
  • Null Object
  • Observer
  • Servant
  • Specification
  • State
  • Strategy
  • Template Method
  • Visitor

Do the names alone sufficiently describe them?

The Factory Pattern

In class-based programming, the factory method pattern is a creational pattern which uses factory methods to deal with the problem of creating objects without specifying the exact class of object that will be created. This is done by creating objects via calling a factory method—either specified in an interface and implemented by child classes, or implemented in a base class and optionally overridden by derived classes—rather than by calling a constructor.

Note the language used to describe the pattern.

The Factory Pattern - How about a UML Diagram?

The Factory Pattern - An Example

Define an interface for creating an object, but let the subclasses decide which class to instantiate. The Factory method lets a class defer instantiation to subclasses.

Step 1: Define our interfaces

interface IEmployee {
  string Name { get; }
  decimal GetCheckAmount();
}
interface IEmployeeFactory {
  IEmployee Create(string name, string position);
}

The Factory Pattern - Step 2: Implement IEmployee

public class SalariedEmployee : IEmployee {
  //  Our private fields to store our values
  private string name;
  private decimal yearlySalary;
  
  // Constructor
  internal SalariedEmployee (string name, decimal yearlySalary) {
    this.name = name;
    this.yearlySalary = yearlySalary;
  }
  // Readonly Name property
  string IEmployee.Name {
    get { return name; }
  }
  // Function to calculate a check amount
  decimal IEmployee.GetCheckAmount() {
    return yearlySalary / 52;
  }
}

The Factory Pattern - Step 3: Implement a Factory

Create a class implementing IEmployeeFactory

public class SalariedEmployeeFactory : IEmployeeFactory {
  public IEmployee Create(string name, string position) {
    if(position == "boss")
      return new SalariedEmployee(name, 300000);
    return new SalariedEmployee(name, 40000);
  }
}

Step 4: Try out our new factory

public class FactoryExamples {
  public void Example1() {
    IEmployeeFactory f = new SalariedEmployeeFactory();
    IEmployee[] Employees = new IEmployee[] {
      f.Create("Larry", "stooge"),
      f.Create("Curly", "stooge"),
      f.Create("Moe", "boss")
    };
  }
}

All that code just to create some lousy objects??? Really???

Factories in F#

Step 1: Define the Employee interface (The factory will just be a function)

type IEmployee =
  abstract member Name: string
  abstract member GetCheckAmount: unit -> decimal

Step 2: Create a function returning an object implementing IEmployee

let createSalaryEmployee(name,position) = 
  let yearlySalary = if position = "boss" then 300000.0m else 40000.0m
  { new IEmployee with
    member this.Name = name
    member this.GetCheckAmount() = yearlySalary / 52.0m }

Step 3: Try out our constructor

//  Let's try this out
let employee = createSalaryEmployee
let employees = [
  employee("Larry", "stooge") 
  employee("Curly", "stooge")
  employee("Moe", "boss")
]

Takeaways

More Pattern Recipes

The Singleton Pattern

C# Version

class A {
  public private A() {}
  private static A instance = new A();
  public static A Instance() {
    return 
  }
  public void Action() {
    Console.Write("action");
  }
}

Tao Liu's Version

type A private () =
    static let instance = A()
    static member Instance = instance
    member this.Action() = printfn "action"
let DesignPattern1() = 
    let a = A.Instance;
    a.Action()
;

The Functional Singleton

F# C#
let makeSingleton f =
  let instance = lazy f()
  fun () -> instance.Value
Func<A> makeSingleton<A>(Func<A> f) {
  var instance = f();
  return () => instance;
}
  • Singletons are just functions that return the same instance
  • Using first class functions, closures and higher ordered types there's no need to repeat this pattern throughout your code.

The Decorator Pattern

Attach additional responsibilities to an object dynamically keeping the same interface. Decorators provide a flexible alternative to subclassing for extending functionality.

public interface Coffee {
    public double getCost();
    public String getIngredients();
}
public class SimpleCoffee : Coffee {
    public double getCost() { return 1; }
    public String getIngredients() { return "Coffee"; }
}
public class Milk : Coffee {
    private Coffee decoratedCoffee;
    public Milk(Coffee decoratedCoffee) {
        this.decoratedCoffee = decoratedCoffee;
    } 
    public double getCost() { // overriding methods defined in the abstract superclass
        return decoratedCoffee.getCost() + 0.5;
    }
    public String getIngredients() {
        return decoratedCoffee.getIngredients() + ingredientSeparator + "Milk";
    }
}

The Decorator Pattern - In F#

Take Aways

The Builder Pattern - In C#

Separate the construction of a complex object from its representation allowing the same construction process to create various representations.

class CoffeeBuilder {
  protected Coffee coffee;
  public Coffee getCoffee() {
      return coffee;
  }
 
  public void createNewCoffeeProduct() {
    coffee = new SimpleCoffee();
  }
 
  public void addMilk() {
    coffee = new Milk(coffee);
  }
}
// Usage
var builder = new CoffeeBuilder();
builder.createNewCoffeeProduct();
builder.addMilk();
var myCoffee = builder.getCoffee();

The Builder Pattern - In C# Using Fluent Interface

class CoffeeBuilder {
  protected Coffee coffee;
  public Coffee getCoffee() {
      return coffee;
  }
 
  public CoffeeBuilder createNewCoffeeProduct() {
    coffee = new SimpleCoffee();
    return this;
  }
 
  public CoffeeBuilder addMilk() {
    coffee = new Milk(coffee);
    return this;
  }
}
// Usage
var myCoffee = new CoffeeBuilder()
  .createNewCoffeeProduct().addMilk().getCoffee();

The Builder Pattern - In F# Using Fluent Interfaces

Define our fluent builder

type CoffeeBuilder(coffee:Coffee) = 
  new() = CoffeeBuilder(SimpleCoffee)
  member this.addMilk() = CoffeeBuilder(Milk(coffee))
  member this.getCoffee() = coffee

Use it

let builder = new CoffeeBuilder()
let myCoffee = builder.addMilk().getCoffee()

The Builder Pattern - In F#

Why create a fluent interface when you can just pipe constructors?

let myCoffee = SimpleCoffee |> Milk

Do F# Sequences use the Builder Pattern?

let myFunctions =
  let path = @"C:\Project"
  Directory.EnumerateFiles(path, "*.vb", SearchOption.AllDirectories)
  |> Seq.map File.ReadAllText
  |> Seq.collect (fun text -> Regex.Matches(text, "Function \w+\([^)]*\)") |> Seq.cast
 )
  |> Seq.map (fun m -> m.Value)
  |> Seq.take 10  

Composites

Patterns Implemented Elegantly with Object Expressions

Pattern Name Correlating Type?
Singleton - Ensure a class has only one instance, and provide a global point of access to it. () -> 'a
Lazy Initialization - Delay creating an until the first time it's needed () -> 'a
Multiton - Ensure a class has only named instances, and provide global point of access to them string -> 'a
Factory Method 'a -> 'b
Adaptor - Convert the interface of a class into another interface clients expect. 'a -> 'b
Decorator - Attach additional responsibilities to an object dynamically keeping the same interface. 'b -> 'a -> 'a
Prototype - Specify the kinds of objects to create using a prototypical instance, and create new objects by copying this prototype 'a -> () -> 'a
Composite - Treat a list of objects as a single object ('a list -> 'a)

Average Developers Implement Patterns Poorly

How about new names for design patterns around type signatures?

Action() → ()
Source() → a
Sinksa → ()
Functiona → b
Predicatea → bool
Pickera → Option<b>
Liftera → M<a>
Combinera → b → c
Foldera → b → a

Names are a Double Edge Sword

Patterns Implemented Elegantly with Union Types and Pattern Matching

Patterns Implemented Elegantly with Union Types and Pattern Matching

PatternDescription
Visitor Pattern Represent an operation to be performed on the elements of an object structure.
Interpreter Pattern Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.
Specification Pattern Recombinable business logic in a Boolean fashion

Defining and Visiting a Simple AST

The Visitor Pattern

We require two interfaces. The first forces us to implement visit methods for all node types. The second so each node can accept a visitor.

interface IExprVisitor {
    void visit(AddExpr addExpr);
    void visit(ValueExpr valueExpr);
}

interface IExpr {
  	void accept(IExprVisitor visitor);
}

Implementing an Accepting Node

class AddExpr : IExpr {
  public IExpr left;
  public IExpr right;
  public AddExpr(IExpr left, IExpr right) {
    this.left = left;
    this.right = right;
  }
  public void accept(IExprVisitor visitor) {
    visitor.visit(this);
  }
}

Now Let's Create a Printing Visitor

class PrintingVisitor : IExprVisitor {
  StringBuilder sb = new StringBuilder();
  public void visit(AddExpr addExpr) {
    sb.Append("(");
    addExpr.left.accept(this);
    sb.Append(" + ");
    addExpr.right.accept(this);
    sb.Append(")");
  }
  public void visit(ValueExpr valueExpr) {
    sb.Append(valueExpr.value);
  }
  public string ToString() {
    return sb.ToString();
  }
}

...and finally a simple Print function

string Print(IExpr expr) {
  var printer = new PrintingVisitor();
  expr.accept(printer);
  return printer.ToString();
}

Shall We Implement an Interpreter Too?

How about a universal language?

An Untyped Language that's a Closed System

You can apply any function to any other function - It just might not ever stop

I or IDλa.a
Kλa.λb.a
Sλa.λb.λc.a c (b c)
TRUEλa.λb.a
FALSEλa.λb.b
0λa.λb.b
1λa.λb.a b
2λa.λb.a (a b)
POWλa.λb.b a
ANDλa.λb.a b a
ORλa.λb.a a b

A good closed system can be universally powerful and insightful

Symbolically Evaluating Pure Lambda Calculus

IDλx.x
TRUEλx.λy.x
FALSEλx.λy.y
ANDλp.λq.p q p

Let's partially evaluate And(True)

1. (λp.λq.p q p)(λx.λy.x)
2. (λp.λq.(λx.λy.x) q (λx.λy.x))
3. (λq.(λx.λy.q) (λx.λy.x))
4. (λq.q)

Converting F# to Pure Lambda Calculus

Working Towards an Evaluator

We need to be able to substitute variables with expressions

let rec substitute (varName:var) (withExpr:term) (expr:term) =
    let doSubRec = substitute varName withExpr 
    match expr with
    | Var(name) when varName = name -> withExpr
    | App(left, right) -> App(doSubRec left, doSubRec right)
    | Lambda(var, body) when var <> varName -> 
        Lambda(var, doSubRec body)
    | x -> x

Let's start by with evaluating a single step before we tackle the larger problem

let rec evalStep expr = 
  match expr with
  | App(Lambda(var, expr), right) -> substitute var right expr
  | App(left, right) -> App(evalStep left, evalStep right)
  | Lambda(var, body) -> Lambda(var, evalStep body)
  | x -> x

Evaluating Multiple Steps

Let's evaluate multiple steps
let rec eval (maxSteps:int) (term:term) =
  seq {
    yield term
    let last = ref term
    let next = ref (evalStep term)
    while next.Value <> last.Value do
      yield next.Value
      last := next.Value
      next := evalStep next.Value
  } |> Seq.truncate maxSteps |> Seq.toList
A utility to print
let printEval max term =
  let steps = term |> eval max
  for step in steps do
    printfn "%s" (ToString step)
  let last = steps |> List.rev |> List.head
  last

Where to Start

Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowchart; it'll be obvious.
Fred Brooks
Bad programmers worry about the code. Good programmers worry about data structures and their relationships.
Linus Torvalds
Smart data structures and dumb code works a lot better than the other way around
Eric Raymond

A Problem Solving Progression

  1. Start by solving your program as well defined data type
  2. Then try solving it with simple transformations
  3. Then try a conventional workflow
  4. If a conventional workflow becomes too complicated...

Note: F# typically forces your code to read in this order

Computation Expressions

What Builders are Made of...

Computation Expression Building Blocks

Zero() → M a
Returna → M a
Yielda → M a
ReturnFromM a → M a
YieldFromM a → M a
Delay() → M a → M a
CombineM a → M a → M a
BindM a → (a → M b) → M b
Forseq a → (a → M b) → M b
Forseq a → (a → M b) → seq M b
While(() → bool) * (M a → M a)

Counting Types

'a A value
() -> 'a Function - no args returning a value
() -> IO<'a> Function returning some input
'a -> 'a A pure function returning its own type
'a -> 'b A regular function
'a * 'b Tuples
'a + 'b Discriminated Unions

This assumes we're talking about pure functions


How can we account for side-effects in types?

Before We Finish Up

Design Patterns are Important

Contact Info

A link to my presentation is on my github page.