Haskell Flavoured Curry

curry

Reading time: 10 minutes
Currying is a very useful pattern in functional programming. It is a way of breaking up a function which takes multiple parameters in to a chain of outer to inner functions, each of which, takes one parameter. It allows arguments which are known at one point in program execution to be captured and used in a later execution of a function requiring more arguments. In some ways, it’s similar to when an Object is instantiated in OO with one or more property values which are used in later function executions involving that object.

I have found that the subject of currying can be confusing for developers who are new to functional programming. It was for me at the start anyway. I used to try and relate everything back to OO but I discovered that using a substitution model approach based on the Lambda Calculus really simplified things. I won’t go into the specifics of Lambda Calculus here but I’ll give a short example of using a substitution approach in the context of understanding currying.

So, we have a function which transforms a String by prepending a certain number, n, of characters to the start of it returning a new String.

So, in pseudocode this could look like:

prepend(n, c, s) = put n c's at the start of s

Now lets execute this function:

prepend(3, 'z', "Tom")

This would result in

"zzzTom"

This function is completely pure in that it has no observable interaction with its outside context. This is extremely useful because it means that anywhere we see this function called in a program, we can substitute the call arguments into the function’s implementation without changing the meaning of our program. Functional programmers love to say “functional programming is easier to reason about” and this isn’t just a catchphrase. It is this ability to substitute arguments for parameters in expressions, along with all the other functional programming goodness like immutability, that does actually make functional programming easier to reason about.

So, using a simple substitution model, when we call

prepend(3, 'z', "Tom")

in our program, we can replace it with its implementation expression by substituting into it the arguments 3, ‘z’ and “Tom” for the parameters n, c and s respectively.

so

prepend(3, 'z', "Tom")

becomes

put 3 'z' 's at the start of "Tom"

For a curried version of this function we can break it up into three one parameter functions: (I’m using

->

here to separate a function name with its parameter and the function’s expression body – again this is pseudocode)

prependA(n) -> prependB(c) -> prependC(s) -> put n c's at the start of s

Okay, hold a while here! I know this looks kind of weird as we have three functions, starting with the outer prependA function and returning an inner function until we reach the innermost expression. This is where, before, I would have gained initial understanding by thinking about each outer closure returning its inner closure working from the outmost function, prependA to the innermost, prependC – outer to inner functions/closures is the subject of one of my earlier blogs: Closures For OO Developers – 1.
I find that trying to think in this way can start to bend the brain a little bit as higher order functions become more complex. If we look at how this works using the substitution model, things become way easier!

Okay, so lets say we know how many characters we want to prepend to a String but we don’t know what the character is or what the String is just yet. That’s okay!
We can still call our function

prependA(n)

.
So, if n is 3, we call,

prependA(3)

and substituting we 3 for n in its implementation expression, we get

prependB(c) -> prependC(s) -> put 3 c's at the start of s

Okay now, we have a function which can take, as a parameter, the character that we are prepending. At some point, we know that the character we want to prepend is ‘z’, so we call

prependB('z')

substituting z for c in its implementation expression, we get

prependC(s) = put 3 'z' 's at the start of s

Now we have a function which can take a String, s, and prepend three ‘z’ characters to the front of it to produce a new String.

At some point, we find out that the String we want to transform is “Tom” so we call:

prependC("Tom")

Now, we substitute again and this becomes:

put 3 'z' 's at the start of "Tom"

which is back to what we had when we called the original prepend(3, ‘z’, “Tom”)

Haskell likes its Curry

In the above example, I have actually shown, in a simplified way, how the function substitution would work in the Lambda Calculus.
With Haskell being an implementation of the Lambda Calculus, all functions are curried. This doesn’t mean that all functions have to be written as one parameter functions. When a function is declared with multiple parameters, Haskell breaks this up into a series of outer to inner one parameter curried functions underneath the hood. So, our prepend function from above could be declared in Haskell in a way that doesn’t look like its curried.

prepend :: Int -> Char -> String -> String 
prepend n c s = take n (repeat c) ++ s

The expression in the implementation of the prepend function above just says:
take the character, c repeated n times and stick it onto the String s to form a new String (without mutating the original String s).
The type signature is

prepend :: Int -> Char -> String -> String 

Type signatures in Haskell show the curried nature of functions with a series of types separated by

->

with the last being the return type of the function.

The prepend function above takes three parameters, n, c, and s just like the prepend function in our earlier pseudocode. However, just like how I broke this up into a series of outer to inner one parameter functions in the pseudocode, Haskell does this automatically for us.

This allows us to do some really handy stuff!

So, say we want a function to pad a String with a number of characters to the left of the String but we know that we will always want 10 characters. We can declare this as our pad10 function below.

pad10 :: Char -> String -> String 
pad10 = prepend 10

In the above code, we have simply assigned pad10 to prepend but we are only calling the prepend function with one argument, 10. Because the pretend function is automatically curried, when we call pretend 10, we get back another function which takes a character, c which in turn, when called with a character argument, will return the innermost expression which is the expression that actually does the String prepending.

We can continue with this pattern.

So, say we always want to pad a String to the left with 10 white space characters.

pad10WhiteSpaces :: String -> String 
pad10WhiteSpaces = pad10 ' '

In the Haskell code above, we again take advantage of Haskell’s automatic currying and call pad10 with 1 argument, the

' '

character. We can follow a similar substitution to our pseudocode so:

substituting

pad10 ' '

we get

prepend 10 ' '

and substituting this, we get:

take 10 (repeat ' ') ++ s

So when we call

pad10WhiteSpaces "Tom"

this substitutes to

take 10 (repeat ' ') ++ "Tom"

when executed, will produce

"          Tom"

Haskell’s automatic currying can take a bit of getting used to but it makes for beautiful code! It really shines when you want to re-use a multi parameter function to create a function that can only take fewer or even one parameter. For example, if we had a list of Strings and we wanted to produce a list of all the these same String values but with each one padded with 10 spaces. All we need is the original prepend function and this transformation would be as simple as mapping (prepend 10 ‘ ‘) over the list of Strings:

map (prepend 10 ' ') ["I", "like", "curry", "a", "lot"]

Isn’t that handy!

Executing this results in

["          I","          like","          curry","          a","          lot"]

Leave a Reply

Your email address will not be published. Required fields are marked *