Functional Programming

26 minute read

Functional Programming

Now with lists and polymorphism in our toolbox, we can finally start to look at functional programming.

In Haskell a function is a value, just like a number or a list is. Functions can be passed as parameters to other functions. Here’s a toy example. The function applyTo1 takes a function of type Int->Int, applies it to the number 1, and returns the result.

applyTo1 :: (Int -> Int) -> Int
applyTo1 f = f 1

Let’s define a simple function of type Int->Int and see applyTo1 in action.

addThree :: Int -> Int
addThree x = x + 3

applyTo1 addThree
  ==> addThree 1
  ==> 1 + 3
  ==> 4

Let’s go back to the type annotation for applyTo1.

applyTo1 :: (Int -> Int) -> Int

The parentheses are needed because the type Int -> Int -> Int would be the type of a function taking two Int arguments. More on this later.

Let’s look at a slightly more interesting example. This time we’ll implement a polymorphic function doTwice. Note how we can use it with various types of values and functions.

doTwice :: (a -> a) -> a -> a
doTwice f x = f (f x)

doTwice addThree 1
  ==> addThree (addThree 1)
  ==> 7
doTwice tail "abcd"
  ==> tail (tail "abcd")
  ==> "cd"

makeCool :: String -> String
makeCool str = "WOW " ++ str ++ "!"

doTwice makeCool "Haskell"
  ==> "WOW WOW Haskell!!"

Functional Programming on Lists

That was a bit boring. Luckily there are many useful list functions that take functions as arguments. By the way, functions that take functions as arguments (or return functions) are often called higher-order functions.

The most famous of these list-processing higher-order functions is map. It gives you a new list by applying the given function to all elements of a list.

map :: (a -> b) -> [a] -> [b]

map addThree [1,2,3]
  ==> [4,5,6]

The partner in crime for map is filter. Instead of transforming all elements of a list, filter drops some elements of a list and keeps others. In other words, filter selects the elements from a list that fulfill a condition.

filter :: (a -> Bool) -> [a] -> [a]

Here’s an example: selecting the positive elements from a list

positive :: Int -> Bool
positive x = x>0

filter positive [0,1,-1,3,-3]
  ==> [1,3]

Note how both the type signatures of map and filter use polymorphism. They work on all kinds of lists. The type of map even uses two type parameters! Here are some examples of type inference using map and filter.

onlyPositive xs = filter positive xs
mapBooleans f = map f [False,True]

Prelude> :t onlyPositive
onlyPositive :: [Int] -> [Int]
Prelude> :t mapBooleans
mapBooleans :: (Bool -> b) -> [b]
Prelude> :t mapBooleans not
mapBooleans not :: [Bool]

One more thing: remember how constructors were just functions? That means you can pass them as arguments to other functions!

wrapJust xs = map Just xs

Prelude> :t wrapJust
wrapJust :: [a] -> [Maybe a]
Prelude> wrapJust [1,2,3]
[Just 1,Just 2,Just 3]

Examples of Functional Programming on Lists

How many “palindrome numbers” are between 1 and n?

-- a predicate that checks if a string is a palindrome
palindrome :: String -> Bool
palindrome str = str == reverse str

-- palindromes n takes all numbers from 1 to n, converts
-- them to strings using show, and keeps only palindromes
palindromes :: Int -> [String]
palindromes n = filter palindrome (map show [1..n])

palindrome "1331" ==> True
palindromes 150 ==>
  ["1","2","3","4","5","6","7","8","9",
   "11","22","33","44","55","66","77","88","99",
   "101","111","121","131","141"]
length (palindromes 9999) ==> 198

How many words in a string start with “a”? This uses the function words from the module Data.List that splits a string into words.

countAWords :: String -> Int
countAWords str = length (filter startsWithA (words str))
  where startsWithA s = head s == 'a'

countAWords "does anyone want an apple?"
  ==> 3

The function tails from Data.List returns the list of all suffixes (“tails”) of a list. We can use tails for many string processing tasks. Here’s how tails works:

tails "echo"
  ==> ["echo","cho","ho","o",""]

Here’s an example where we find what characters come after a given character in a string. First of all, we use tails, map and take to get all substrings of a certain length:

substringsOfLength :: Int -> String -> [String]
substringsOfLength n string = map shorten (tails string)
  where shorten s = take n s

