CSc 372 - Comparative Programming Languages
12 : Haskell -- Composing Functions

Christian Collberg

Department of Computer Science

University of Arizona

1 Composing Functions

We want to discover frequently occurring patterns of computation. These patterns are then made into (often higher-order) functions which can be specialized and combined. map f L and filter f L can be specialized and combined:

$\begin{gprogram} double :: [Int] -> [Int]\\ double xs = map ((*) 2) xs\\ \\ p... ...) xs) \\ \redtxt{? doublePos [2,3,0,-1,5]} \\ \mbox{[4, 6, 10]} \end{gprogram}$

2 Composing Functions...

Functional composition is a kind of ``glue'' that is used to ``stick'' simple functions together to make more powerful ones.
In mathematics the ring symbol ( $\circ$ ) is used to compose functions:

$\begin{displaymath}(f \circ g)(x) = f(g(x)) \end{displaymath}$
In Haskell we use the dot (".") symbol:

$\begin{gprogram} infixr 9 . \\ (.) :: (b->c) -> (a->b) -> (a->c) \\ (f . g)(x) = f(g(x)) \end{gprogram}$

3 Composing Functions...

$\begin{gprogram} (.) :: (b->c) -> (a->b) -> (a->c) \\ (f . g)(x) = f(g(x)) \end{gprogram}$

Composition

"." takes two functions f and g as arguments, and returns a new function h as result.
g is a function of type a->b.
f is a function of type b->c.
h is a function of type a->c.
(f.g)(x) is the same as z=g(x) followed by f(z).

4 Composing Functions...

We use functional composition to write functions more concisely. These definitions are equivalent:

$\begin{gprogram} doit x = f1 (f2 (f3 (f4 x))) \\ doit x = (f1 . f2 . f3 . f4) x \\ doit = f1 . f2 . f3 . f4 \end{gprogram}$

The last form of doit is preferred. doit's arguments are implicit; it has the same parameters as the composition.
doit can be used in higher-order functions (the second form is preferred):

$\begin{gprogram} \redtxt{? map (doit) xs} \\ \redtxt{? map (f1 . f2 . f3 . f4) xs} \end{gprogram}$

5 Example: Splitting Lines

Assume that we have a function fill that splits a string into filled lines:

$\begin{gprogram} fill :: string -> [string] \\ fill s = splitLines (splitWords s) \end{gprogram}$

fill first splits the string into words (using splitWords) and then into lines:

$\begin{gprogram} splitWords :: string -> [word] \\ splitLines :: [word] -> [line] \end{gprogram}$

We can rewrite fill using function composition:

$\begin{gprogram} fill = splitLines . splitWords \end{gprogram}$

6 Precedence & Associativity

"." is right associative. I.e.
$\begin{gprogram} f.g.h.i.j = f.(g.(h.(i.j))) \end{gprogram}$
"." has higher precedence (binding power) than any other operator, except function application:
$\begin{gprogram} 5 + f.g 6 = 5 + (f. (g 6)) \end{gprogram}$
"." is associative:
$\begin{gprogram} f . (g . h) = (f . g) . h \end{gprogram}$
"id" is "."'s identity element, i.e id . f = f = f . id:
$\begin{gprogram} id :: a -> a \\ id x = x \end{gprogram}$

7 The `count` Function

Define a function count which counts the number of lists of length in a list :

$\begin{gprogram} \xx count 2 [[1],[],[2,3],[4,5],[]] $\Rightarrow$ 2 \end{gprogram}$

Using recursion:
$\begin{gprogram} count :: Int -> [[a]] -> Int \\ count \_ [] = 0 \\ count n (x... ...xxxx = 1 + count n xs \\ \x \vert otherwise \xxxxxx = count n xs \end{gprogram}$

Using functional composition:
$\begin{gprogram} count' n = length . filter (==n) . map length \end{gprogram}$

8 The `count` Function...

$\begin{gprogram} count' n = length . filter (==n) . map length \end{gprogram}$

What does count' do?

Count

Note that
$\begin{gprogram} count' n xs = length (filter (==n) (map length xs)) \end{gprogram}$

9 The `init` & `last` Functions

last returns the last element of a list.
init returns everything but the last element of a list.

Definitions:
$\begin{gprogram} last = head . reverse \\ \\ init = reverse . tail . reverse \end{gprogram}$

Simulations:
$\begin{gprogram} {[1,2,3]}$\stackrel{\tc{reverse}}{\Longrightarrow}$[3,2,1]$\sta... ...ightarrow}$ [2,1]$\stackrel{\tc{reverse}}{\Longrightarrow}$[1,2] \end{gprogram}$

