In the land of "tl;dr", the oneliner 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 oneliners 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 aweinspiring, as shrinking code can take considerable skill; most recently, I’ve been stunned by a 1433character chess engine in C.
Having already praised Bash oneliners, 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 oneliners:
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 emptylist 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 emptylist case into the same line as the inductive step? Yes, if you share my appreciation for oneliners! 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 subproblems to get oneliners. 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 nletter strings consisting of the letters in "BEN":
f = induct [""] $ \n > [x:xs  x < "BEN", xs < f (n1)]
Compute an nbit Gray code:
g = induct [""] $ \n > (map ('0':)) (g (n1)) ++ (map ('1':)) (reverse (g (n1)))
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.
No comments:
Post a Comment