Continue with Functional Programming: Haskell

This time I think we will deal a bit with Haskel, try to have a feel of it characteristics, which is functional in a mathematical sense.

We will go directly to function in Haskell. That's where we will spend most of the time with.

I assume that you know how to install haskell.

let's start our terminal and begin gchi where we can test Haskell with console.

gchi

GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Prelude>

There are many tutorials on Haskell on the web, and what we trying to do here is the get you to taste the unique style of Haskell by assuming that you used to code in imperative language such C++, Python, or Java before.

We define function like this:

triple x = 3 * x

triple is function name; x is parameter. Note that there is no parentheses. "=" sign is special here, which begin the definition of the function.

Let's try

triple 5
=> 15

Hakell does not change state. You cannot literally assign a value as the following:

x = 5
=> parse error on input ‘=’

Once it is assigned using let x = 5, you cannot change it to something else. Remember that this is the essence of functional programming.

x -> f(x)
x is passed into a function and return a value

But x itselt does not change. This has a serious implication, such that it can be used in theorem proving, but here we won't get into that.

Let's get a few more examples before we launch a hard one at the end. Here is another example using if and else statement.

operate x = if x `mod` 2 == 0 then x - 1 else x * 2

List comprehension

The definition of set such as:

S = { 3.x | x E N, x <= 20} is very useful in defining any set without having to explicitly write all the elements.

Here we can write the above expression by following Haskell code:

let s = [3*x | x <- [1..20]]
[3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60]

In console we use let to assign a variable. "|" is for telling the beginning of constraints and other conditions. we can have more than one conditions separated by ",".

We can even have a complicated expression such as this:

[[x, y, z, t, u, v] | x <- [1..10], y <- [1..10], z <- [1..10], t <- [1..10], u <- [1..10], v <- [1..10], y >= x, z >= y, t >= z, u >= t, v >= u, x + y + z + t + u + v <= 100, 5*x + 3*y + z - t - 3*u - 5*v <= 100 ] !! 500

[1,1,3,8,10,10]

If we realy need to

Let's get to a more seriously fun problem. Here is a problem in Framgia Magazine, Fragazine as it is called. The problem is like this:

At the bus station by Tet holiday, a Framgia developer meets a pretty girl. He wants to get to know her. To ask for her phone number, he needs to solve a hard quiz. Can you help our poor developer? Following is the conversation between them.

Girl: I have 1 sister and 2 brothers, and the product of 3 people's ages is 144. Boy: Too hard, I haven't figured it out. More hints, please. Girl: Sum of 3 people's ages is the number of license plate of the bus that I'm about to get on. Boy: I know which bus you're getting on. But I still can't solve it. Girl: My 2 brothers are twins. End of hint.

What are the ages of her sister and her 2 brothers?

First let make sure that we understand the problem clearly.

• The product of ages x * y * z = 144
• The sum of ages is x + y + z which is not unique, since the boy cannot figure out the exact solution.
• 2 of the ages are the same.

Here is my first implementation using Ruby. But I will leave you to read the code by yourself. If you have any questions, please comment.

def update_count(p_solution, sum, new_arr)
  count = 1
  p_solution.each do |val_arr|
    if val_arr[1] == sum
      val_arr[2] = val_arr[2] + 1
      count = val_arr[2]
    end
  end
  p_solution << [new_arr, sum, count]
end

def find_solution(n)
  divider = []
  possible_solution = []
  three_somes = []
  solution = []

  for i in (1..Math.sqrt(n))
    divider << i if n % i == 0
  end

  divider.each do |val1|
    divider.each do |val2|
      mult = val1 * val2
      next unless n % mult == 0
      val3 = n/mult
      sum = val1 + val2 + val3
      new_arr = [val1, val2, val3].sort!
      unless three_somes.include?(new_arr)
        three_somes << new_arr
        update_count(possible_solution, sum, new_arr)
      end
    end
  end

  possible_solution.each do |ps|
    if ps[0][0] == ps[0][1] && ps[2] > 1
      solution << ps
    end
  end

  solution && solution[0] ? solution[0][0] : []
end

p find_solution(144)
[4, 4, 9]

Now let implement this using Haskell instead. The thinking process is quite different. I like to think that Haskell is more mathematically oriented. We write function in a way that define function in Mathematics.

import Data.List

brother :: Int -> [[Int]]
brother n = [[x, y, z] |
  x <- [1..n],
  y <- [1..n],
  z <- [1..n],
  y >= x,
  z >= y,
  x * y * z == n]

group :: (Eq a) => [a] -> [[a]]
group = foldr f []
  where
    f x [] = [[x]]
    f x (y:xs) = if x == (head y) then ((x:y):xs) else ([x]:y:xs)

findDuplicates :: [Int] -> [Int]
findDuplicates xs = [head x | x <- group (sort xs), length x > 1]

possible_solutions = brother 144
sum_arr = map (sum $) possible_solutions
duplicates = findDuplicates sum_arr

solution = [x | x <- possible_solutions, (sum x) `elem` duplicates, length (findDuplicates x) >= 1]

OK, Let's go over step by step. we define function brother. brother :: Int -> [[Int]]

• brother is a function name
• :: is to tell we begin define type. Except for the last type, all other types are for arguments passed to functions. Here it accepts Int (Integer) and return array of array of type Int. The following lines defines constraints of each parameters and logic of the function.

brother n = [[x, y, z] |
  x <- [1..n],
  y <- [1..n],
  z <- [1..n],
  y >= x,
  z >= y,
  x * y * z == n]

It will return array of array of 3 integers x, y, z. all x, y, z are between 1 and n, of course. and to avoid duplication of the same combination, we set x <= y <= z, and the main condition is x * y * z == n (144 in our problem).

Next we unnecessarily define function group which we can easily use a existing function group in Library Data.List. but we try to see how function works here. The first line is type of function and arguments with type class (Eq). Type class in Haskell is something like Interface in Java and more, so that we can use common function such as "==".

group :: (Eq a) => [a] -> [[a]]
group = foldr f []
  where
    f x [] = [[x]]
    f x (y:xs) = if x == (head y) then ((x:y):xs) else ([x]:y:xs)

foldr is called right fold which accumlate on the right side. we start to apply on the array from the right-most element. we apply the function on each element by comparing if each element on the right to its left. If it is not equal that element x form an array of itself, other it form an array (x:y).

The last function is function to find duplicated element.

findDuplicates :: [Int] -> [Int]
findDuplicates xs = [head x | x <- group (sort xs), length x > 1]

Types are from array of integer to array of integers. First we sort array in the decending order, so that equal elements will be close to each other. Then we group same elements to a group.

Last step we filter out array brother which each array element has the same sum as other element and 2 elements of the inner array are equal.

solution = [x | x <- possible_solutions, (sum x) `elem` duplicates, length (findDuplicates x) >= 1

I still think this is not yet the best implementation for the problem, but it serves the purpose of our essay justly.

I hope you enjoy it. Welcome for any comments and questions.