Thinking functionally

Carey's been learning functional programming with F#, and as a learning exercise he solved in F# Project Euler's Problem 1.

Consider the meat of a solution in Haskell (with which we'd get the answer via sum $ multiples 1000 [3,5]): Data.List's union function computes the union of two lists, e.g.,

Prelude Data.List> union [1..3] [3..6]
[1,2,3,4,5,6]

The types of expressions convey a lot about what they do, so let's pick apart the above definition:

*Main Data.List> :t foldl union []
foldl union [] :: (Eq a) => [[a]] -> [a]
*Main Data.List> foldl union [] [[1..3],[3..6]]
[1,2,3,4,5,6]
*Main Data.List> foldl union [] [[1..3],[3..6],[1..7]]
[1,2,3,4,5,6,7]

So the fold allows us to compute the union of an arbitrary number of lists. If this still seems puzzling, remember that the sum of a list of numbers is foldl (+) 0. Take a look at the graphic representation of fold to help your intuition.

The dot is function composition—chosen for its similar appearance to ∘ as used in many math texts, e.g., (f ∘ g)(x). Recall from algebra class that you understand composed functions by reading "inside-out."

So we know we're computing a union of lists, and from the problem statement, we want products of 3 and 5. So the rest must be generating those products.

Its name makes takeWhile's value obvious, but consider an example:

Prelude Data.List> takeWhile (<4) [1..10]
[1,2,3]

So that's capping the products at whatever the value of max is, but what about the goofiness inside?

*Main Data.List> :t flip (map . (*)) [1..]
flip (map . (*)) [1..] :: (Num a, Enum a) => a -> [a]

Although it may not be obvious yet, this is generating all multiples of a given n.

With flip, we reverse the operands of a binary function:

*Main Data.List> :t flip
flip :: (a -> b -> c) -> b -> a -> c

But what are we flipping?

*Main Data.List> :t map . (*)
map . (*) :: (Num a) => a -> [a] -> [a]

Point-free style looks unintelligible coming from an imperative background, but you'll see it all over in Haskell code. Someone once quipped that Haskell is to manipulating functions as Perl is to manipulating strings. We might equivalently write the above function as

*Main Data.List> :t \n xs -> map (n*) xs
\n xs -> map (n*) xs :: (Num a) => a -> [a] -> [a]

Note that backslash is lambda, i.e., the function above takes two arguments with its value being xs scaled by n.

This particular definition has issues. We have to build in the upper-bounding machinery because the function isn't lazy. Consider:

*Main Data.List> take 10 $ multiples 1000 [3,5]
[3,6,9,12,15,18,21,24,27,30]

Notice the absence of multiples of 5. They don't come until much later:

*Main Data.List> elemIndex 10 $ multiples 1000 [3,5]
Just 334

Also, union is overkill because we can make use of our knowledge that the multiples will emerge in increasing order: Notice that we no longer have to force an upper bound, and the merged result is nicer:

*Main> take 10 $ multiples [3,5]
[3,5,6,9,10,12,15,18,20,21]