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? 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.