Second order functions

16 July 2009
In Haskell there are second order functions, which is when functions take other functions as parameters. To show its usefulness consider the built-in function map which applies a function to every element within the list; in the example below [1,2,3,4] becomes [2,4,6,8]:

double :: Int -> Int double x = x*2 map double [1,2,3,4]

Now suppose you wanted to apply a threshold to a list of numbers. Naturally you would define a function that takes both the threshold value and the value to be checked:

threshold :: Int -> Int -> Int threshold limit x | x < limit = 0 | otherwise = x

However unlike double, threshold takes two parameters. This is not a problem as in Haskell you can create a 1-variable function by filling in the earlier parameters. Hence to calculate [0,0,0,0,5,6,7,8] from [1,2,3,4,5,6,7,8] you can use:

map (threshold 5) [1,2,3,4,5,6,7,8]

This is an examples of partial evaluation, and it is very useful. To demonstrate this usefulness, I was recently writing in Python a tokeniser. Tokenisers are normally implemented using switch statements; however Python does not have switch statements, so they have to be emulated using functions and dictionaries (dictionaries are basically hash-tables)

token = { '"' : readString, '$' : readVariable, '(' : readSymbol, ')' : readSymbol, ';' : readSymbol }[char]()

The problem arose because readSymbol was a special case where I wanted to pass forward the current character as an extra parameter, and I definitely did not want to use an if-then-else chain. Mercifully Python's lambda function can perform what amounts to partial evaluation:

token = { '"' : readString, '$' : readVariable, '(' : lambda : readSymbol(extraParam), ')' : lambda : readSymbol(extraParam), ';' : lambda : readSymbol(extraParam) }[char]()

(16th July 2009)