Higher order functions

4th week of CIS 194 got into meat of functional programming: higher order functions. These are functions that either take other functions as parameters or return functions when called. While I was very familiar with them before, Haskell has neat trick in the sleeve for them. Topics covered included anonymous functions, function composition, partial application and folds (again).

Syntax for anonymous functions took a bit to get used to. Instead of the familiar fn, they’re defined with \, because it sort of looks like lambda character with the short leg missing. So to define an anonymous function that adds two parameters together, one would write:

(\a b -> a + b)

Parentheses are needed to indicate compiler what part of the line actually is the lambda, as they usually appear in the middle of other stuff. As usual, lambdas serve best a simple, throwaway functions, that don’t have too much of logic in them.

Composition I have been using quite a bit already, as I like to treat my program as a pipeline for data. You can’t always use composition, but sometimes types line up just perfectly and a pipeline can be formed. For example, in order to process a list of numbers by multiplying them by two and then adding one, one could write:

doubleUp :: Num a => [a] -> [a]
doubleUp = map succ . map (*2)

This also shows a neat trick that Haskell does with functions. All functions are auto curried. When called with less arguments than what they require, Haskell doesn’t signal an error, but returns a new function. This new function is identical to old one, but the parameters that were supplied are now fixed and can’t be given again. This is why (*2) doesn’t give an error, but creates a function that multiplies value given to it by two. And since map expects a function of just single parameter, it matches nicely there.

map (*2) defines a function that expects a list of numbers and produces a new list of numbers where they have been multiplied by two. map succ does the same, but instead of multiplying just adds one.

One of the exercises was to write program to calculate primes using sieve of Sundaram. The wikipedia article has good explanation of how it works and translating it into Haskell wasn’t too difficult. I ended up golfing around a bit (I pretty much always end up doing that with Haskell and exercises), but that’s just fine as it lets me to practice different things. In the end I had following:

sieveSundaram :: Integer -> [Integer]
sieveSundaram n | n < 1 = []
sieveSundaram n = doubleUp $ filterBySum n $ filterBySize $ createPairs n

createPairs :: Integer -> [(Integer, Integer)]
createPairs n = [(x, y) | x <- [1..n], y <- [1..n]]

filterBySize :: [(Integer, Integer)] -> [(Integer, Integer)]
filterBySize = filter (\(i, j) -> 1 <= i && 1 <= j && i <= j)

filterBySum :: Integer -> [(Integer, Integer)] -> [Integer]
filterBySum n ijs = filter (`notElem` (sums ijs)) [1..n]
                    where sums = map (\(i, j) -> i + j + 2*i*j)

doubleUp :: [Integer] -> [Integer]
doubleUp = map succ . map (*2)

Not sure how readable that is. The basic gist is to create i, j pairs and then filter out ones where i is bigger than j. Resulting pairs are then used to calculate i + j + 2 * i * j and remove results from 1..n range. Finally remaining numbers are multiplied by 2 and added 1 to get final list of primes.


3 thoughts on “Higher order functions

  1. I find Haskell suits mathematical problems well because it allows solutions to be defined almost as one would on paper. I think it’s the combination of all these different features — currying, point-free and composition, comprehensions, decent polymorphism — with powerful lazy loading that allows great expressive power.

    Though an engineer with scalability requirements would seek to optimize that implementation, somehow creating a infinite list and filtering downstream here doesn’t feel wrong. However, I would bet that, if asked to implement an equivalent solution in C, a “traditional” engineer would limit pair generation at its source, among other early optimizations.

    • For me the biggest draw in Haskell probably is how it lets me to write what things are, instead of how to calculate something. There’s plenty of things I like fascinating in Haskell, but that’s probably the biggest one.

      I wanted to write a completely lazy implementation of the sieve, which could generate larger and larger numbers (getting slower as it goes of course), but couldn’t really figure out how. Probably would have to take the whole implementation apart and write it from scratch. If it even is possible, I’m not quite sure. But it was fun exercise nevertheless.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s