substringsOfLength 3 "hello"
  ==> ["hel","ell","llo","lo","o",""]

There’s some shorter substrings left at the end (can you see why?), but they’re fine for our purposes right now. Now that we have substringsOfLength, we can implement the function whatFollows c k s that finds all the occurrences of the character c in the string s, and outputs the k letters that come after these occurrences.

whatFollows :: Char -> Int -> String -> [String]
whatFollows c k string =
  map tail (filter match (substringsOfLength (k+1) string))
  where match sub = take 1 sub == [c]

whatFollows 'a' 2 "abracadabra"
  ==> ["br","ca","da","br",""]

Partial Application

When using higher-order functions you can find yourself defining lots of small helper functions, like addThree or shorten in the previous examples. This is a bit of a chore in the long run, but luckily Haskell’s functions behave a bit weirdly…

Let’s start in GHCi:

Prelude> let add a b = a+b
Prelude> add 1 5
6
Prelude> let addThree = add 3
Prelude> addThree 2
5

So, we’ve defined add, a function of two arguments, and only given it one argument. The result is not a type error but a new function. The new function just stores (or remembers) the given argument, waits for another argument, and then gives both to add.

Prelude> map addThree [1,2,3]
[4,5,6]
Prelude> map (add 3) [1,2,3]
[4,5,6]

Here we can see that we don’t even need to give a name to the function returned by add 3. We can just use it anywhere where a function of one argument is expected.

This is called partial application. All functions in Haskell behave like this. Let’s have a closer look. Here’s a function that takes many arguments.

between :: Integer -> Integer -> Integer -> Bool
between lo high x = x < high && x > lo

Prelude> between 3 7 5
True
Prelude> between 3 6 8
False

We can give between less arguments and get back new functions, just like we saw with add:

Prelude> (between 1 5) 2
True
Prelude> let f = between 1 5 in f 2
True
Prelude> map (between 1 3) [1,2,3]
[False,True,False]

Look at the types of partially applying between. They behave neatly, with arguments disappearing one by one from the type as values are added to the expression.

Prelude> :t between
between :: Integer -> Integer -> Integer -> Bool
Prelude> :t between 1
between 1 :: Integer -> Integer -> Bool
Prelude> :t between 1 2
between 1 2 :: Integer -> Bool
Prelude> :t between 1 2 3
between 1 2 3 :: Bool

Actually, when we write a type like Integer -> Integer -> Integer -> Bool, it means Integer -> (Integer -> (Integer -> Bool)). That is, a multi-argument function is just a function that returns a function. Similarly, an expression like between 1 2 3 is the same as ((between 1) 2) 3, so passing multiple arguments to a function happens via multiple single-argument calls. Representing multi-argument functions like this is called currying (after the logician Haskell Curry). Currying is what makes partial application possible.

Here’s another example of using partial application with map:

map (drop 1) ["Hello","World!"]
  ==> ["ello","orld!"]

In addition to normal functions, partial application also works with operators. With operators you can choose whether you apply the left or the right argument. (Partially applied operators are also called sections or operator sections). Some examples:

Prelude> map (*2) [1,2,3]
[2,4,6]
Prelude> map (2*) [1,2,3]
[2,4,6]
Prelude> map (1/) [1,2,3,4,5]
[1.0,0.5,0.3333333333333333,0.25,0.2]

Prefix and Infix Notations

Normal Haskell operators are applied with prefix notation, which is just a fancy way to say that the function name comes before the arguments. In contrast, operators are applied with infix notation – the name of the function comes between the arguments.

An infix operator can be converted into a prefix function by adding parentheses around it. For instance,

(+) 1 2 ==> 1 + 2 ==> 3

This is useful especially when an operator needs to be passed as an argument to another function.

As an example, the function zipWith takes two lists, a binary function, and joins the lists using the function. We can use zipWith (+) to sum two lists, element-by-element:

Prelude> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude> zipWith (+) [0,2,5] [1,3,3]
[1,5,8]

Without the ability to turn an operator into a function, we’d have to use a helper function – such as add above.

Note that omitting the parentheses leads into a type error:

Prelude> zipWith + [0,2,5,3] [1,3,3]

