Examples of Functions

Note

This is a literate Haskell page: you can load it directly into ghci by following these steps.

Example: nand with pattern matching

Haskell functions are written in an equational style, and use simple pattern matching to decide which equation to apply. As an example of this, 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 very directly:

> 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:

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

For infix style, wrap it in back-quotes:

Main> True `nand` True     -- infix style
False
Main> True `nand` False
True
Main> 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, try to pick a 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
                                                         -- thanks to 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 how to write 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 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 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.

Now it’s easy to write is_prime:

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

And is_composite:

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

A composite number is an integer greater than 1 that is not prime.

Suppose you want 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 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, but it’s instructive to 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), both with the type signatures a -> a -> Bool.

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

A type class does not say how == and /= work 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.

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]

Notice that 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]]

Notice the expression [n | n <- xs, n <= x]. This is an example of a list comprehension, which is a notation inspired by set theory. 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 this partitioning in-place without making a copy. Also, appending lists with ++ is relatively slow compared to the usual quicksort partitioning. So this function doesn’t scale to longer lists the way that a more traditional, in-place, quicksort implementation would in a language like Go or C++.

You can implement an efficient in-place quicksort (search for “efficient haskell quicksort” on the web), but it is much more complicated, and requires techniques beyond what we can cover in an introduction to Haskell.

Example: Testing with QuickCheck

QuickCheck is a useful way to automatically test some kinds of functions. QuickCheck does property testing, i.e. it tests if some property of a function is true.

To see what this means, here are a few examples of properties for quicksort:

• quicksort (quicksort lst) == quicksort lst, for any list lst; this says quicksort is idempotent
• quicksort (reverse lst) == quicksort lst, for any list lst
• quicksort [1..n] == [1..n], for any integer n greater than 0
• length lst == length (quicksort lst), for any list lst

By implementing each of these properties as Haskell functions that start with prop_, QuickCheck can automatically generate and run lots of random tests:

-- quicksort_testing.hs

--
-- To use QuickCheck, you need to install it. The easiest way to do this is
-- to use the cabal package manager:
--
--   $ cabal update
--   $ cabal install QuickCheck
--
--
-- To run all tests, type runTests in the interpreter:
--
-- > runTests
--
-- Some useful references for quickCheck:
--  - http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html
--  - https://begriffs.com/posts/2017-01-14-design-use-quickcheck.html
--

import Test.QuickCheck

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]

-- sorting is idempotent
--
-- in general, a function f is idempotent if f (f x) = f x for all x, i.e.
-- applying f twice gives the same result as applying it once
prop_qs1 :: [Int] -> Bool
prop_qs1 lst = quicksort (quicksort lst) == quicksort lst

-- sorting a list, or its reverse, returns the same result
prop_qs2 :: [Int] -> Bool
prop_qs2 lst = quicksort lst == quicksort (reverse lst)

-- sorting [1,2,..n] returns the same list
prop_qs3 :: Int -> Bool
prop_qs3 n = quicksort [1..n] == [1..n]

-- sorting doesn't change the length of a list
prop_qs4 :: [Int] -> Bool
prop_qs4 lst = length lst == length (quicksort lst)

-- this is  a do environment --- the way that Haskell lets you perform actions
-- in sequence
runTests = do
  quickCheck prop_qs1
  quickCheck prop_qs2
  quickCheck prop_qs3
  quickCheck prop_qs4

Type runTests do the testing, e.g.:

> runTests
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.

quickCheck generates 100 random inputs for each prop_ function and verifies that the property is true for each input. Of course, this does not guarantee quicksort is bug-free, but in practice random testing often does a good job of catching bugs in small functions. Plus, many programmers find property tests more interesting to create than low-level (input, output) pairs.

Lets see what happens when QuickCheck finds a bug. Consider this function:

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

The bug is in the equation for smalls: n < x is written, when it is meant to be n <= x. Here’s what testing does:

> runTests
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
*** Failed! Falsifiable (after 10 tests and 4 shrinks):
[4,4]

Notice that the first 4 properties don’t catch the bug — QuickCheck can’t guarantee to catch all problems! It’s prop_qs4 that catches the error, i.e. prop_qs4 notices that the list output by quicksortBuggy is not always the same length as the input list.

