Functional Programming, at Last

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 string = length (filter startsWithA (words string))
  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",""]

Exercises

All exercises can be found in Set3a and Set3b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 3a:

Exercises from 3b:

None for now!

You can check your current points from the blue blob in the bottom-right corner of the page.