First Haskell Published Program: Arithmetic Progression

I find Haskell a challenging language, one that let you express yourself in different ways as procedural or object oriented programming allows you to do it. I knew about it quite a few months ago, but I have never had the time to concentrate to develop any example using it. As I found in the Facebook challenge example, I considered was a good opportunity to create a program with the current knowledge of Haskell (minimal) and still learn a lot using what I take for granted in other languages (C++ or Objective C).

At first, it is really a change of paradigm to start thinking about functions instead of variables that you declare at the beginning and use them as the program executes. Here those do not exist in the same way, as it does for loops (while or for) and the list are fundamental for data manipulation, you will notice my tries to force the language to behave as a procedural language, which I am aware it is not the best practice, but for the first steps I consider it is ok.

The statement of the test is the following:

The first line contains an Integer N, which is the number of terms which will be provided as input.
This is followed by N consecutive Integers, with a space between each pair of integers. All of these are on one line, and they are in AP (other than the point where an integer is missing).

Sample Input
5
1 3 5 9 11

Sample Output
7

Explanation
You are provided with 5 integers. As you can can observe, they have been picked from a series, in which the starting term is 1 and the common difference is 2. The only abberration, i.e. the missing term (7), occurs between 5 and 9. This is the missing element which you need to find.

Constraints
3 <= N <= 2500 All integers in the series will lie in the range [-10^6,+10^6].

Initially, the allowed time frame lies under 45min, but it took me around 5 hours to figure out a solution, having considered that I learned how to read files, read form STD, write (all with monads); recursions, "where" clauses, list comprehension, pattern matching and a little refresh of arithmetic progressions :), if you are interested in the full solution, the code is here. Let's start explaining function by function:

main = do
--    zz <- readFile "input.txt"
    zz <- getLine
    let z = strToInt zz
--    print z
--    let inc = increment z
--    print inc
    let x = missing z
    print x 
--    writeFile "output.txt" $ show x

The main, as in many other languages, is going to be the starting execution point. The "do" keyword states that what comes next is going to have IO actions, as "getLine" does: retrieve all input from the STDIO, then "bind" whatever comes from it to the "variable" (which is not exactly a variable but a ¿function?). The "let" keyword allows to "transform" the "IO String" to a simple "String" and "Purify" the IO action to a more common argument that takes place into the "strToIn" function. Lastly, "z" becomes the input of the function "missing" which is in charge of finding the missing number in the progression.

strToInt :: String -> [Int]
strToInt = (map read) . tail . words

As a simple explanation, the function "strToInt" transforms an String into a list of Integers doing "Function Composition" (cascade of input - output function calls). First it takes the implicit argument and splits it into words, which will be determined by a space, then discards the first element of the list, because in the challenge the input has first the number of elements and then the full progression. Then the resulting list is going to be mapped to the function read and transform each element into an integer, simple and concise, right??

initial :: (Int, Int)
initial = (0, 1)

missing :: [Int] -> Int
missing [] = 0
missing ys = (head ys) + (snd val - 1) * (fst val)
        where 
            val = pairSum ys initial

Now, initial is just a simple macro that defines a tuple that works as a starting point of saying (difference, position). Missing is going to be recursive function over a list of integers that returns the missing value in the progression, which first checks, is this an empty list, then the value is 0, otherwise I will apply the general formula of progression once I know the (difference, position) tuple from pairSum using the initial macro.

pairSum :: [Int] -> (Int, Int) -> (Int, Int)
pairSum [] _ = (0, 0)
pairSum (x:[]) (u, v) = (u, v)
pairSum (x:y:ys) (u, v) = 
    if (u /= 0 && diff /= u)
    then
        if (v > 2)
        then
            (u, v + 1)
        else
            (diff, v)
    else
        pairSum (y:ys) (diff, v + 1)
    where
        diff = abs(x - y)

Here some cases take place. Are you an empty list, then return a tuple of 0's. If you only have a list of one element, then we are not looking anymore for any pair of values. Then, the list can be decomposed into three elements, the head (x), the next element (y) and the rest of the list (ys); with this we are going to verify that at least we calculate a difference (u /= 0) and that previous and next difference match in order to continue searching, when this case does not happen, we see if the position of the missing number (v) is not in the second position of the list, in order to return the tuple "(difference, missing element position)".

This approach allows the algorithm to loop the list just once, determine where the missing element is and then calculate it using the general formula; this would create a complexity of O(n-m) where n is the number of elements in the list and m the position of the missing element, with a worst case of O(n) and best of O(1) if the element is in the first position of the list.