It's hard to find small examples that are unambiguously better in Haskell. Even if we have a program that's neater and shorter in Haskell, people unfamiliar with its abstractions will claim that the Python version is "obvious" and the Haskell version is too esoteric. And hey, I suppose that's true for them—it just says more about what they're familiar with than the quality of code in either language.

I feel this disqualifies most Haskell one-liners: too many people would see them as glib and little more. Consider the oft-cited "list powerset" function that gets you every sublist of the argument:

powerset :: [a] -> [[a]] 
powerset = filterM (const [True, False]) 

Personally, I'm entirely comfortable with this code. It defines what a powerset is: it's what you get if you both include and exclude every possible element in a list. But I'm already comfortable thinking this way; somebody who isn't—perhaps someone unfamiliar with how the list monad works or someone with a more operational mindset—would find this function obfuscated. (In fact, that's exactly the second comment said on the Reddit thread I found by googling "Haskell powerset".)

The code is just too cute.

A good example would have to be a bit larger and would have to rely on Haskell's expressiveness in ways that would be awkward to reproduce in Python. So that's what we have to identify: ways in which Haskell is more expressive than Python.

I have a couple in mind, but we could come up with more.

• algebraic data types, coupled with pattern matching, make it easier to work with a whole class of tasks. In particular, it's much easier to write code that works with programming languages or formal languages.
• laziness is exceptionally powerful. Among other things, it makes it easier to represent data of arbitrary size and resolution without losing information when things get combined, "at the seams". A slightly involved example is a data type for 2d image data with infinite extent and resolution, which we can get with lazy quadtrees.

That second one is especially relevant: I can imagine doing it in Haskell, even reasonably easily in the simplest case, and can't imagine doing it at all in Python. At best I'd try to port my Haskell code, but it would be incredibly tedious and error-prone.

Algebraic Data Types

In Haskell, it is natural to express your computations by pattern matching over algebraic data types. Often, the code you have to write flows directly from the types: you set your problem up and the solution falls right out of the setup.

I've actually had this come up in the real world, on my interview with Jane Street. Of course, I can't tell you the details of the question, but I had a much easier time with it than I should have. It was significantly easier than the other questions I had and I believe I did much better on it than most people—all because I used Haskell. (Well, to be fair, OCaml would have been just as good in that instance.)

And why? Because it centered around working with formal languages and, through that, trees. After I defined the types I needed, solving the problem was almost systematic: I pattern matched on my types, handled all the cases and derived the final function step by step.

This is going to hold for most problems to do with programming languages or formal languages—especially problems small enough to fit into an interview. An example might be to implement an algebraic solver that can handle variables and simplifies arithmetic expressions as much as it can. You start with the types

data Expr = Var String 
          | Lit Integer 
          | Expr :+: Expr 
          | Expr :-: Expr 
          | Expr :*: Expr  deriving (Show, Eq) 

Then you implement the logic to simplify. It's a bit fiddly, but flows from the types pretty directly—simple enough in Haskell but, I believe, rather harder in Python.

simplify :: Expr -> Expr 
simplify expr 
  | nextStep == expr = expr 
  | otherwise       = simplify nextStep 
  where nextStep = case expr of 
          Var x -> Var x 
          Lit n -> Lit n 
           
          (Lit n1 :+: Lit n2) -> Lit (n1 + n2)  
          (Lit n1 :-: Lit n2) -> Lit (n1 - n2) 
          (Lit n1 :*: Lit n2) -> Lit (n1 * n2) 
 
          (e1 :+: e2) -> simplify e1 :+: simplify e2 
          (e1 :-: e2) -> simplify e1 :-: simplify e2 
          (e1 :*: e2) -> simplify e1 :*: simplify e2 

One really cool part is that this code is easy to extend. For example, to handle 0 and 1 intelligently, you would just have to add a few more patterns:

          (Lit 0 :*: _) -> Lit 0 
          (_ :*: Lit 0) -> Lit 0 
 
          (Lit 0 :+: e) -> simplify e 
          (e :+: Lit 0) -> simplify e 
          (Lit 1 :*: e) -> simplify e 
          (e :*: Lit 1) -> simplify e 

The shape of the code follows the types closely and the simplification rules are expressed in an immediately natural way. The code is easy to derive and the types help you cover all the cases you need and make it easier to extend the code with additional functionality—something interviewers love to ask about. (With good reason: it's something that's incredibly important in real world programming too!)

You could do all this in Python of course, but it would be more awkward and painful. I've experienced this first-hand when the homework for my programming langauges class was in Python. The Haskell story is much nicer.

Laziness

Another facet of Haskell that stands out as particularly expressive is laziness. Relying on laziness, we can express ideas and abstractions directly that would be painful without it.

One advantage is that we can write algorithms that have to be evaluated interleaved in lexically separate chunks. This, for example, gives us a trivial-seeming efficient function to select the top k elements from an unordered list:

select :: Ord a => Int -> [a] -> [a] 
select k = take k . sort 

We just use our normal sort function and rely on laziness to not sort the whole list. As long as the sorting function is reasonable itself, this has the asymptotics we want.

An interesting approach, but one that borders on "cute" and not that difficult in Python. (In part because Python has laziness built in—but just for lists, in the form of generators!)

We want something a bit more interesting, relying on laziness in less trivial ways. What's laziness good at modeling that's difficult without it? Infinity, especially infinity in the sense of arbitrary precision—think real numbers. Here's an interesting problem, perhaps a tad cruel for an interview: design a data type to store the positions of objects in two dimensions with arbitrary precision. This could be used, for example, for graphics that are resolution-independent. We want to index into a continuous area ([math]\mathbb{R}^2[/math]) in a way that's simpler and more general than something like SVG.

So how can we do this? Well, a reasonable way to represent image data in two dimensions is to use a quadtree. A quadtree indexes a two-dimensional space by repeatedly breaking it up into quadrants. Areas that contain more details are broken up into smaller quadrants and areas without much detail are left at a higher resolution.

A finite quadtree for a lightning bolt. Picture in the public domain from Wikimedia.

To get an arbitrary resolution, we can use a lazy quadtree with a potentially unbounded depth. When we need to render it at a given resolution, we evaluate it up to some limit, approximating (ie anti-aliasing) after that. The simplest case—just black and white pixels, with "gray" as our approximation—is short enough to comfortably fit into an interview. More complex cases, like arbitrary colors, are going to be trickier and more fiddly but will follow the same general idea.

The reason this is easy with Haskell is that data types are lazy by default. A potentially infinite quadtree that we can evaluate in part is… just a normal quadtree:

data Quad = White 
          | Black 
          | Gray Quad Quad Quad Quad 

Being able to make infinitely deep quadtrees is actually useful: we can have a single circle function that produces a quadtree of a circle that would render as well as possible for any resolution. The same capabilities as SVG but simpler and more general. We would be able to use these infinite trees like any other image data, combining with other quadtrees and never losing information until the end—operations compose seamlessly and any rounding is explicitly part of rendering, not part of the data representation itself.

Writing operations over Quad is a matter of pattern-matching and is pretty straightforward in a similar way to the expression evaluator I showed earlier.

Some operations require a tiny bit of cleverness to keep them lazy—you want to avoid any operation that requires reading in the full depth of the tree like simplifying equal nodes into larger ones. But keeping this in mind is not difficult—it's something that comes with a bit of practice. You end up with enitely lazy transformations of quadtrees that you can chain as much as you like and, thanks to the magic of lazy evaluation, only enough of each step will be performed to get the final result you want. You never need to compute the whole thing which is great because the whole thing might stretch forever!

Even this is already going to be significantly more difficult without laziness. I wouldn't even know where to start in Python, except perhaps by trying to emulate Haskell—poorly. But we can actually take this problem a step further: what if we want to expand our code to have an unbounded extent? That is, what if we not only want to support arbitrary resolutions but also an infinite canvas?

To make this work, of course, we can't ever store the whole canvas in memory—we have to evaluate no more than we need to render. Sounds like more laziness!

Why is this useful? Well, it lets us express useful things like grids or space-filling curves or fractals or noise in a way that can be combined with other images, no matter how large those images are. And the logic is useful even if we don't care about fully infinite extents: it will let us perform operations on large images, reuse sub-parts of those images in other places and then only compute the minimum we need to render any given result. Image code written like this is supremely composable and modular.

To get an unbounded resolution, we had a lazy tree that could extend as far downwards as it wanted. To render it, we just evaluate as far down as we need to hit our desired resolution, and approximate after that. However, the area we're evaluating is inherently bounded: the tree we start with it the biggest, and all its subtrees—a potentially infinite sequence—represent smaller and smaller regions.

What we need is a tree that's lazy in both directions: we can travel as far down as we like and we can travel as far up as we like. The higher we go, the larger the region covered. To render a given region at a given resolution we would first ascend high enough to cover that region and then descend low enough to hit our resolution. At each step, we rely on laziness to not compute anything extraneous.

To be fair, this is still tricky even in Haskell. But it's approachable or even—if you know the right abstraction—systematic. To travel up and down a tree (or any other type), we can use a zipper and we can derive the zipper for any type programmatically. (Fascinatingly, it's the result of taking the derivative of the type.)

I'm pretty confident in these ideas and could work them out in Haskell on an interview, with some fair hints and prodding. It would be unfair to expect somebody to know all the tricks, but going from "lazy quadtree" or "lazy quadtree with zipper" to the right type and arguments is eminently reasonable. That's pretty much what I did: I got the high-level idea from Conal's blog but could go from that to a real implementation myself.

I can't even begin to imagine doing this in Python. At best, I could work out all the details in Haskell and try porting them to Python but I doubt I could get there without running into hoards of bugs. Attempting to emulate laziness, algebraic data types and pattern matching in a language that supports none of them is miserable.

So there's a great example of something easier in Haskell than in Python: an image representation with unbounded area and unbounded resolution, allowing us to compose and manipulate images without losing any information along the way and finally computing exactly what we need to render them without doing extraneous work.

I think that's pretty cool. And you could totally fit a bare-bones version into an interview question. But if you're interviewing people who aren't au fait with laziness, it's just sadistic and cruel.