O'Reilly logo

Programming F# by Chris Smith

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Functional Patterns

Now that we have covered some advanced concepts in the functional style of programming, let’s examine some common design patterns they enable. Describing solutions to problems in terms of design patterns makes it easier to explain and reuse such solutions.

Memoization

When you write in the functional style, most of the functions you write will be pure, meaning that for the same input they will always produce the same output. However, if you call the same pure function many times, it can be a waste of resources to recompute known values. Instead, it would be more efficient to store those values in a Dictionary<_,_> type that maps input values to function results.

The process of storing known input/result pairs of a function is known as memoization, and can be done automatically by taking advantage of higher-order functions and closures in F#.

Example 7-23 defines a memoize function, which takes a function as a parameter and returns a memoized version of that function as its result. The memoized version stores a dictionary of previous results in its closure, and calls the provided function only when necessary.

Example 7-23. Memoizing pure functions

open System.Collections.Generic

let memoize (f : 'a -> 'b) = let dict = new Dictionary<'a, 'b>() let memoizedFunc (input : 'a) = match dict.TryGetValue(input) with | true, x -> x | false, _ -> // Evaluate and add to lookup table let answer = f input dict.Add(input, answer) answer // Return our memoized version of f dict is ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required