Haskell currying and partial application left over from BarCamp

At BarCamp Bangkok I only managed to partially apply the Haskell talk — Yoda speaks Haskell, which was a shame in many ways because the small bit at the end was the most interesting.

In the talk I said I wasn't trying to teach these aspects of functional programming, just to show what exists and how they can be used. Basically enough to try to interest people in functional programming by letting them see what they can do and hopefully giving enough to prompt them to go and experiment and learn more about it.

In continuing from the end of the talk we had some working code that turned this:

[ "fear", "anger", "hate", "suffering" ]

Into this:

"Fear leads to anger. Anger leads to hate. Hate leads to suffering."

The code we had was this¹ [1How we got there is something I'll write up properly as a session plan when I get time.]:

import Data.Char

-- fix is the Haskell name for the Y combinator
fix :: (a -> a) -> a
fix f = let x = f x in x

-- We'll come to this form later on
inner_duplicate = fix
	(\f x ->
		if length x < 2 then
			[]
		else
			( ( x !! 0, x !! 1 ) : ( f $ tail x ) )
	)

--
-- Our implementation starts here
--

yoda = [ "fear", "anger", "hate", "suffering" ]

leads_to ( l,  r ) = l ++ " leads to " ++ r

sentence ( f : other ) = ( toUpper f ) :  other ++ "."

spaces l r = l ++ " " ++ r

hypozeuxis w =  foldl1 spaces $ map sentence $ map leads_to $ inner_duplicate w

Partial Application

Two of the functions are very similar in form:

leads_to ( l,  r ) = l ++ " leads to " ++ r
spaces l r = l ++ " " ++ r

The first one uses pattern matching to crack open the tuple to get at the left and right sides whilst the second takes the two arguments in the normal Haskell way. As for the expression on the right, both are concatenating the strings with different middle parts.

We can write a new function that takes the innner text as an extra parameter and then re-write the other two functions in terms of it:

interstitial l inner r = l ++ inner ++ r
leads_to ( l,  r ) = interstitial l " leads to " r
spaces l r = interstitial l " " r

This is nicer in many respects, but we can do much better. Looking at the spaces function we see that it is taking r as its last parameter and just passing that on. We can just factor this r out.

spaces l = interstitial l " "

When we say that spaces takes one argument followed by another we mean it quite literally in Haskell. This new version of the function takes the first argument and applies it straight away to interstitial. The thing that is returned is a function that will wait for the second argument before it can execute and return the string we want.

This technique is called partial application. We apply some, but not all, of the arguments to a function and we get back a function that is waiting for the other arguments. We can use this with the argument l as well if we re-order the arguments to interstitial.

interstitial inner l r = l ++ inner ++ r
leads_to ( l,  r ) = interstitial " leads to " l r
spaces = interstitial " "

This is much more pleasing. By making interstitial take the inner text first we can configure it by passing this in once and we can then apply the other two arguments when we have them available. Clearly it hardly seems worth the bother of having spaces at all as a function and we can just wrap it in to our hyposeuxis function.

hypozeuxis w =  foldl1 ( interstitial " " ) $ map sentence $ map leads_to $ inner_duplicate w

Curry

leads_to is so close in form to our old spaces that it seems a shame that we can't do something similar with it. It however takes the two arguments together as a tuple rather than one at a time.

Thankfully there is a way to convert between these two forms. To go from a function which takes two arguments at the same time to one that takes them one after another we use a conversion called curry. The process of taking a function that expects one argument one after the other to one that takes two at the same time is called uncurry. It is this we want as we will take interstitial, partially apply one argument which leaves us with a function that takes two arguments one after the other. To leads_to we pass both arguments at the same time.

interstitial inner l r = l ++ inner ++ r
leads_to = uncurry ( interstitial " leads to " )

Again, it hardly seems worth the bother of having this as a separate function now. Removing it leaves us with a pleasingly short program.

yoda = [ "fear", "anger", "hate", "suffering" ]

interstitial inner l r = l ++ inner ++ r

sentence ( f : other ) = ( toUpper f ) :  other ++ "."

hypozeuxis w =  foldl1 ( interstitial " " ) $ map sentence $ map ( uncurry ( interstitial " leads to " ) ) $ inner_duplicate w

There are a few other things that can be done from here, but this should be enough to start to explore more partial application and currying from.

The techniques can be used from many other languages and they also have parallels with object oriented techniques² [2Think of passing parameters to a an object's constructor as an analogy for partial application and a method returning an object which has more methods on it as an analogy for currying.]. They are however much more clearly seen in Haskell.