Examples of Functions

Example: nand with pattern matching

Haskell functions are written in an equational style, and often use pattern matching to decide which equation to apply. For example, lets implement the nand function. nand stands for “not and” and is defined by the following truth table:

A	B	A nand B
False	False	True
True	False	True
False	True	True
True	True	False

Haskell lets us implement it like this:

nand :: Bool -> Bool -> Bool
nand False False = True
nand False True  = True
nand True  False = True
nand True  True  = False

This is pretty much a direct transcription of the nand truth table!

You can call nand using either prefix or infix style, whatever you prefer. Here’s prefix style:

> nand False True    -- prefix style
True
> nand True True
False

For infix style, back-quotes are required:

> True `nand` True     -- infix style
False
> True `nand` False
True
> False `nand` False

Example: Calculating 1 + 2 + 3 + … + n

Here are some different ways of calculating \(1 + 2 + 3 + \ldots + n\):

mysum1 :: Int -> Int
mysum1 n = sum [1..n]

[1..n] expands to the list [1,2,3,...,n], and the built-in function sum adds up all the numbers.

This version uses basic recursion:

mysum2 :: Int -> Int
mysum2 0 = 0                     -- base case
mysum2 n = n + (mysum2 (n - 1))  -- recursive case

A variation on this is to use guarded commands:

mysum3 :: Int -> Int
mysum3 n
      | n < 0     = error "n must be >= 0"
      | n == 0    = 0
      | otherwise = n + (mysum3 (n - 1))

Or you could use if-then-else:

mysum4 :: Int -> Int
mysum4 n = if n == 0 then 0 else n + (mysum4 (n - 1))

In general, pick the style that is easiest to read, and does not result in unnecessarily slow code.

Example: Length of a List

The built-in Haskell function length returns the length of a list.

Let’s write our own versions:

len1 :: [a] -> Int
len1 [] = 0
len1 x  = 1 + len1 (tail x)

The tail functions returns a list with its first element removed, e.g. tail [2, 6, 8] returns [6, 8].

Haskell has some special syntax for getting the head and tail elements of a list:

len2 :: [a] -> Int
len2 []           = 0
len2 (first:rest) = 1 + (len2 rest)

Instead of the names first and rest, Haskell functions often uses more generic names like x and xs:

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

We don’t actually use the variable x, so you can replace it with _:

len4 :: [a] -> Int
len4 []     = 0
len4 (_:xs) = 1 + (len4 xs)

You could also write it using guarded commands:

len5 :: [a] -> Int
len5 seq
     | null seq  = 0  -- null tests if a list is empty
     | otherwise = 1 + (len5 (tail seq))

Or using if-then-else:

len6 :: [a] -> Int
len6 seq = if null seq then 0 else 1 + (len6 (tail seq))

Example: RGB Color Functions

The following functions are provided as more examples for learning and understanding basic Haskell.

-- RGB Color Functions
--
-- An RGB triple is a 3-tuple (R, G, B), where R, G, and B are integers in the
-- range [0, 256).

in_range :: Int -> Bool
in_range x = 0 <= x && x < 256

is_rgb :: (Int, Int, Int) -> Bool
is_rgb (r, g, b) = (in_range r) && (in_range g) && (in_range b)

is_gray :: (Int, Int, Int) -> Bool
is_gray (r, g, b) = (r == g && g == b)

invert_rgb :: (Int, Int, Int) -> (Int, Int, Int)
invert_rgb (r, g, b) = (255 - r, 255 - g, 255 - b)

-- returns the brightness of an RGB triple
brightness :: (Int, Int, Int) -> Float
brightness (r, g, b) = ((fromIntegral r) + (fromIntegral g) + (fromIntegral b)) / 3.0

-- returns the distance between two RGB colors
dist :: (Int, Int, Int) -> (Int, Int, Int) -> Float
dist (r1,g1,b1) (r2,b2,g2) = let dr = fromIntegral (r1 - r2)
                                 dg = fromIntegral (g1 - g2)
                                 db = fromIntegral (b1 - b2)
                             in sqrt (dr^2 + db^2 + dg^2)

-- same as dist, but uses "where" instead of "let/in"
dist2 :: (Int, Int, Int) -> (Int, Int, Int) -> Float
dist2 (r1,g1,b1) (r2,b2,g2) = sqrt (dr^2 + db^2 + dg^2)
                              where dr = fromIntegral (r1 - r2)
                                    dg = fromIntegral (g1 - g2)
                                    db = fromIntegral (b1 - b2)

-- constraint lo hi x; uses guards instead of patterns
constrain :: Int -> Int -> Int -> Int
constrain lo hi x
            | x < lo    = lo
            | hi < x    = hi
            | otherwise = x

constrain_rgb :: (Int, Int, Int) -> (Int, Int, Int)
constrain_rgb (r, g, b) = (legal r, legal g, legal b)
                          where legal = constrain 0 255  -- local function defined
                                                         -- using currying

