with Interpreters

and Functional Programming

Chapter 14

Infix Operators and List Examples

**H. Conrad Cunningham**

**17 October 2018**

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.

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`

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

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

```
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

`++`

```
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?

`++`

(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

`++`

(2)For all finite lists

`xs`

:For all natural numbers

`n`

and finite lists`xs`

:

`!!`

```
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?

`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?

`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`

,

`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`:`

```
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
```

- 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 positionEmpty list is sorted

```
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 list, element constrained to class `Ord`

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

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

.