10 The `any` Function

any p xs returns True if p x == True for some x in xs:

$\begin{gprogram} any ((==)0) [1,2,3,0,5] $\Rightarrow$ True \\ any ((==)0) [1,2,3,4] $\Rightarrow$ False \end{gprogram}$

Using recursion:
$\begin{gprogram} any :: (a -> Bool) -> [a] -> Bool \\ any \_ [] = False \\ any p (x:xs) = \= \vert p x = True \\ \x \vert otherwise = any p xs \end{gprogram}$

Using composition:
$\begin{gprogram} any p = or . map p \\ \redtxt{{[1,0,3]}$\stackrel{\tc{map ((==... ...dtxt{[False,True,False]$\stackrel{\tc{or}}{\Longrightarrow}$True} \end{gprogram}$

11 `commaint` Revisited...

Let's have another look at one simple (!) function, commaint.
commaint works on strings, which are simply lists of characters.
You are not $\backslash\backslash\backslash$ now supposed to understand this!

From the commaint documentation:

[commaint] takes a single string argument containing a sequence of digits, and outputs the same sequence with commas inserted after every group of three digits, $\cdots$

12 `commaint` Revisited...

Sample interaction:
$\begin{gprogram} \redtxt{? commaint ''1234567''} \\ \x 1,234,567 \end{gprogram}$

commaint in Haskell:
$\begin{gprogram} commaint = \= reverse . foldr1 ($\backslash$x y->x++'',''++y) .... ... takeWhile (not.null) . \\ \x \xx map (take n).iterate (drop n) \end{gprogram}$

13 `commaint` Revisited...

CommaInt

14 `commaint` Revisited...

$\begin{gprogram} commaint = \= reverse . foldr1 ($\backslash$x y->x++'',''++y) .... ... takeWhile (not.null) . \\ \x \xx map (take n).iterate (drop n) \end{gprogram}$

iterate (drop 3) s returns the infinite list of strings
$\begin{gprogram}[s, drop 3 s, drop 3 (drop 3 s),\\ \x drop 3 (drop 3 (drop 3 s)), $\cdots$] \end{gprogram}$
map (take n) xss shortens the lists in xss to n elements.

15 `commaint` Revisited...

$\begin{gprogram} commaint = \= reverse . foldr1 ($\backslash$x y->x++'',''++y) .... ... takeWhile (not.null) . \\ \x \xx map (take n).iterate (drop n) \end{gprogram}$

takeWhile (not.null) removes all empty strings from a list of strings.
foldr1 (x y->x++","++y) s takes a list of strings s as input. It appends the strings together, inserting a comma in between each pair of strings.

16 Lambda Expressions

(x y->x++","++y) is called a lambda expression.
Lambda expressions are simply a way of writing (short) functions inline. Syntax:
$\begin{gprogram} \xx $\backslash$ arguments -> expression \end{gprogram}$
Thus, commaint could just as well have been written as

$\begin{gprogram} commaint = $\cdots$ . foldr1 insert . $\cdots$ \\ \x where \= group n = $\cdots$ \\ \x \x insert x y = x++'',''++y \end{gprogram}$

Examples:
$\begin{gprogram} squareAll xs = map ($\backslash$ x -> x * x) xs \\ length = foldl' ($\backslash$n \_ -> n+1) 0 \end{gprogram}$

17 Summary

The built-in operator "." (pronounced ``compose'') takes two functions f and g as argument, and returns a new function h as result.
The new function h = f . g combines the behavior of f and g: applying h to an argument a is the same as first applying g to a, and then applying f to this result.
Operators can, of course, also be composed: ((+2) . (*3)) 3 will return 2 + (3 * 3) = 11.

18 Homework

Write a function mid xs which returns the list xs without its first and last element.
1. use recursion
2. use init, tail, and functional composition.
3. use reverse, tail, and functional composition.

$\begin{gprogram} \redtxt{? mid [1,2,3,4,5]} $\Rightarrow$ [2,3,4] \\ \redtxt{?... ...} $\Rightarrow$ ERROR \\ \redtxt{? mid [1,3]} $\Rightarrow$ [] \end{gprogram}$

Christian S. Collberg
2005-09-19

CSc 372 - Comparative Programming Languages 12 : Haskell -- Composing Functions

CSc 372 - Comparative Programming Languages
12 : Haskell -- Composing Functions