Haskell is, probably, the best functional programming language. And Learn You a Haskell is, probably, the best way to dive in.

I learn Haskell for the purpose of being a better programmer. Here we will try to solve one small problem from the Learn You a Haskell book using Swift and functional approach.

Problem

List all right triangles that have integers for all sides and all sides equal to or smaller than 10 has a perimeter of 24?

Solution in Haskell

A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set-builder notation (set comprehension) as distinct from the use of map and filter functions. (Wikipedia)

Before we continue, please, read the Set Builder Notation article.

As you know, in functional programming we either describing a problem than writing a solution. Let’s describe our problem using Set Builder Notation taking into consideration that side b isn’t larger than the hypothenuse and that side a isn’t larger than side b:

S = {(a, b, c) | a ∈ ℕ ^ b ∈ ℕ ^ c ∈ ℕ, a ∈ [1..10] ^ b ∈ [1..a] ^ c ∈ [1..b], a^2 + b^2 = c^2, a + b + c = 24}
  • (a, b, c) - Output expression or output function. For us it’s just a tuple which contains triangles sides lengths.
  • a ∈ ℕ ^ b ∈ ℕ ^ c ∈ ℕ, a ∈ [1..10] ^ b ∈ [1..a] ^ c ∈ [1..b] - Input set. Builds [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] set from - natural numbers set. (for the sake of understanding it is written literally describing the text of the problem). a, b, c are Natural (Integer) numbers and are smaller then 10. There is no 0-sided triangle, obiviously.
  • a^2 + b^2 = c^2, a + b + c = 24 - Predicate. Satisfies when coma-separated parts return true. (and logic)

Lets do nothing, but translate it to Haskell, using List Comprehension syntax and we will have a ready solution.

ghci> let rightTriangles = [ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a+b+c == 24]
ghci> rightTriangles 
[(6,8,10)]

Solution in Swift

BTW, I remember that “equation system solution” exists, but we are trying to understand programming, not math ;)

Warm up

As we know, list comprehension consists of three main parts: Output expression, Input set, Predicate. Let’s imagine, that we need to create the list of even squares of Integers each of which is less then 100.

Set building notation solution:

S = { x*x | ∃n : x ∈ ℕ, x < 100, x = 2*n}

Haskell solution:

let xs = let xs = [x*x | x <- [1..100], even x]

Swift solution is pretty simple though

(1...100).map { $0*$0 }.filter { $0 % 2 == 0 }
  • $0*$0 is the Output function. map applies it to each element of the set.
  • (1...100) is our Input set
  • $0 % 2 == 0 is a predicate.

So, now, when we know all the basics, it’s a time to solve Triangles problem.

Solution

Solution should return the Array of all possible triangles, satysfing the problem conditions. Each triangle is represented with triple (in Haskel - triple is three element tuple)

Let’s build the set of existing triangles with sides lengths 1..10

let triangles = (1...10).map { a in
  (1...10).map { b in
    (1...10).map { c in
      // Output function returns (Int, Int, Int) tuple
      return (a, b, c)
    }
  }
}

print(triangles)
// Prints
> [[[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 1, 5), (1, 1, 6), (1, 1, 7), (1, 1, 8), (1, 1, 9), (1, 1, 10)], [(1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 2, 7), (1, 2, 8), (1, 2, 9), (1, 2, 10)], [(1, 3, 1), (1, 3, 2), (1, 3, 3), (1, 3, 4), (1, 3, 5),...

The result contains some extra brackets (which is correct), so we better rewrite it using flatMap:

let triangles = (1...10).flatMap { a in
  (1...10).flatMap { b in
    (1...10).flatMap { c in
      return (a, b, c)
    }
  }
}

print(triangles)
// Prints
> [(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 1, 5), (1, 1, 6), (1, 1, 7), (1, 1, 8), (1, 1, 9), (1, 1, 10), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 2, 7), (1, 2, 8), (1, 2, 9), (1, 2, 10), (1, 3, 1), (1, 3, 2), (1, 3, 3), (1, 3, 4), (1, 3, 5), (1, 3, 6),...

Output now is much better. We have the Array of (Int, Int, Int), or, another word, we built needed set of needed triangles. The only thing we should do is to add the Predicate.

let triangles = (1...10).flatMap { c in
  (1...c).flatMap { b in
    (1...b).flatMap { a in
      return (a, b, c)
    }
  }
}.filter { tr in
    let isRight = tr.0 * tr.0 + tr.1 * tr.1 == tr.2 * tr.2
    let pSatisfies = tr.0 + tr.1 + tr.2 == 24
    return isRight && pSatisfies
}
print(triangles)

// Output
> [(6, 8, 10)]

Conclusion

It looks weird. I made the simple problem complex, wrote some weird code which could be ten times simpler. But functional programming is not just a monad usage. Functional programming is the way, where math and coding go together. It is elegant and beautiful. This article was not a programming use case. It’s about to describe another approach on the simple example.

Where to go from here

Some Sequences and generators stuff will be good to recall. If you are not familiar with flatMap - read Map and FlatMap Demystified by Umberto Raimondi. And last but not least - Learn You a Haskell for Great Good

If you have any suggestions, found the mistake or just want to talk - @limlab_io. Thank you for reading!