with Interpreters

and Functional Programming

Chapter 17

Higher Order Function Examples

**H. Conrad Cunningham**

**23 October 2018**

Copyright (C) 2017, 2018, H. Conrad Cunningham

**Acknowledgements**: I originally created these slides in Fall 2017 to accompany what is now Chapter 17, Higher Order Function Examples, in the 2018 version of the textbook *Exploring Languages with Interpreters and Functional Programming*.

**Browser Advisory**: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of October 2018 is a recent version of Firefox from Mozilla.

**Code**: The Haskell module for this chapter is in `HigherOrderExamples.hs`

.

Examine other useful functions from the Prelude library (list-breaking operators, list-combining operators)

Explore additional higher-order function examples (rational arithmetic, merge sort)

Remove blank spaces from beginning of string

For all finite lists `xs`

and predicates `p`

on same type:

```
span' :: (a -> Bool) -> [a] -> ([a],[a]) -- span in Prelude
span' _ xs@[] = (xs, xs)
span' p xs@(x:xs')
| p x = let (ys,zs) = span' p xs' in (x:ys,zs)
| otherwise = ([],xs)
break' :: (a -> Bool) -> [a] -> ([a],[a]) -- break in Prelude
break' p = span (not . p)
```

For all finite lists `xs`

and predicates `p`

on same type:

```
zipWith' :: (a->b->c) -> [a]->[b]->[c] -- zipWith in Prelude
zipWith' z (x:xs) (y:ys) = z x y : zipWith' z xs ys
zipWith' _ _ _ = []
zip'' :: [a] -> [b] -> [(a,b)] -- zip
zip'' = zipWith' (\x y -> (x,y))
zip''' = zipWith (,) -- same as zip''
```

Scalar product of vectors

- Prelude
`zipWith3`

for triples;`Data.List`

has`zipWith4`

$\cdots$`zipWith7`

for 4-to 7-tuples

Above can be reimplemented/extended using higher order functions

```
compareRat :: (Int -> Int -> Bool) -> Rat -> Rat -> Bool
compareRat r x y = r (numer x * denom y) (denom x * numer y)
eqRat,neqRat,ltRat,leqRat,gtRat,geqRat :: Rat -> Rat -> Bool
eqRat = compareRat (==)
neqRat = compareRat (/=)
ltRat = compareRat (<)
leqRat = compareRat (<=)
gtRat = compareRat (>)
geqRat = compareRat (>=)
```

If list fewer than two elements, sorted

Otherwise split into two half-length sublists, sort each

Merge two ascending sublists into ascending list

```
msort :: Ord a => (a -> a -> Bool) -> [a] -> [a]
msort _ [] = []
msort _ [x] = [x]
msort less xs = merge less (msort less ls) (msort less rs)
where n = (length xs) `div` 2
(ls,rs) = splitAt n xs
merge _ [] ys = ys
merge _ xs [] = xs
merge less ls@(x:xs) rs@(y:ys)
| less x y = x : (merge less xs rs)
| otherwise = y : (merge less ls ys)
```

```
msort :: Ord a => (a -> a -> Bool) -> [a] -> [a]
msort _ [] = []
msort _ [x] = [x]
msort less xs = merge less (msort less ls) (msort less rs)
where n = (length xs) `div` 2
(ls,rs) = splitAt n xs
merge _ [] ys = ys
merge _ xs [] = xs
merge less ls@(x:xs) rs@(y:ys)
| less x y = x : (merge less xs rs)
| otherwise = y : (merge less ls ys)
```

Under what circumstances does

`msort less xs`

terminate normally?What is time complexity of

`msort less xs`

? space complexity?

List-breaking and list-combining operators

Rational arithmetic with higher order functions

Merge sort

The Haskell module for this chapter is in `HigherOrderExamples.hs`

.