Pretty Code with Haskell December 16, 2020

The nice thing about having a “thoughts” section is that unlike a technical blog, I don’t feel pressured to make my posts particularly technically impressive. I can just write about random stuff that popped up in my life that’s kind of short and silly.

I’ve always had a tenuous working relationship with monads; I know just enough to use them for basic things and get through the monad homework for a little type theory survey course that I took, but I wouldn’t say that I have any great understanding. So it’s always pleasant when I find that I can sprinkle in a little bit of monadic thinking into my code. I am under the impression that they make one look terribly clever.

Anyway, wanting some relaxation after a somewhat taxing final exam, I decided to write a tiny bit of Haskell to solve a problem.¹ The problem is the $d$-sum problem:

Fix an integer $d > 0$. Given a list of $n$ integers, are there $d$ (not necessarily distinct) elements that sum to $0$?

Assuming the integers are bounded by $n^{\text{poly}(d)}$ in magnitude, there’s a very obvious $\tilde{O}(n^d)$ strategy (the $\text{poly}(\log n)$ factors may arise from arithmetic operations), which is to just try every possible combination of $d$ elements.² Here’s a short snippet which does the slightly more general task of seeing if any $d$ elements sum to a specified target value:

{- computes all combinations of k elements of a list, with replacement -}
combinations :: (Integral t) => [a] -> t -> [[a]]
combinations list 0 = []
combinations list 1 = map return list
combinations list k =
  combinations list (k-1) >>= \elt -> map (:elt) list

{- solves the d-sum problem inefficiently -}
dSum :: (Integral t) => [t] -> t -> t -> Bool
dSum list d target =
  any (== target) $ map sum $ combinations list d

I think the use of the return and >>= operators on the list monad make the code a little prettier, and at least on toy problems, Haskell is always a joy to read. (Though of course, (:[]) is a little shorter than return for lists, but I like the longer word.) But then I saw this and thought: hey, wouldn’t it be nice to make it even more monadic? One of the best things about Haskell is that it’s flexible enough to allow you to write very elegant code. One of the worst things about Haskell is that it’s also flexible enough to allow you to write nearly unreadable code. Here’s a more generalized variant of the same combinations function:

import Control.Monad
import Control.Applicative
import Control.Functor

combinations' ::
  (Integral t,
   Monad m,
   Alternative m,
   Monoid (m (m a))) => m a -> t -> m (m a)
combinations' list 0 = mempty
combinations' list 1 = fmap return list
combinations' list k =
  combinations' list (k-1) >>= (list <&>) . (flip $ (<|>).return)

These behave identically, as one would expect, when you give them a real list:

λ> combinations' [1,2,3] 3 == combinations [1,2,3] 3
True
λ> (length $ combinations (take 5 [1..]) 4) == 5^4
True

I spent way too much time looking up the right <&>, <|>, <*>, etc. operators to do what I wanted.