-- add two RGB colors, constraining any values greater than 255
simple_add :: (Int, Int, Int) -> (Int, Int, Int) -> (Int, Int, Int)
simple_add (r1,g1,b1) (r2,g2,b2) = constrain_rgb (r1+r2, g1+g2, b1+b2)

-- convert a string color name into an RGB triple
to_RGB :: String -> (Int, Int, Int)
to_RGB "red"   = (255,0,0)
to_RGB "green" = (0,255,0)
to_RGB "blue"  = (0,0,255)
to_RGB "white" = (255,255,255)
to_RGB "black" = (0,0,0)
to_RGB _       = error "unknown color"

-- convert an RGB triple into a string name
to_Str :: (Int, Int, Int) -> String
to_Str (255,0,0)     = "red"
to_Str (0,255,0)     = "green"
to_Str (0,0,255)     = "blue"
to_Str (255,255,255) = "white"
to_Str (0,0,0)       = "black"
to_Str _             = error "unknown RGB triple"

Example: Finding Primes

Lets write a couple of functions for finding prime numbers. They won’t be extremely efficient, but they are interesting examples of Haskell functions.

Recall that an integer \(n\) is prime if it’s greater than 1, and is evenly divisible only by 1 and itself. For example, 2 is the smallest prime (and the only even prime), and the next few primes are 3, 5, 7, 11, and 13. There are an infinite number of primes, and in general testing for primality is an important computational problem.

It’s not hard to see that if the smallest divisor (greater than 1) of \(n\) is \(n\) itself, then \(n\) must be prime. For example, the smallest divisor (greater than 1) of 101 is 101, so 101 is prime.

So here is a function that users guarded commands and returns the smallest divisor of a number:

smallest_divisor :: Integer -> Integer
smallest_divisor n
    | n < 0     = error "n must be >= 0"
    | n == 0    = 0
    | n == 1    = 1
    | otherwise = head (dropWhile (\x -> n `mod` x /= 0) [2..n])

The dropWhile function takes two parameters: a predicate function, and a list. Here we’ve passed it the lambda function (\x -> n `mod` x /= 0), which returns True just when x does not evenly divide n. The expression [2..n] returns the list [2, 3, ..., n-1, n], i.e. all possible divisors of n. The call to dropWhile “drops”, i.e. removes, all the elements from the start of the list that fail to satisfy the function. The first element of the list that is returned is thus the smallest divisor of n.

We can use smallest_divisor to write is_prime like this:

is_prime :: Integer -> Bool
is_prime n | n < 2     = False
           | otherwise = (smallest_divisor n) == n

A composite number is an integer greater than 1 that is not prime. So is_composite can be written like this:

is_composite :: Integer -> Bool
is_composite n | n <= 1     = False
               | otherwise  = not (is_prime n)

Combining is_prime with other standard functions lets us do some interesting calculations. For example, here’s how you can calculate a list of all the primes up to 100:

filter is_prime [2..100]

Or a list of all the composites up to 100:

filter is_composite [2..100]

filter pred lst returns a new list containing just the elements of lst that satisfy pred.

You could also write functions like these:

primes_less_than :: Integer -> [Integer]
primes_less_than n = filter is_prime [2..(n-1)]

composites_less_than :: Integer -> [Integer]
composites_less_than n = filter is_composite [2..(n-1)]

Another way to calculate the first 100 primes, or composites, is this:

take 100 (filter is_prime [2..])

take 100 (filter is_composite [2..])

The function take n lst returns a list that is the first n elements of list.

The expression [2..] is the infinite list [2,3,4,5,...]. Since Haskell uses lazy evaluation, it doesn’t generate the elements on [2..] until they are needed, and so in the expression take 100 (filter is_prime [2..]) only a finite portion of [2..] ends up getting evaluated.

Example: List Equality

The built-in function == tests if two lists are equal. Lets implement our own version:

equal :: Eq a => [a] -> [a] -> Bool
equal [] []         = True
equal [] _          = False
equal _  []         = False
equal (a:as) (b:bs) = if a == b then (equal as bs) else False

The Eq a => at the start of the type signature is important. Eq is a standard type class provided by Haskell which is defined like this (taken from here):

class  Eq a  where
    (==), (/=) :: a -> a -> Bool

    x /= y     =  not (x == y)   -- default implementation of "not equal"
    x == y     =  not (x /= y)   -- default implementation of "equal"

This defines a type class named Eq. It says that any type a that is an instance of Eq must implement both == (equals) and /= (not equals), each with the type signatures a -> a -> Bool.

In addition, Eq provides default implementations of == and /=. So, if a only implements ==, then \= will automatically be defined as not (x == y).

Eq does not say how == and /= are implemented for any particular type a: it just says that those functions must exist for a. You use instance to define specific functions for a type class. For example:

instance Eq Integer where
  x == y =  x `integerEq` y

This says that, for the type Integer, x == y is defined to be x `integerEq` y, where we assume integerEq is a low-level function that tests if two Integer values are the same.

We don’t need to define /= explicitly, because the /= from the Eq class will automatically be used whenever we call x \= y, i.e. x \= y evaluates to not (x == y), which evaluates to not (x `integerEq` y).

