Tagline-Oriented Programming

In the land of "tl;dr", the one-liner is king. Short is sweet, and also highly contagious. A paragraph is easy to ignore, while a good tagline embeds itself in a reader’s mind against their will, spreading independently of the accompanying product.

In programming, some one-liners are equally alluring. There is only room for the bare essentials: we must distill the purest form of solutions to problems. Their brevity makes them memorable, and awe-inspiring, as shrinking code can take considerable skill; most recently, I’ve been stunned by a 1433-character chess engine in C.

Having already praised Bash one-liners, this time I’m taking a shallow look at Haskell, and in particular, a trivial function:

emp :: a -> ([b] -> a) -> [b] -> a
emp a f [] = a
emp a f (x:xs) = f (x:xs)

Or since we’re advocating one-liners:

emp a f x = if null x then a else f x

Why? In Haskell, recursion on lists often goes like this:

f []     = empty_list_case
f (x:xs) = recurse_somehow x f(xs)

The emp function let us combine these two lines into one. The fold family of functions is similar: for them, the 2nd argument handles the empty-list case, while the 1st argument is a function that describes how to process the next element. However, they are insufficiently general for our purposes.

Should we go to this trouble just to squeeze the empty-list case into the same line as the inductive step? Yes, if you share my appreciation for one-liners! Also:

• this is a natural extension of the precedent set by the fold family

• it’s harder to forget about the base case

• single lines suit interactive Haskell (if you do type these in, remember to add "let" in front of the definitions).

Examples

Here’s foldl and foldr in one line each:

foldr f z = emp z $ \(x:xs) -> f x (foldr f z xs)
foldl f z = emp z $ \(x:xs) -> foldl f (f z x) xs

And the membership test:

elem x = emp False $ \(y:ys) -> x==y || (x `elem` ys)

All subsequences (though in an order differing from Data.List.subsequences):

sub = emp [[]] $ \(x:xs) -> sub xs ++ (map (x:) (sub xs))

How about all permutations? In C, where we can loop through an array and swap elements in place, an easy but impure recursive solution takes every element in turn, temporarily swaps it to the first position, then calls itself on the remainder of the elements, where the lowest level of recursion prints the whole buffer.

In Haskell, I found it easiest to do something similar by maintaining 2 lists on either side of a selected element. My first attempt came out as:

-- Invoke with: p "" "" "abc"
p a [] [] = [a]
p [] ys [] = []
p a ys [] = map (a++) (p [] [] ys)
p a ys (x:xs) = (if null a then (p [x] ys xs) else []) ++ (p a (x:ys) xs)

It’s unclear how to rewrite this in one line. Perhaps it’s best to break the problem into two sub-problems to get one-liners. The following is based on elegant code found on a mailing list:

f = emp [] $ \(x:xs) -> (x,xs):[(y,x:ys) | (y,ys) <- (f xs)]
perm = emp [[]] $ \xs -> [y:zs | (y,ys) <- (f xs), zs <- (perm ys)]

The helper function f is the FP version of iterating through a list and plucking an element out, and has uses outside this problem.

Integers

A similar definition for integers is also handy:

induct a f x = if 0==x then a else f

For starters, we can define emp with induct:

emp a f = induct a f . length

List all n-letter strings consisting of the letters in "BEN":

f = induct [""] $ \n -> [x:xs | x <- "BEN", xs <- f (n-1)]

Compute an n-bit Gray code:

g = induct [""] $ \n -> (map ('0':)) (g (n-1)) ++ (map ('1':)) (reverse (g (n-1)))

Though shallow, Haskell would gain from default induct and emp functions. (Perhaps there already are? I don’t know Haskell that well.) They bring the length of many interesting function defintions under a mystical threshold that makes them catchy and appealing.