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.

Lecture Goals

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

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

List-Breaking Operations (1)

    takeWhile':: (a -> Bool) -> [a] -> [a] -- takeWhile in Prelude
    takeWhile'  p []  = [] 
    takeWhile'  p (x:xs) 
        | p x        = x : takeWhile' p xs 
        | otherwise  = [] 

    dropWhile' :: (a -> Bool) -> [a] -> [a] -- dropWhile in Prelude
    dropWhile'  p []  = [] 
    dropWhile'  p xs@(x:xs') 
        | p x        = dropWhile' p xs' 
        | otherwise  = xs

List-Breaking Operations (2)

Remove blank spaces from beginning of string

    dropWhile ((==) ' ')

For all finite lists xs and predicates p on same type:

    takeWhile p xs ++ dropWhile p xs = xs

List-Breaking Operations (3)

    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:

    span p xs == (takeWhile p xs, dropWhile p xs)

List-Combining Operations

    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

    sp :: Num a => [a] -> [a] -> a 
    sp xs ys = sum' (zipWith' (*) xs ys) 

• Prelude zipWith3 for triples; Data.List has zipWith4 $\cdots$ zipWith7 for 4-to 7-tuples

Rational Arithmetic Revisited

    eqRat :: Rat -> Rat -> Bool 
    eqRat x y = (numer x) * (denom y) == (numer y) * (denom x)

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 (>=) 

Merge Sort (1)

• 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)

Merge Sort (2)

    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?

Key Ideas

• List-breaking and list-combining operators

• Rational arithmetic with higher order functions

• Merge sort

Source Code

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