<interactive>:1:11: error:
  • Couldn't match expected type
      ‘[Integer] -> (a -> b -> c) -> [a] -> [b] -> [c]’
                with actual type ‘[Integer]’
  • The function ‘[0, 2, 5, 3]’ is applied to one argument,
    but its type ‘[Integer]’ has none
    In the second argument of ‘(+)’,
      namely ‘[0, 2, 5, 3] [1, 3, 3]’
    In the expression: zipWith + [0, 2, 5, 3] [1, 3, 3]
  • Relevant bindings include
      it :: (a -> b -> c) -> [a] -> [b] -> [c]
        (bound at <interactive>:1:1)

The reason for this weird-looking error is that GHCi got confused and thought that we were somehow trying to add zipWith and [0,2,5,3] [1,3,3] together. Logically, it deduced that [0,2,5,3] must be a function since it’s being applied to [1,3,3] (remember that functions bind tighter than operators).

Unfortunately, error messages can sometimes be obscure, since the compiler cannot always know the “real” cause of the error (which is in this case was omitting the parentheses). Weird error messages are frustrating, but only the programmer knows what was the original intent behind the code.

Another nice feature of Haskell is the syntax for applying a binary function as if it was an infix operator, by surrounding it with backticks (`). For example:

6 `div` 2 ==> div 6 2 ==> 3
(+1) `map` [1,2,3] ==> map (+1) [1,2,3] ==> [2,3,4]

Lambdas

The last spanner we need in our functional programming toolbox is λ (lambda). Lambda expressions are anonymous functions. Consider a situation where you need a function only once, for example in an expression like

let big x = x>7 in filter big [1,10,100]

A lambda expression allows us to write this directly, without defining a name (big) for the helper function:

filter (\x -> x>7) [1,10,100]

Here are some more examples in GHCi:

Prelude> (\x -> x*x) 3
9
Prelude> (\x -> reverse x == x) "ABBA"
True
Prelude> filter (\x -> reverse x == x) ["ABBA","ACDC","otto","lothar","anna"]
["ABBA","otto","anna"]
Prelude> (\x y -> x^2+y^2) 2 3           -- multiple arguments
13

The Haskell syntax for lambdas is a bit surprising. The backslash character (\) stands for the greek letter lambda (λ). The Haskell expression \x -> x+1 is trying to mimic the mathematical notation λx. x+1. Other languages use syntax like x => x+1 (JavaScript) or lambda x: x+1 (Python).

Note! You never need to use a lambda expression. You can always instead define the function normally using let or where.

By the way, lambda expressions are quite powerful constructs which have a deep theory of their own, known as Lambda calculus. Some even consider purely functional programming languages such as Haskell to be typed extensions of Lambda calculus with extra syntax.

Sidenote: The `.` and `$` Operators

The two most common operators in Haskell codebases are probably . and $. They are useful when writing code that uses higher-order functions. The first of these, the . operator, is the function composition operator. Here’s its type

(.) :: (b -> c) -> (a -> b) -> a -> c

And here’s what it does

(f.g) x ==> f (g x)

You can use function composition to build functions out of other functions, without mentioning any arguments. For example:

double x = 2*x
quadruple = double . double  -- computes 2*(2*x) == 4*x
f = quadruple . (+1)         -- computes 4*(x+1)
g = (+1) . quadruple         -- computes 4*x+1
third = head . tail . tail   -- fetches the third element
                             --   of a list

We can also reimplement doTwice using (.). Note how we can use doTwice both as applied only to a function, or as applied to a function and a value.

doTwice :: (a -> a) -> a -> a
doTwice f = f . f

let ttail = doTwice tail
in ttail [1,2,3,4]
  ==> [3,4]

(doTwice tail) [1,2,3,4] ==> [3,4]

doTwice tail [1,2,3,4] ==> [3,4]

Often function composition is not used when defining a new function, but instead to avoid defining a helper function. For instance, consider the difference between these two expressions:

let notEmpty x = not (null x)
in filter notEmpty [[1,2,3],[],[4]]
  ==> [[1,2,3],[4]]

filter (not . null) [[1,2,3],[],[4]]
  ==> [[1,2,3],[4]]

The other operator, $ is more subtle. Let’s look at its type.

($) :: (a -> b) -> a -> b

It takes a function of type a -> b and a value of type a, and returns a value of type b. In other words, it’s a function application operator. The expression f $ x is the same as f x. This seems pretty useless, but it means that the $ operator can be used to eliminate parentheses! These expressions are the same:

head (reverse "abcd")
head $ reverse "abcd"

This isn’t that impressive when it’s used to eliminate one pair of parentheses, but together . and $ can eliminate lots of them! For example, we can rewrite

reverse (map head (map reverse (["Haskell","pro"] ++ ["dodo","lyric"])))

(reverse . map head . map reverse) (["Haskell","pro"] ++ ["dodo","lyric"])

and then

reverse . map head . map reverse $ ["Haskell","pro"] ++ ["dodo","lyric"]

Sometimes the operators . and $ are useful as functions in their own right. For example, a list of functions can be applied to an argument using map and a section of $:

map ($"string") [reverse, take 2, drop 2]
  ==> [reverse $ "string", take 2 $ "string",
       drop 2 $ "string"]
  ==> [reverse "string", take 2 "string", drop 2 "string"]
  ==> ["gnirts", "st", "ring"]

If this seems complicated, don’t worry. You don’t need to use . and $ in your own code until you’re comfortable with them. However, you’ll bump into . and $ when reading Haskell examples and code on the internet, so it’s good to know about them. This article might also help.

Example: Rewriting `whatFollows`

Now, let’s rewrite the whatFollows example from earlier using the tools we just saw. Here’s the original version:

substringsOfLength :: Int -> String -> [String]
substringsOfLength n str = map shorten (tails str)
  where shorten s = take n s

whatFollows :: Char -> Int -> String -> [String]
whatFollows c k str =
  map tail (filter match (substringsOfLength (k+1) str))
  where match sub = take 1 sub == [c]

To get started, let’s get rid of the helper function substringsOfLength and move all the code to whatFollows:

whatFollows c k str =
  map tail (filter match (map shorten (tails str)))
  where shorten s = take (k+1) s
        match sub = take 1 sub == [c]

Now let’s use partial application instead of defining shorten:

whatFollows c k str =
  map tail (filter match (map (take (k+1)) (tails str)))
  where match sub = take 1 sub == [c]

Let’s use . and $ to eliminate some of those parentheses:

whatFollows c k str =
  map tail . filter match . map (take (k+1)) $ tails str
  where match sub = take 1 sub == [c]

We can also replace match with a lambda:

whatFollows c k string =
  map tail . filter (\sub -> take 1 sub == [c])
           . map (take (k+1)) $ tails string

Finally, we don’t need to mention the string parameter at all, since we can just express whatFollows as a composition of map, filter, map and tails:

whatFollows c k =
  map tail . filter (\sub -> take 1 sub == [c])
           . map (take (k+1))
           . tails

We can even go a bit further by rewriting the lambda using an operator section

    \sub -> take 1 sub == [c]
=== \sub -> (==[c]) (take 1 sub)
=== \sub -> (==[c]) ((take 1) sub)
=== \sub -> ((==[c]) . (take 1)) sub
=== ((==[c]) . (take 1))
=== ((==[c]) . take 1)

Now what we have left is:

whatFollows c k = map tail . filter ((==[c]) . take 1)
                           . map (take (k+1))
                           . tails

This is a somewhat extreme version of the function, but when used in moderation the techniques shown here can make code easier to read.

More Functional List Wrangling Examples

Here are some more examples of functional programming with lists. Let’s start by introducing a couple of new list functions:

-- take elements from a list as long as they satisfy
-- a predicate
takeWhile :: (a -> Bool) -> [a] -> [a]

-- drop elements from a list as long as they satisfy
-- a predicate
dropWhile :: (a -> Bool) -> [a] -> [a]

takeWhile even [2,4,1,2,3]   ==> [2,4]
dropWhile even [2,4,1,2,3]   ==> [1,2,3]

There’s also the function elem, which can be used to check if a list contains an element:

elem 3 [1,2,3]   ==> True
elem 4 [1,2,3]   ==> False

Using these, we can implement a function findSubstring that finds the earliest and longest substring in a string that consist only of the given characters.

findSubstring :: String -> String -> String
findSubstring chars = takeWhile (\x -> elem x chars)
                      . dropWhile (\x -> not $ elem x chars)

findSubstring "a" "bbaabaaaab"              ==> "aa"
findSubstring "abcd" "xxxyyyzabaaxxabcd"    ==> "abaa"

The function zipWith lets you combine two lists element-by-element:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith (++) ["John","Mary"] ["Smith","Cooper"]
  ==> ["JohnSmith","MaryCooper"]
zipWith take [4,3] ["Hello","Warden"]
  ==> ["Hell","War"]

Sometimes with higher-order functions it’s useful to have a function that does nothing. The function id :: a -> a is the identity function and just returns its argument.

id 3 ==> 3
map id [1,2,3] ==> [1,2,3]

This seems a bit useless, but you can use it for example with filter or dropWhile:

filter id [True,False,True,True]
  ==>  [True,True,True]

dropWhile id [True,True,False,True,False]
  ==>  [False,True,False]

Another very simple but sometimes crucial function is the constant function, const :: a -> b -> a. It always returns its first argument:

const 3 True ==> 3
const 3 0    ==> 3

When partially applied it can be used when you need a function that always returns the same value:

map (const 5) [1,2,3,4]
  ==> [5,5,5,5]

filter (const True) [1,2,3,4]
  ==> [1,2,3,4]

Lists and Recursion

Here’s a new operator, :

Prelude> 1:[]
[1]
Prelude> 1:[2,3]
[1,2,3]
Prelude> tail (1:[2,3])
[2,3]
Prelude> head (1:[2,3])
1
Prelude> :t (:)
(:) :: a -> [a] -> [a]

The : operator builds a list out of a head and a tail. In other words, x : xs is the same as [x] ++ xs. Why do we need an operator for this?

Actually, : is the constructor for lists: it returns a new linked list node. The other list constructor is [], the empty list. All lists are built using : and []. The familiar [x,y,z] syntax is actually just a nicer way to write x:y:z:[], or even more explicitly, x:(y:(z:[])). In fact (++) is defined in terms of : and recursion in the standard library.

Here’s a picture of how [1,2,3] is structured in memory:

Building a List

Using : we can define recursive functions that build lists. For example here’s a function that builds lists like [3,2,1]:

descend 0 = []
descend n = n : descend (n-1)

descend 4 ==> [4,3,2,1]

Here’s a function that builds a list by iterating a function n times:

iterate f 0 x = [x]
iterate f n x = x : iterate f (n-1) (f x)

iterate (*2) 4 3 ==> [3,6,12,24,48]

let xs = "terve"
in iterate tail (length xs) xs
  ==> ["terve","erve","rve","ve","e",""]

Here’s a more complicated example: splitting a string into pieces at a given character:

split :: Char -> String -> [String]
split c [] = []
split c xs = start : split c (drop 1 rest)
  where start = takeWhile (/=c) xs
        rest = dropWhile (/=c) xs

split 'x' "fooxxbarxquux"   ==>   ["foo","","bar","quu"]

Pattern Matching for Lists

Last lecture, it was said that constructors are things that can be pattern matched on. Above, it was divulged that the constructors for the list type are : and []. We can put one and one together and guess that we can pattern match on : and []. This is true! Here’s how you can define your own versions of head and tail using pattern matching:

myhead :: [Int] -> Int
myhead [] = -1
myhead (first:rest) = first

mytail :: [Int] -> [Int]
mytail [] = []
mytail (first:rest) = rest

You can nest patterns. That is, you can pattern match more than one element from the start of a list. In this example, we use the pattern (a:b:_) which is the same as (a:(b:_)):

sumFirstTwo :: [Integer] -> Integer
-- this equation gets used for lists of length at least two
sumFirstTwo (a:b:_) = a+b
-- this equation gets used for all other lists
-- (i.e. lists of length 0 or 1)
sumFirstTwo _       = 0

sumFirstTwo [1]      ==> 0
sumFirstTwo [1,2]    ==> 3
sumFirstTwo [1,2,4]  ==> 3

Here’s an example that uses many different list patterns:

describeList :: [Int] -> String
describeList []         = "an empty list"
describeList (x:[])     = "a list with one element"
describeList (x:y:[])   = "a list with two elements"
describeList (x:y:z:xs) =
  "a list with at least three elements"

describeList [1,3]
  ==> "a list with two elements"

describeList [1,2,3,4,5]
  ==> "a list with at least three elements"

List patterns that end with :[] can be typed out as list literals. That is, just like [1,2,3] is the same value as 1:2:3:[], the pattern [x,y] is the same as the pattern x:y:[]. Let’s rewrite that previous example.

describeList :: [Int] -> String
describeList []         = "an empty list"
describeList [x]        = "a list with exactly one element"
describeList [x,y]      = "a list with exactly two elements"
describeList (x:y:z:xs) =
  "a list with at least three elements"

Another way we can nest patterns is pattern matching on the head while pattern matching on a list. For example this function checks if a list starts with 0:

startsWithZero :: [Integer] -> Bool
startsWithZero (0:xs) = True
startsWithZero (x:xs) = False
startsWithZero []     = False

Consuming a List

Using pattern matching and recursion, we can recursively process a whole list. Here’s how you sum all the numbers in a list:

sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs

Here’s how you compute the largest number in a list, this time using a helper function.

myMaximum :: [Int] -> Int
myMaximum [] = 0  -- actually this should be an error...
myMaximum (x:xs) = go x xs
  where go biggest [] = biggest
        go biggest (x:xs) = go (max biggest x) xs

Note:, go is just a cute name for the helper function here. It’s not special syntax.

It’s often convenient to use nested patterns while consuming a list. Here’s an example that counts how many Nothing values occur in a list of Maybes:

countNothings :: [Maybe a] -> Int
countNothings [] = 0
countNothings (Nothing : xs) = 1 + countNothings xs
countNothings (Just _  : xs) = countNothings xs

countNothings [Nothing,Just 1,Nothing]  ==>  2

Building and Consuming a List

Now that we can build and consume lists, let’s do both of them at the same time. This function doubles all elements in a list.

doubleList :: [Int] -> [Int]
doubleList [] = []
doubleList (x:xs) = 2*x : doubleList xs

It evaluates like this:

doubleList [1,2,3]
=== doubleList (1:(2:(3:[])))
==> 2*1 : doubleList (2:(3:[]))
==> 2*1 : (2*2 : doubleList (3:[]))
==> 2*1 : (2*2 : (2*3 : doubleList []))
==> 2*1 : (2*2 : (2*3 : []))
=== [2*1, 2*2, 2*3]
==> [2,4,6]

Once you know pattern matching for lists, it’s straightforward to define map and filter. Actually, let’s just look at the GHC standard library implementations. Here’s map:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

and here’s filter:

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

Note! Naming the argument _pred is a way to tell the reader of the code that this argument is unused. It could have been just _ as well.

Tail Recursion and Lists

When a recursive function evaluates to a new call to that same function with different arguments, it is called tail-recursive. (The recursive call is said to be in tail position.) This is the type of recursion that corresponds to an imperative loop. We’ve already seen many examples of tail-recursive functions, but we haven’t really contrasted the two ways for writing the same function. This is sumNumbers from earlier in this lecture:

sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs

In the second equation the function + is at the top level, i.e. in tail position. The recursive call to sumNumbers is an argument of +. This is sumNumbers written using a tail recursive helper function:

sumNumbers :: [Int] -> Int
sumNumbers xs = go 0 xs
  where go sum [] = sum
        go sum (x:xs) = go (sum+x) xs

Note the second equation of go: it has the recursive call to go at the top level, i.e. in tail position. The + is now in an argument to go.

For a function like sumNumbers that produces a single value (a number), it doesn’t really matter which form of recursion you choose. The non-tail-recursive function is easier to read, while the tail-recursive one can be easier to come up with. You can try writing a function both ways. The tail-recursive form might be more efficient, but that depends on many details.

However, when you’re returning a list there is a big difference between these two forms. Consider the function doubleList from earlier. Here it is again, implemented first directly, and then via a tail-recursive helper function.

doubleList :: [Int] -> [Int]
doubleList [] = []
doubleList (x:xs) = 2*x : doubleList xs

doubleList :: [Int] -> [Int]
doubleList xs = go [] xs
    where go result [] = result
          go result (x:xs) = go (result++[2*x]) xs

Here the direct version is much more efficient. The (:) operator works in constant time, whereas the (++) operator needs to walk the whole list, needing linear time. Thus the direct version uses linear time (O(n)) with respect to the length of the list, while the tail-recursive version is quadratic (O(n²))!

One might be tempted to fix this by using (:) in the tail-recursive version, but then the list would get generated in the reverse order. This could be fixed with an application of reverse, but that would make the resulting function quite complicated.

There is another reason to prefer the direct version: laziness. For now it’s enough for you to know that the direct way of generating a list is simpler, more efficient and more idiomatic. You should try to practice it in the exercises. Check out the standard library implementations of map and filter above, even they produce the list directly without tail recursion!

Something Fun: List Comprehensions

Haskell has list comprehensions, a nice syntax for defining lists that combines the power of map and filter. You might be familiar with Python’s list comprehensions already. Haskell’s work pretty much the same way, but their syntax is a bit different.

Mapping:

[2*i | i<-[1,2,3]]
  ==> [2,4,6]

Filtering:

[i | i <- [1..7], even i]
  ==> [2,4,6]

In general, these two forms are equivalent:

[f x | x <- lis, p x]
map f (filter p lis)

List comprehensions can do even more. You can iterate over multiple lists:

[ x ++ " " ++ y | x <- ["A", "B"], y <- ["C","D"] ]
  ==> ["AC","AD","BC","BD"]

You can make local definitions:

[ reversed | word <- ["this","is","a","string"],
             let reversed = reverse word ]
  ==> ["siht","si","a","gnirts"]

You can even do pattern matching in list comprehensions!

firstLetters string = [ char | (char:_) <- words string ]

firstLetters "Hello World!"
  ==> "HW"

Something Fun: Custom Operators

In Haskell an operator is anything built from the characters !#$%&*+./<=>?@\^|-~. Operators can be defined just like functions (note the slightly different type annotation):

(<+>) :: [Int] -> [Int] -> [Int]
xs <+> ys = zipWith (+) xs ys

(+++) :: String -> String -> String
a +++ b = a ++ " " ++ b

Self Checks

Check 1

What’s the type of this function?

both p q x = p x && q x

a -> Bool -> a -> Bool -> a -> Bool
(a -> Bool) -> (a -> Bool) -> a -> Bool
(a -> Bool) -> (b -> Bool) -> c -> Bool

Check 2

What’s the type of this function?

applyInOut f g x = f (g (f x))`

(a -> b) -> (b -> a) -> a -> b
(a -> b) -> (b -> c) -> a -> c
(a -> a) -> (a -> a) -> a -> a

Check 3

Which one of the following functions adds its first argument to the second?

f x x = x + x
f x = \y -> x + y
f = \x y -> x + x

Check 4

Which one of these functions does not satisfy f 1 ==> 1?

f x = (\y -> y) x
f x = \y -> y
f x = (\y -> x) x

Check 5

Which one of the following functions is correctly typed?

f x y = not x; f :: (Bool -> Bool) -> Bool
f x = x ++ "a"; f :: Char -> String
f x = 'a' : x; f :: String -> String

Check 6

How many arguments does drop 2 take?

Zero
One
Two

Check 7

What does this function do? f (_:x:_) = x

Returns the first element of a list
Returns an arbitrary element of a list
Returns all except the first and last elements of a list
Returns the second element of a list

Check 8

What is the result of the following expression?

reverse $ take 5 . tail $ "This is a test"`

"i sih"
"set a"
A type error

Check 9

If f :: a -> b, then what is the type of map (.f)?

[b -> c] -> [a -> c]
[c -> a] -> [c -> b]
(b -> c) -> [a -> c]
[a] -> [b]

Check 10

What is the type of the leftmost id in id id?

unspecified
a
a -> a
(a -> a) -> (a -> a)

Check 11

What is the type of const const?

unspecified
(c -> a -> b) -> a
c -> (a -> b -> a)
a -> b -> c -> a

Acknowledgment:

This reading was originally written by Joel Kaasinen and John Lång in their open source textbook. The book is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License, which allows users to copy, modify, and distribute the book.

This reading was modified by Titus H. Klinge in 2021 and presented above under the same license in order to better serve the students of this course.

Instructor

Functional Programming

Functional Programming on Lists

Examples of Functional Programming on Lists

Partial Application

Prefix and Infix Notations

Lambdas

Sidenote: The . and $ Operators

Example: Rewriting whatFollows

More Functional List Wrangling Examples

Lists and Recursion

Building a List

Pattern Matching for Lists

Consuming a List

Building and Consuming a List

Tail Recursion and Lists

Something Fun: List Comprehensions

Something Fun: Custom Operators

Self Checks

Check 1

Check 2

Check 3

Check 4

Check 5

Check 6

Check 7

Check 8

Check 9

Check 10

Check 11

Acknowledgment:

Sidenote: The `.` and `$` Operators

Example: Rewriting `whatFollows`