You are previewing Programming F#.

Programming F#

Cover of Programming F# by Chris Smith Published by O'Reilly Media, Inc.
O'Reilly logo

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 ...

The best content for your career. Discover unlimited learning on demand for around $1/day.