Eq is a basic and important type class, and so Haskell provides dozens of Eq instances for its basic types.

Pig Latin

Pig Latin is a silly language that kids sometimes use. To convert an English word to Pig Latin, you follow these two rules:

• Pig Latin Rule 1: If the word starts with a consonant, then move all the consonants from the start of the word to the end of the word. For example, the word “cat” becomes “atcay” in Pig Latin, and “strength” becomes “engthstray”.
• Pig Latin Rule 2: If the word starts with a vowel, add “ay” to the end of the word. For instance, “orange” becomes “orangeay” (pronounced “orange-ay”), “is” becomes “isay”, and “a” becomes “aay”.

To convert an entire sentence to Pig Latin, convert each word to Pig Latin. For example, “bring the candy at noon” becomes “ingbray ethay andycay atay oonnay”.

Let’s write a Haskell function called piggify that converts a string of English words into Pig Latin, e.g.:

> piggify "mary found the treasure"
"arymay oundfay ethay easuretray"

The type signature for piggify is:

piggify :: String -> String

Now lets think of the basic algorithm for piggify. This seems like a reasonable approach:

• Split the English string into words. The standard Haskell function words can do this:

  > words "in the box"
  ["in","the","box"]
  

• Convert each of the words on the list from the previous step to Pig Latin using the map function. map f lst applies the function f to every element of the list lst, returning the results in a new list.

  So, for example, the expression map piglatin ["in","the","box"] evaluates to the same thing as [piglatin "in", piglatin "the", piglatin "box"], which evaluates to ["inay","ethay","oxbay"].

  We haven’t written the piglatin function yet. So we’ll make a note that this function needs to be written, and implement it later.

• Finally, since piggify returns a string, we have to convert the list of strings from the previous step into a string of words. The standard Haskell function unwords can do this, e.g.:

  > unwords ["inay","ethay","oxbay"]
  "inay ethay oxbay"
  

These steps are enough to let us write the piggify function:

piggify :: String -> String
piggify s = unwords (map piglatin (words s))

The next task is to write the piglatin function, which converts a single English word to Pig Latin. Here is one implementation:

-- returns True if c is a vowel, and False otherwise
isVowel :: Char -> Bool
isVowel c = c `elem` "aeiouAEIOU"

piglatin :: String -> String
piglatin s | s == ""           = s
           | isVowel (head s)  = s ++ "ay"
           | otherwise         = (dropWhile isCons s) ++ (takeWhile isCons s)
                                 ++ "ay"
                               where isCons c = not (isVowel c)

The first two steps handle the cases of the empty string and words that start with vowels. For words that start with consonants:

• dropWhile isCons s returns the string that is the same as s but all leading consonants have been removed. Note that the function isCons c is a locally defined helper function that returns True if c is a consonant, and False otherwise.

  For example, dropWhile isCons "treasure" returns "easure".

• takeWhile isCons s returns all the leading consonants of s. For example, takeWhile isCons "treasure" returns the string "tr".

So, if s is the string "treasure", we get this:

(dropWhile isCons "treasure") ++ (takeWhile isCons "treasure") ++ "ay"

= "easure" ++ "tr" ++ "ay"

= "easuretray"

This way of writing code is som,etimes called top-down development. We first wrote piggify, and then after that we wrote piglatin. It is possible to go the other way as well, i.e. to use bottom-up development where we would write (and test) piglatin first, and then implement piggify.

Example: Sorting

Here’s a short implementation of quicksort:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (x:xs) = smalls ++ [x] ++ bigs
                   where smalls = quicksort [n | n <- xs, n <= x]
                         bigs   = quicksort [n | n <- xs, n > x]

The type signature starts with Ord a =>. Ord is a type class that guarantees that <= and > (and the other comparison functions) work for whatever type a is. Types like numbers, strings, and lists of number/strings all implement Ord, and so you can call quicksort on any of those. For example:

> quicksort [8, 9, -1, 5, 2]
[-1,2,5,8,9]

> quicksort "banana"
"aaabnn"

> quicksort ["up", "on", "yes", "no", "cow"]
["cow","no","on","up","yes"]

> quicksort [[5, 2], [2, 8, 7], [1,1,1], [4]]
[[1,1,1],[2,8,7],[4],[5,2]]

The expression [n | n <- xs, n <= x] is an example of a list comprehension, which is a notation inspired by set theory that combines mapping and filtering. The list comprehension [n | n <- xs, n <= x] evaluates to a list containing all the elements of xs that are less than, or equal to, x.

While the source code for quicksort is remarkably short and readable, it is very inefficient. For instance, the list comprehensions that partition xs return a copy of the data, whereas quicksort traditionally does partitioning in-place without making a copy. Also, appending lists with ++ is slow compared to in-place quicksort, and also makes copies. So this function doesn’t scale to longer lists the way that a traditional, in-place, quicksort implementation would in a language like Go or C++.

You can implement an efficient in-place quicksort, but it is much more complicated (e.g. see this version), and requires techniques beyond what we can cover in an introduction to Haskell.