Navigate / search

Curried vs Uncurried Functions

Over a year ago I explained Memoization in this post. If you’ve read that, you should be comfortable with the following.

open System.Collections.Generic

let negate x =
    printfn "Negating..."
    -x

let cache f =
    let cache = Dictionary<_, _>()

    fun x ->
        if cache.ContainsKey(x) then
            cache.[x]
        else
            let result = f x
            cache.[x] <- result
            result

let fastNegate = cache negate

We’re pretending that ‘negate’ is an expensive function that we want to avoid calling unnecessarily, so we use the ‘cache’ function to wrap ‘negate’ with some caching behaviour. Negate takes one argument. What happens when we try to cache a function that takes more than one argument, like ‘add x y’?

On first glance it appears to work.

let add x y = 
    printfn "Adding two args"
    x + y

let fastAdd = cache add

val add : x:int -> y:int -> int
val fastAdd : (int -> int -> int)

But if you try to use it the results are, disappointing.

> fastAdd 1 5;;
Adding two args
val it : int = 6

> fastAdd 1 5;;
Adding two args
val it : int = 6

The underlying ‘add’ function is called every time. We can check to see if anything is added to our cache with a ‘printfn’.

let cache f =
    let cache = Dictionary<_, _>()

    fun x ->
        if cache.ContainsKey(x) then
            cache.[x]
        else
            let result = f x
            cache.[x] <- result
            printfn "Added Item to cache, Items now in Cache: %d" cache.Count
            result

> fastAdd 1 2;;
Added Item to cache, Items now in Cache: 1
Adding two args
val it : int = 3

> fastAdd 1 2;;
Adding two args
val it : int = 3

> fastAdd 2 1;;
Added Item to cache, Items now in Cache: 2
Adding two args
val it : int = 3

That’s odd. The first time we call the function, something is added to the cache. The second time, using the same values, nothing is added to the cache. When we try different arguments another item is added to the cache. This suggests the cache is being used.

Remember that functions in FSharp are curried, which means that a function which takes two arguments (like add) is translated (curried) into a series of functions which each take a single argument.

So, when we try to cache

add x y

what we actually cache is the partially applied function

add x

We can test this. As long as we keep the same value for x, the fastAdd function will use the cached version. As soon as we change x, we get a new partially applied function that is different to the one in the cache. We can see this in the example above. It is the change in x from 1 to 2 that triggered the addition of a new item to the cache.

So, we’re not actually caching our *expensive* add function at all. We’re just caching the partial application of it.

We could rewrite our ‘add’ function so that it takes one argument, a tuple.

let add (x, y) =
    x + y

let fastAdd = cache add

> fastAdd (1, 2);;
Added Item to cache, Items now in Cache: 1
val it : int = 3

> fastAdd (1, 2);;
val it : int = 3

> fastAdd (1, 3);;
Added Item to cache, Items now in Cache: 2
val it : int = 4

We’ve ‘uncurried’ the function. Now everything works. But it’s still no good. We’ve duplicated our add function, and remember this all relates to functions that are a lot more complicated than addition.

We could wrap the original curried function so the logic isn’t duplicated. We’re really just putting an adapter around it to change it’s signature.

let add x y = 
    printfn "Adding two args"
    x + y

let uncurriedAdd (x, y) =
    add x y 

let fastAdd = cache uncurriedAdd

val add : x:int -> y:int -> int
val uncurriedAdd : x:int * y:int -> int
val fastAdd : (int * int -> int)

> fastAdd (1, 3);;
Adding two args
Added Item to cache, Items now in Cache: 1
val it : int = 4

> fastAdd (1, 3);;
val it : int = 4

That’s still rubbish though. The signature of ‘fastAdd’ is different to ‘add’, so it isn’t an alternative. If we think in terms of higher order functions, ‘add’ and ‘fastAdd’ have different types. We can’t pass ‘fastAdd’ to a function that is expecting ‘add’ and expect things to just work.

We could write a ‘cache2’ function that follows the same pattern as ‘cache’ but works with functions of two arguments. That will work but it’s a shame not to use the working cache function that we already have.

Feel free to stop reading and figure out a solution. What follows is one way of doing it.

The solutions above weren’t good enough, but we were on the right track. Uncurrying the ‘add’ function to make it compatible with our cache is fine, although we shouldn’t have to write a specific function each time we need to uncurry a function. Through the magic of higher order functions we can write the following.

let uncurryTwoToOne f (x, y) = f x y

That allows us to write the following.

let uncurriedAdd = uncurryTwoToOne add

That saves us doing the uncurrying individually for each function. It still leaves us with a function that isn’t compatible with the original signature of Add. So, caching it is still no good. Remember the ‘cache’ function doesn’t change the signature, it takes a function that accepts one argument and it wraps it to add caching, but it maintains the same signature. That way, the cached version can be used anywhere the original is used.

It looks like we need to wrap the cached version of ‘add’ in yet another function to convert the signature back to curried form. Another higher order function to the rescue.

let curryOneToTwo f x y = f (x, y)

And now we finally have a working solution.

let fastAdd = add |> uncurryTwoToOne |> cache |> curryOneToTwo

> fastAdd 1 3;;
Adding two args
Added Item to cache, Items now in Cache: 1
val it : int = 4

> fastAdd 1 3;;
val it : int = 4

Note that in the ‘fastAdd’ function we are not piping the result of ‘add’ through the chain of functions, the actual ‘add’ function itself is the value. Each function in the chain is passed a function which it wraps before passing it on. Like building up the layers of an onion.

It seems like we should be able to make ‘fastAdd’ into a general purpose higher order function too.

let curried2 f = f |> uncurryTwoToOne |> cache |> curryOneToTwo

Putting it all together. We get the following

open System.Collections.Generic

let uncurryTwoToOne f (x, y) = f x y

let curryOneToTwo f x y = f (x, y)

let cache f =
    let cache = Dictionary<_, _>()

    fun x ->
        if cache.ContainsKey(x) then
            cache.[x]
        else
            let result = f x
            cache.[x] <- result
            printfn "Added Item to cache, Items now in Cache: %d" cache.Count |> ignore
            result

let cache2 f = f |> uncurryTwoToOne |> cache |> curryOneToTwo

let add x y = 
    printfn "Adding two args"
    x + y

let fastAdd = cache2 add

> fastAdd 1 3;;
Adding two args
Added Item to cache, Items now in Cache: 1
val it : int = 4

> fastAdd 1 3;;
val it : int = 4

> fastAdd 1 4;;
Adding two args
Added Item to cache, Items now in Cache: 2
val it : int = 5

> fastAdd 1 4;;
val it : int = 5

Leave a comment

name*

email* (not published)

website