First attempt of functional programming: Haskell

Starting my university life at Imperial College is a tricky decision to make, because not until I’ve arrived at my first lecture hall did I know that our first class was going to be Haskell programming.

I’ve been using many imperative language before, but none of them even looks like Haskell. I had started to accommodate myself to think functionally, but nevertheless have failed to do so. Some people praise the simplicity of functional programming and it’s resemblance to math equations, but others complain that it’s uselessly difficult. I found that it lies somewhere in between, only if you use it modularly in certain places.

We will talk about the following features of Haskell and functional programming:

• Every could be a function.
• Pattern matching
• Higher-order functions
• User defined data types and parsing
• Resemblance to math
• Stateless programming

Now, to give you a taste, everything in Haskell is a function.

When we try to compute 5 + 6, what we are really doing is regarding 5 as the first argument and 6 the second, and then put them into the function of addition. So, just like writing some function like function_name(arg1, arg2) in other imperative languages, we can write (+) 5 6 in Haskel to make things “functional”. Notice the bracket around the plus sign could be removed for simplicity.

Just as mentioned above, everything is a function, so is the construction of a list. In Haskell, there are two list operators :(list builder) and ++(list concatenation). A list [0, 1, 2] is really just 0:1:2:[]. The list builder here is really just a function that takes two arguments: the first argument is an element, and the second argument is a list(the rest of a list). The return value of this function is just a list. As said above, we can also write (:) 0 ((:) 1 ((:) 2 [])). The usage of ++ is similar.

The definition of Integer(not Int) is also functionally recursive. For instance, 0 is 0, 1 is Succ 0, 2 is Succ (Succ 0), 3 is Succ (Succ (Succ 0)), etc. This is an example of the application of Peano arithmetic in computer science. If you are concerned about how to store the chain of Succ in the memory, you can refer the Haskell documentation.

Now, the uniqueness of functional programming probably comes from pattern matching. In short, pattern matching is a nicer version of if-else statement. Because constructions of many things are functional(such as list), there are some things that can only be done in pattern matching and cannot be achieved using imperative if-else.

Here is an example of using pattern matching in a function:

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs

Here, [] means that if the argument of length function is an empty list, the function returns 0. If the input argument takes the form of (x:xs), the function returns 1 + the length of xs. Notice as said earlier, in (x:xs), x is the first element and the xs is the rest of the list. Many built-in functions in Haskell are defined in this way: using pattern matching combined with some sort of recursion.

Functional programming is best used for building for list process/operations using its higher order functions. There are plenty of built-in list operations, such as map, length, any, all, take, drop, filter, zipWith, fold, nub, head, tails, elem, insert, group, find. You can check the full list of operations in the Prelude and List package at Haskell reference.

We will try to show some of the implementations of list operations here:

--map is used to apply a function on every elements in a given list
map :: (a -> a) -> [a] -> [a]
map f []     = []
map f (x:xs) = (f x) : (map f xs)

—-any is used to check whether a list contains an element that satisfy the Boolean function
any :: (a -> Bool) -> [a] -> Bool
any f []     = False
any f (x:xs) = f x || any xs

—-elem is used to check whether a given element is in a list
elem :: a -> [a] -> Bool
elem i []     = False
elem i (x:xs) = (i == x) || elem i xs

—-filter is used to select the elements in a list that satisfy the predicate function
filter :: (a -> Bool) -> [a] -> [a]
filter f []     = []
filter f (x:xs)
  | f x = x : (filter f xs)
  | otherwise = filter f xs

--take is used to take the first n elements of a list. Pre: n <= list.length
take :: Int -> [a] -> [a]
take 0 _      = []
take n (x:xs) = x:(take (n - 1) xs)

There are many more functions that can be realized easily using recursion and functional features of Haskell. On the top of these, functional programming in general allows you to define datatypes that can be used in pattern matching. This aids the process of interpreting codes or parsing formatted files such as HTML/XML. For instance, you can defined a datatype like this:

type Name = String
type Attributes = [(String, String)]

data XML = Text String | Element Name Attributes [XML] 
deriving (Eq, Show)

Eq and Show just means that this datatype can be compared using equality(==) or inequality(/=). For more, visit Data.Eq documentation.

“Text String” represents the texts inside an XML tag, and attributes is a list of string pairs that represent attributes and their corresponding values that a tag possess. An “Element Name Attributes [XML]” represents a tag with a name and a list of attributes, as well as the XML tags that is behind this one.

In this way, we can using pattern matching to parse XML files into this data type. For instance, s1, s2, s3 is corresponding to x1, x2, x3 after parsing:

s1, s2, s3 :: String
s1
  = "<a>A</a>"
s2 
  = "<a x="1\"><b>A</b><b>B</b></a>"
s3
  = "<a>
      <b>
        <c att="att1">text1</c>
        <c att="att2">text2</c>
      </b>
      <b>
        <c att="att3">text3</c>
        <d>text4</d>
      </b>
    </a>"

x1, x2, x3 :: XML
x1
  = Element "a" [] [Text "A"]
x2
  = Element "a"
            [("x","1")]
            [Element "b" [] [Text "A"],
             Element "b" [] [Text "B"]]
x3
  = Element "a" 
            [] 
            [Element "b" 
                     [] 
                     [Element "c"
                              [("att","att1")] 
                              [Text "text1"],
                      Element "c" 
                              [("att","att2")]
                              [Text "text2"]],
             Element "b" 
                     [] 
                     [Element "c" 
                              [("att","att3")] 
                              [Text "text3"],
                      Element "d" 
                              [] 
                              [Text "text4"]]]

We can then conduct a series of operations easily on this parsed data. This is potentially useful in data manipulation, and Haskell can be used in the process of parsing.

Haskell and functional programming languages takes closer look to mathematical equations than any other imperative programming languages. When you try to compute factorials in Java, it looks like this:

public int fac(int n) {
    if (n == 0 || n == 1) return 1;
    return n * fac(n - 1);
}

In Haskell, it is as simple as this:

fac :: Int -> Int
fac 0 = 1
fac 1 = 1
fac n = n * fac (n - 1)

It is super clean and we do not need an if-else statement to cover the base case. This is one of the reasons that Haskell is much preferred by math people. When you try to realize complicate algorithms like merge sort, Haskell is way more clearer than other languages:

merge :: [Int] -> [Int] -> [Int]
-- Pre: both argument lists are ordered merge [] [] = []
merge [] (x : xs) = x : xs
merge (x : xs) [] = x : xs
merge (x : xs) (y : ys)
  | x < y     = x : merge xs (y:ys)
  | otherwise = y : merge (x : xs) ys

mergeSort :: [Int] -> [Int]
mergeSort [] = []
mergeSort xs = merge (mergeSort xs’) (mergeSort xs’’)
    where (xs’, xs’’) = splitAt (length xs ‘div‘ 2) xs

Haskell is stateless and does not retain data, which is a feature that most functional programming languages has. In imperative programming languages, executing lines of codes can potentially change the state of variables inside the main memory, thus we have to keep track of the state of program using Hoare’s Triple. In Haskell or other functional languages, we don’t have to do that: each line of code does not change the state of the program, and the data is merely used as input and then becomes output after the operations(there is no temporary intermediate data). The entire functional program is like a pipeline: the data is merely passengers through the pipes. This feature of Haskell makes it good at multithreading since we do not need to care about race condition.

There are other important features of Haskell as well, such as lazy evaluation, currying functions, lambda expression or anonymous functions, monads, etc. But those are beyond the realm of introduction. If you really want to be proficient in functional programming languages, I recommend you learn Haskell first.