Building a 1000 line Java program in 6 lines of Haskell

Some languages are very expressive and some languages are Java. Let's disassemble an overly expressive six-line algorithmical Haskell program. I'll walk you through all the tricks, weirdness and beauty.

Note I'm not assuming any Haskell knowledge, but some familiarity with another programming language is of advantage.

The six-line program that we are disassembling solves a coding interview problem called the knights tournament. Let me give you a quick overview of it.

The Knights Tournament 🔗

There is an arbitrary but fixed number of knights n. These knights are healthy and strong, the healthier they are the more health points they have, the stronger they are the more damage points they deal. But these knights have an unlucky fate: They are battling each other until only one knight is left. The rules are strict. They stand in a circle and can only hit the knight to their right. The order of hits is well defined: After a knight was hit, they are allowed to make the next hit. Well, if they are still standing. If that is not the case, then the knight to the right that would have been hit can take their turn to hit. This continues as long as there is only one knight left. There can only be one winner.

The Approach 🔗

Before we dig into the code, let's conceptualize a solution. Haskell works with immutable data structures, so typically the solution concepts already look way different from their mutable counterparts. Trying to make a mutable solution concept work in a functional programming language is madness and can quickly lead to frustration.

The main entity we are dealing with is a knight. A knight has a name, health points and damage points. We express the circular arena of knights as an immutable list of these knights.

The tournament is divided into turns when a knight hits another knight. We define a turn as a function that takes the arena of knights as an input and returns a new arena of knights. That new arena describes the state of the arena after the hit of the turn was done. That is, it reduces the health of the hit knight and might even remove the knight if its health below zero.

How do we express which turn it is? With a turn being done, we move the first knight to the end of the arena list. So it's always the first knight's turn. We kind of use the list as a queue, always taking the first knight and moving them to the back of the queue. This continues as long as the size of the queue becomes 1.

The Knight data type 🔗

In Java, we would go ahead and define a class Knight with fields, a constructor and possibly getters and setters and a toString and would already be way beyond six lines. In Haskell it is one line.

data Knight = Knight String Int Int deriving (Show, Read)

We define the data type Knight with three fields of type String (the name), Int (the damage points) and Int (the health points). The fields are identified by their position rather than a name. There are also data types that allow to identify fields by a name, but identifying by their position has advantages later on.

The keyword data expresses that we want to define such a data type. The first Knight defines the name of the type. The second Knight defines the constructor to create an instance of the type. This constructor accepts the three fields and can be used with Knight "James" 3 12. This constructs a knight James with twelve health points and three damage points.

Note In Haskell, you don't have to use brackets () for function calls. You can imagine it to be like bash where you also write git status instead of git(status) or git("status").

The keyword deriving instructs Haskell to automatically provide us with some functions for this data type. The type class Show provides us with a show function that transforms a knight into a string representation. Haskell gives us the default implementation inferred from the constructor name and field names which is Knight "James" 3 12. The type class Read provides us with the counterpart to show. It defines a function read that takes a string representation of a knight and constructs a knight from it. These two methods allow us to interact with the input of the user from the command-line.

Taking a hit 🔗

We're reaching line 2 and 3. This is a small helper function takeHit to express what it means for a knight to take a hit. It takes two arguments: A knight and the damage points dealt to that knight. It returns a single element list of that knight with that damage dealt to it. Or an empty list, well, if the knight decided to drop out of the tournament.

takeHit (Knight name damage health) points =
  map (Knight name damage) $ filter (>0) [health-points]

The first line declares the signature of the function takeHit accepting the knight and the points. We use a technique called destructuring for the knight. We could write takeHit knight points and would have the knight available as a variable knight in the body of the function. But we are actually only interested in its fields. So we destructure the knight into its fields such that we can refer to name, damage and health directly.

Note Haskell is a statically typed language with powerful type inference. The function might look to you dynamically typed, but Haskell is actually able to figure out that Knight name damage health is of type Knight and points is of type Int and that takeHit returns a list of knights [Knight]. Nevertheless, it can be beneficial for better error messages and readability to add the optional type signature takeHit :: Knight -> Int -> [Knight] manually.

The second line is the function body. There are multiple things going on there. First, writing f $ g x is syntactic sugar for f (g x). It avoids having to count closing brackets if there is a longer call chain f (g (h (k (x)))) where you can instead write f $ g $ h $ k x.

We define a list [health-points]. It is a single element list that would be [7] for a knight with 12 health points and 5 damage points dealt to it. The resulting health can be negative, in that case, we want to have an empty list instead. To achieve that, we filter the list with a function >0. This expression >0 uses a Haskell language feature called partial application. It is equivalent to a lambda \x -> x>0. By leaving out the left part of the comparison, Haskell knows that >0 is not true or false, but rather a function where the left part of the comparison still needs to be passed before it resolves into a true or false.

So with filter (>0) [health-points], we either have a single element list of positive health points or an empty list. We now want to construct a new knight from it (or rather the same knight with different health points). To achieve that, we map the list. Knight name damage is again a usage of partial application: The health points still need to be provided. Hence, Knight name damage is a function accepting health points and returning a knight with that name, damage and health points.

The result of the full body is therefore either a single element list of a knight with the same name and damage points and reduced health points or and empty list.

The turn 🔗

We now want to define the function that takes the arena of knights, performs a single knight's turn on it and returns the updated arena.

