count_change.fs

open System
open System.Diagnostics

let inline (|LessThan|_|) n = function
    | x when x < n -> Some()
    | _ -> None

let rec cc amount coins =
    match amount, coins with
    | 0, _ -> 1
    | _, [] | LessThan 0, _ -> 0
    | _, c::cs -> cc amount cs + cc (amount - c) coins

[<EntryPoint>]
let main argv =
    let stopWatch = Stopwatch.StartNew()

    let x = cc 100 [1;2;3;4;5;6;7]

    printfn "Result: %i elapsed: %g ms" x stopWatch.Elapsed.TotalMilliseconds
    Console.ReadLine() |> ignore
    0

A tail recursive version that would work with very long lists (but take a lifetime) seems to be 5 times slower. Clearly unnecessary but worth having a look at.

let cc =
    let rec cc kont amount coins =
        match amount, coins with
        | 0, _ -> kont 1
        | _, [] | LessThan 0, _ -> kont 0
        | _, c::cs -> cc (fun v -> cc ((+) v >> kont) (amount - c) coins) amount cs

    cc id