Wednesday, October 05, 2016

TMTOWTDI, Haskell Style

I assure you there will be no further allusions to Korean earworms. That said, on to the subject at hand...

Remember the exercise in the online Haskell course that had several tests to filter out weak passwords, all of which had to pass for the fictitious system to allow a String value to be used as a password? I wanted to make it easy to change, so I wanted to take a [String -> Bool] and get a [Bool] I could apply and to for the final thumbs up/thumbs down decision.

The first step: roll my own, which has a pleasing symmetry with map if you write it as a list comprehension:

wonkyMap fs x = [f x | f <- fs]

Then I stumbled across Derek Wyatt's blog post about using sequence for the purpose. Life was good... and then I got Haskell Programming from first principles, and life got better, because its authors do a very good job of explaining the Applicative type class. Applicative defines two functions, pure and (<*>):

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

Here f is a unary type constructor like Maybe or [] (both of which happen to be in Applicative). Being a Functor is a prerequisite for being an Applicative, as you can see from that first line. pure, given a value of type a, gives you back one of type f a. (<*>) is intended to act like function application, letting you take plain old a -> b values and apply some number of them (possibly zero--an empty list is a list, and Nothing is a Maybe (a -> b)) to some number of a values in an f a and get back an f b.

For our purposes, f is [], and if you think about it there's not much choice for what pure and (<*>) can be:

 instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

That's almost exactly what we want--the only thing we have to do is put our candidate password in a list (purify it?), like so:

s `satisfies` cs = and $ cs <*> [s]

So, for this exercise, Haskell is kind of Perl-like: TMTOWDI (there's more than one way to do it). Some would say this shows Haskell is Perl-like in a worse way, namely having weird unintelligible operators. I won't take a position, save to say that ghci makes it a lot easier than Perl (or APL, the original "WTF does this do?" language). :t is your friend!

Prelude> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Now, are all three ways we've come up with equally good? Rolling your own function is a way to start, but why reinvent the wheel? sequence works, but

Prelude> :t sequence
sequence :: (Monad m, Traversable t) => t (m a) -> m (t a)

is far more general than (<*>), so that it takes more thought to realize it can be used this way. (<*>) more directly and specifically says it has to do with what we want, so I would argue that it is clearer.

One more thing: type classes don't just have functions; they have rules that those functions must follow. I urge you to track down the rules for Applicative and persuade yourself that [] satisfies them.

A flashback and analogy

You've probably heard about how the notion of sum types (e.g. Algol 68 union s, Rust enum s, Haskell type s) and product types (e.g. tup...