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.