Haskell – Solving Simple Diophantine Equation with Functional Programming

Haskell is a statically typed, purely functional programming language known for its concise syntax and mathematical precision. It utilizes lazy evaluation, meaning it only calculates values when they are strictly needed, allowing for the creation of infinite data structures. This encourages a declarative style of coding, where you describe what something is rather than how to compute it step-by-step.

The problem: Red and Black Shirts

Imagine you enter a store where red shirts cost 18 USD and black shirts cost 11 USD. For some reason you have exactly 1188 USD and you are willing to spend all of these in that store for these two items. The puzzle is to figure exactly how many of each shirt you can buy. Mathematically, this is a Linear Diophantine Equation:

18x + 11y = 1188

We need to find integer values for x (red shirts) and y (black shirts) and these should be whole numbers (Z). Since there are two variables and only one equation, there could be multiple solutions – or none.

The solution

To solve that with Haskell, we will build a model, a mathematical solver and finally a generator for all posible answers.

1. Modeling the Equation

First, we define a custom data type to represent the equation ax+by=c. We call it LDE2 (Linear Diophantine Equation with 2 variables). We also define a checkSolution function that takes a pair of numbers (x, y) and returns True if they satisfy the equation:

• data LDE2: This holds our three constants (a, b and c). For that problem this will be 18, 11 and 1188.
• checkSolution: This performs the math a*x + b*y == c and returns a boolean.

2. Finding a Concrete Solution

To find the first answer without guessing (as we are developers, developers, developers), we use the Extended Euclidean Algorithm. This algorithm calculates the Greatest Common Divisor (GCD) of a and b, while finding the coefficients x' and y', such that:

a*x' + b*y' = GCD(a, b)

That recursive function returns a tuple (d, x, y).

However, this only solves for the GCD (which is 1 for 18 and 11). We need to solve for our total cost, 1188. We write concreteSolution, to scale these coefficients up. If 1188 is divisible by the GCD, we simply multiply x' and y' by the scaling factor k.

Running this on our problem gives us Just ((-3564), 5940). It is mathematically correct, but practically buying negative shirt means selling and this is not what we are into. Enterig a shop with the idea to sell stuff is somehow out of the scope here.

3. The Infinite Solution Factory

This is where Haskell’s lazy evaluation shines. We know that solution to Diophantine equations appear at regular intervals. If (x0, y0) is a solution, then (x0+k(b/d), y0-k(a/d) is also a solution for any integer k. We define diophantine to generate an infinite list of all integer solutions.

The magic happens in ks. The list comprehension [[k, -k]|k<-[1..]] generates [[1,-1], [2,-2], [3,-3]...]We flatten this with concat and prepend 0, creating an infinite list of integers [0,  1, -1, 2, -2, 3, -3 ...] that spirals outward from zero:

4. Filtering for Real World Answers

Finally, to solve our shirt puzzle, we take this infinite stream and verify which pairs are valid in the real world (non-negative, as we want to buy shirts and not to sell them):

Haskell lazily checks the infinite list until if finds the valid range, returning exactly 7 solutions:

These are the only possible combinations of shirts you could have bought. The code is here – https://github.com/Vitosh/Haskell/blob/main/code/02_LDE.hs

Enjoy the code and enjoy the rest of your day! 🙂