The . and $ operators, List wranging (takewhile, etc)

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 string = map shorten (tails string)
    where shorten s = take n s

whatFollows :: Char -> Int -> String -> [String]
whatFollows c k string = map tail (filter match (substringsOfLength (k+1) string))
    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 string = map tail (filter match (map shorten (tails string)))
    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 string = map tail (filter match (map (take (k+1)) (tails string)))
    where match sub = take 1 sub == [c]

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

whatFollows c k string = map tail . filter match . map (take (k+1)) $ tails string
    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:

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

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]

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:

Exercise 3a.5

-- Ex 5: Implement a function capitalize that takes in a string and
-- capitalizes the first letter of each word in it.
--
-- You should probably define a helper function capitalizeFirst that
-- capitalizes the first letter of a string.
--
-- These functions will help:
--  - toUpper :: Char -> Char   from the module Data.Char
--  - words :: String -> [String]
--  - unwords :: [String] -> String
--
-- Example:
--   capitalize "goodbye cruel world" ==> "Goodbye Cruel World"

capitalize :: String -> String
capitalize = todo

Exercise 3a.6

-- Ex 6: powers k max should return all the powers of k that are less
-- than or equal to max. For example:
--
-- powers 2 5 ==> [1,2,4]
-- powers 3 30 ==> [1,3,9,27]
-- powers 2 2 ==> [1,2]
--
-- You can assume that k is at least 2.
--
-- Hints:
--   * k^max > max
--   * the function takeWhile

powers :: Int -> Int -> [Int]
powers k max = todo

Exercise 3a.7

-- Ex 7: implement a functional while loop. While should be a function
-- that takes a checking function, an updating function, and an
-- initial value. While should repeatedly apply the updating function
-- to the initial value as long as the value passes the checking
-- function. Finally, the value that doesn't pass the check is
-- returned.
--
-- Examples:
--
--   while odd (+1) 1    ==>   2
--
--   while (<=4) (+1) 0  ==>   5
--
--   let check [] = True
--       check ('A':xs) = False
--       check _ = True
--   in while check tail "xyzAvvt"
--     ==> Avvt

while :: (a->Bool) -> (a->a) -> a -> a
while check update value = todo

Exercise 3a.8

-- Ex 8: another version of a while loop. This time, the check
-- function returns an Either value. A Left value means stop, a Right
-- value means keep looping.
--
-- The call `whileRight check x` should call `check x`, and if the
-- result is a Left, return the contents of the Left. If the result is
-- a Right, the function should call `check` on the contents of the
-- Right and so on.
--
-- Examples (see definitions of step and bomb below):
--   whileRight (step 100) 1   ==> 128
--   whileRight (step 1000) 3  ==> 1536
--   whileRight bomb 7         ==> "BOOM"
--
-- Hint! Remember the case-of expression from lecture 2.

whileRight :: (a -> Either b a) -> a -> b
whileRight check x = todo

-- for the whileRight examples:
-- step k x doubles x if it's less than k
step :: Int -> Int -> Either Int Int
step k x = if x<k then Right (2*x) else Left x

-- bomb x implements a countdown: it returns x-1 or "BOOM" if x was 0
bomb :: Int -> Either String Int
bomb 0 = Left "BOOM"
bomb x = Right (x-1)

You have reached the end of this section! Continue to the next section:

5. Lists and Recursion

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

The . and $ operators, List wranging (takewhile, etc)

Example: Rewriting whatFollows

More Functional List Wrangling Examples

Exercises

Exercises from 3a:

Example: Rewriting `whatFollows`