turn (knight@(Knight _ damage _) : knight' : knights) =
  takeHit knight' damage ++ knights ++ [knight]

We use a slightly more ambitious form of destructuring in the signature of turn. The whole expression (knight@(Knight _ damage _) : knight' : knights) is a list of knights [Knight]. With knight : knight' : knights, we are telling Haskell to allow us to refer to the first knight of the list as knight, to the second knight of the list as knight' and to the other knights as knights. With knight@(Knight _ damage _), we are saying that we are not interested in the name and health since we use the placeholder _. But we want to be able to refer to the knight as a whole with knight. That is achieved with the syntax knight@(...).

The resulting arena consists of three parts that are added together with the list concatenation function ++. The first part takeHit knight' damage is the second knight that is taking the hit of the first knight and should afterwards be the new first knight since its their turn afterwards. Remember that the return value of takeHit is either a single element list of the knight or an empty list. In case it is an empty list, it will be the turn of the first knight of the other knights afterwards (the third knight). The second part knights are all the other knights. The third part [knight] is the previously first knight that now is at the end.

The main loop 🔗

We want to read a list of knights [Knight "Bob" 3 12, Knight "Alice" 4 24, Knight "Jean" 3 16] from the command-line and print the winning knight Knight "Alice" 4 9 at the end after all turns have been done and only one knight is still standing.

main = getLine >>= putStrLn . show . head . until ((1==).length) turn . read

The function main has a dedicated role in Haskell like in Java. It is the entry point of the program. The expression getLine tells Haskell to read a single line from the command-line as a String. This line, we pass as argument to function putStrLn . show . head . until ((1==).length) turn . read.

Two things:

• The dot . is a composition function. An expression f (g x) is equivalent to (f . g) x. So if we write f . g, it is equivalent to the longer version \x -> f (g x).
• The >>= function is like the dot ., but works for the dedicated type IO String that getLine returns because it works with the outside world (the command line).

Let's disassemble putStrLn . show . head . until ((1==).length) turn . read. Such an expression, you read from the right to the left. We have our line of type String and pass it to the function read. The function read tries to parse a list of knights [Knight] from that String.

Note How does the generic function read knows that it should parse a list of knights? Because the following expression until ((1==).length) turn requires its argument to be a list of knights and hence requires the return type of read to be a list of knights. If following expressions would not make the type clear, then Haskell would compile with an error about unresolved ambiguity.

The expression until ((1==).length) turn performs turns on the list of knights until it is a single element list, that is there is a winner. The expression 1== is again a usage of partial application and (1==).length is a function that first gets the length of the list of knights and then checks if it is equal to one or not.

Once we have a list of a single knight, we take that one knight out of the list with head. Then we transform them into a string representation with show and write them to the console with putStrLn.

If we execute it, it looks like this.

$ ghci knights.hs
*Main> main
[Knight "Bob" 3 12, Knight "Alice" 4 24, Knight "Jean" 3 16]
Knight "Alice" 4 9

All together 🔗

The full six line program looks like this.

data Knight = Knight String Int Int deriving (Show, Read)

takeHit (Knight name damage health) points =
  map (Knight name damage) $ filter (>0) [health-points]

turn (knight@(Knight _ damage _) : knight' : knights) =
  takeHit knight' damage ++ knights ++ [knight]

main = getLine >>= putStrLn . show . head . until ((1==).length) turn . read

Conclusion 🔗

We looked at a Haskell six-line program implementing the tournament of knights. We saw how to define a data type and how to get Haskell to provide show and read functions. We learned about destructuring, partial application and function composition. While this program took conciseness to an extreme, I hope I could show you how various functional concepts can be powerful tools to build an expressive application.

Extended version 🔗

A slightly longer version that I would prefer for cases where readability and maintainability are a more important concern than conciseness would look like this. It includes function signatures, input validation and uses the Maybe type to represent a knight that might be alive or gone.

module KnightTournament ( Knight, game ) where

import Data.Foldable
import Data.Either
import Data.Maybe

data Knight = Knight
  String -- Name
  Int -- Health
  Int -- Damage
  deriving Show

type ValidationError = String

validateKnight :: Knight -> [ValidationError]
validateKnight (Knight name health damage) =
  map snd $ filter fst validations
  where validations = [
          (health <= 0, "Knight " ++ name ++ " already dead!"),
          (damage < 0, "Knight " ++ name ++ " can not deal negative damage!")]

validateArena :: Arena -> [ValidationError]
validateArena = concat.(map validateKnight)

-- The arena is a queue of knights
type Arena = [Knight]

-- The knight takes a hit and maybe leaves the tournament
takeHit :: Int -> Knight -> Maybe Knight
takeHit points (Knight name health damage)
  | points < health = Just $ Knight name (health - points) damage
  | otherwise = Nothing

-- The first knight hits the second one and will then be attached to the end.
-- If the health of the second knight is below zero, he is dead and will be removed.
-- If not, he is the next knight who gets the chance to hit.
turn :: Arena -> Arena
turn (knight@(Knight _ _ damage) : knight' : knights) =
  toList (takeHit damage knight') ++ knights ++ [knight]

game :: Arena -> Either [ValidationError] Knight
game arena = case validateArena arena of
  [] -> Right $ head $ until ((1==).length) turn arena
  errors -> Left errors