Whatever happened to “Question Authority”?

Sometimes a rout is still fun to watch, e.g., Don't Know Much About Capitalism by Tom Woods.

What it all boils down to is this: one side of our political spectrum favors the central planning of Iraq, while the other favors the central planning of Americans. We can only hope for the continued growth of a third side, one that rejects as unworthy of a free people all the superstitious nonsense about the magical powers of our overlords, whether that power is exercised at home or abroad.

Henson's 11

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]

Vanity search

At work, we're evaluating Safari Books Online. I knew they offered more than only O'Reilly titles, so I hoped to find Scott Chacon's Git Internals. No dice.

Maybe in need of a pick-me-up after such a harsh letdown, I searched for my own name. In the results were books that I tech-edited (Perl Developer's Dictionary and SAMS Teach Yourself Perl in 24 Hours), O'Reilly books that have my work, and a few where I'm mentioned in the acknowledgements—Real World Haskell being of recent note.

I was surprised to see a hit in Perl Debugged by Peter Scott and Ed Wright. In Section 3.5, the authors gave a list of people whose code readers ought to emulate, e.g., Larry Wall, Gisle Aas (author of LWP), Tom Christiansen, Nat Torkington, Mark Jason Dominus (author of Higher-Order Perl), Chip Salzenberg, Gurusamy Sarathy, and—both last and least—your humble host!