QuickTest reports that the list [4,4] violates prop_qs4. Trying this with quicksortBuggy shows that it indeed returns the wrong result:

> quicksortBuggy [4,4]
[4]

Notice that QuickCheck said it did “4 shrinks” to get [4,4]. It turns out that humans often find randomly generated data quite messy and hard to read, and so QuickCheck uses various heuristics to “shrink” a failing test case into one that is smaller and simpler. While there is no guarantee how well these heuristics will work, in practice they often do a good job of finding small and simple tests cases that can then be used to help debug the function.

The idea of testing using properties has proven to be quite popular with some programmers, and so you can find many QuickCheck-like tools in other languages. For example, in Python the Hypothesis package offers quickcheck-like testing for Python code.

QuickCheck Example: last item of a list

Let’s use QuickCheck to test a function called mylast that is supposed to work the same as the standard last function (which returns the last element of a list):

mylast :: [a] -> a
mylast []     = error "empty list"
mylast [x]    = x
mylast (_:xs) = mylast xs

-- mylast :: [a] -> a
-- mylast []  = error "empty list"
-- mylast lst = head (drop (n-1) lst)
--              where n = length lst

-- mylast :: [a] -> a
-- mylast []  = error "empty list"
-- mylast lst = head (reverse lst)

We’ve provided a couple of alternate implementations in case you want to test those as well.

First, you need to think of some properties that mylast has. This takes some thinking, and you get better at it with practice. Here are three properties that hold for all non-empty lists a and b:

- ``last (a ++ b) == last b``

• last (reverse a) == head a
• last [a] == a

Looking at our implementation of mylast, the third property (last [a] == a) doesn’t seem like it will be very useful to create test cases for because the second equation in mylast explicitly handles that case, so we can be pretty sure it always holds.

You might try writing the first property like this:

prop_mylast1_bad :: [Int] -> [Int] -> Bool
prop_mylast1_bad a b = mylast (a ++ b) == mylast b

But when you run it you get a failure very quickly:

> quickCheck prop_mylast1_bad
*** Failed! (after 1 test):
Exception:
  empty list
[]
[]

The problem is that prop_mylast1_bad generates any list of Int values, including the empty list []. But our properties only hold for non-empty lists.

There are two ways that you could fix this. The first is to re-write the test using the conditional operator ==>:

prop_mylast1 :: [Int] -> [Int] -> Property
prop_mylast1 a b = a /= [] && b /= [] ==> mylast (a ++ b) == mylast b

This test only checks if the property holds if both a and b are non-empty. Also notice the return type of the test is now Property instead of Bool. Here’s a sample run:

> quickCheck prop_mylast1
+++ OK, passed 100 tests; 16 discarded.

16 of the randomly generated tests were discarded because they include either a or b equal to the empty lists. So be careful when using ==>: if your condition is very restrictive you may not end up doing many tests.

A second approach to writing this test is to use the special type NonEmptyList a provided by QuickCheck:

prop_mylast1b :: NonEmptyList Int -> NonEmptyList Int -> Bool
prop_mylast1b (NonEmpty a) (NonEmpty b) = mylast (a ++ b) == mylast b

This causes the random lists generated by QuickCheck to always have at least one element. Note that the return type is back to Bool again.

Here are all the tests, plus a helper function to run them all:

prop_mylast1 :: [Int] -> [Int] -> Property
prop_mylast1 a b = a /= [] && b /= [] ==> mylast (a ++ b) == mylast b

prop_mylast1b :: NonEmptyList Int -> NonEmptyList Int -> Bool
prop_mylast1b (NonEmpty a) (NonEmpty b) = mylast (a ++ b) == mylast b

prop_mylast2 :: [Int] -> Property
prop_mylast2 a = a /= [] ==> mylast (reverse a) == head a

prop_mylast2b :: NonEmptyList Int -> Bool
prop_mylast2b (NonEmpty a) = mylast (reverse a) == head a

run_mylastTests = do
    quickCheck prop_mylast1
    quickCheck prop_mylast1b
    quickCheck prop_mylast2
    quickCheck prop_mylast2b

Here’s a sample run:

> run_mylastTests
+++ OK, passed 100 tests; 22 discarded.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests; 14 discarded.
+++ OK, passed 100 tests.