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

Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 14, Infix Operators and List

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.

Lecture Goals

• Introduce Haskell infix operations

• Introduce properties of operations

• Examine examples of correct and efficient first-order list processing programs (e.g. insertion sort)

• Continue to examine library of useful functions

Source code: ListProgExamples.hs

Infix Operations (1)

Binary operation:

function of type t1 -> t2 -> t3

• Often prefer infix syntax, e.g., x + y

• Use parentheses to specify order ((y * (z+2)) + x))

• Use precedence to avoid parentheses for different operators

  x + y * z same as (x + (y * z))

Infix Operations (2)

• Use binding or association order to avoid parentheses for similar operators

  • left binding x + y - z same as ((x + y) - z)

  • right binding x^y^z same as (x^(y^z))

  • free binding means no default binding order

• Haskell declarations for left, right, free binding with precedence 0-9, where higher number binds more tightly

      infixl n op
      infixr n op
      infix  n op

Common Infix Operations

    infixr 8 ^                     -- exponentiation
    infixl 7 *                     -- multiplication
    infix  7 /                     -- division
    infixl 6 +, -                  -- addition, subtraction
    infixr 5 :                     -- cons
    infix  4 ==, /=, <, <=, >=, >  -- relational comparisons
    infixr 3 &&                    -- Boolean AND
    infixr 2 ||                    -- Boolean OR 

Function application has precdence of 10

Appending Lists: ++

    infixr 5 ++
        
    (++) :: [a] -> [a] -> [a]   -- in Prelude 
    [] ++ xs     = xs           -- nil left operand 
    (x:xs) ++ ys = x:(xs ++ ys) -- non-nil left operand 

• Termination of xs ++ ys?

• Precondition? Postcondition?

• Time complexity? Space complexity?

• Data sharing?

Properties of ++ (1)

Associativity if ++:

For any finite lists xs, ys, and zs,
xs ++ (ys ++ zs) == (xs ++ ys) ++ zs

Identity for ++:

For any finite list xs, [] ++ xs = xs = xs ++ []

Proofs? See Chapter 25

Properties of ++ (2)

• For all finite lists xs:

      sum (xs ++ ys)     = sum xs + sum ys 
      product (xs ++ ys) = product xs * product ys 
      length (xs ++ ys)  = length xs + length ys 

• For all natural numbers n and finite lists xs:

      take n xs ++ drop n xs = xs

Element Selection: !!

    infixl 9 !!
    (!!) :: [a] -> Int -> a 
    xs     !! n | n < 0 = error "!! negative index"
    []     !! _         = error "!! index too large"
    (x:_)  !! 0         = x 
    (_:xs) !! n         = xs !! (n-1) 

• Termination of xs !! n?

• Precondition? Postcondition?

• Time complexity? Space complexity?

• Tail recursive? Data sharing?

Reversing a List: rev (1)

    rev :: [a] -> [a]
    rev []     = []            -- nil argument
    rev (x:xs) = rev xs ++ [x] -- non-nil argument

• Termination of rev xs? (note ++)

• Precondition? Postcondition?

• Tail recursive?

• Time complexity? (careful!) Space complexity?

• Data sharing?

Reversing a List: rev (2)

Distribution:

For any finite lists xs and ys,
rev (xs ++ ys) = rev ys ++ rev xs

Inverse:

For any finite list xs, rev (rev xs) = xs

For any finite lists xs and ys and natural numbers n,

    take n (rev xs)  = rev (drop (length xs - n) xs)

Tail recursive reverse

    reverse' :: [a] -> [a] -- reverse in Prelude 
    reverse' xs = rev xs []
                  where rev []     ys = ys 
                        rev (x:xs) ys = rev xs (x:ys) 

• Termination of rev xs ys?

• Precondition? Postcondition?

• Time complexity? Space complexity? If improved, how?

• Compare ++ versus :

Other Useful List Functions

    splitAt' :: Int -> [a] -> ([a],[a]) -- splitAt in Prelude
    splitAt' n xs =  (take' n xs, drop' n xs) 

    zip' :: [a] -> [b] -> [(a,b)]   -- zip in Prelude
    zip' (x:xs) (y:ys) = (x,y) : zip' xs ys -- zip.1
    zip' _      _      = []                 -- zip.1
 
    unzip' :: [(a,b)] -> ([a],[b])  -- unzip in Prelude
    unzip' []         = ([],[])
    unzip' ((x,y):ps) = (x:xs, y:ys)
                        where (xs,ys) = unzip' ps

Insertion Sort

Ascending:

Every element is <= all of its successors

• similar for descending, increasing, decreasing

Idea:

To sort x:xs, sort tail xs, then insert x at correct position

Empty list is sorted

Insertion Sort of Int

    isort :: [Int] -> [Int]
    isort []     = []
    isort (x:xs) = insert x (isort xs)

    insert :: Int -> [Int] -> [Int]
    insert x []     = [x]
    insert x xs@(y:ys)     -- xs alias of (y:xs)
        | x <= y    = (x:xs)
        | otherwise = y : (insert x ys)

• Termination of insert x xs? of isort xs?

• Time complexity of insert x xs? of isort xs?

• Space complexity of insert x xs? of isort xs?

Polymorphic Insertion Sort

Polymorphic list, element constrained to class Ord

    isort' :: Ord a => [a] -> [a]
    isort' []     = []
    isort' (x:xs) = insert' x (isort' xs)

    insert' :: Ord a => a -> [a] -> [a]
    insert' x []    = [x]
    insert' x xs@(y:ys)     -- xs alias of (y:xs)
        | x <= y    = (x:xs)
        | otherwise = y : (insert' x ys)

Key Ideas

• Haskell infix operations

• Properties of operations

• Several examples of correct and efficient first-order list processing programs (e.g. insertion sort)

• Library of useful functions

Code

The Haskell code for this section is in file ListProgExamples.hs.