# Concrete data types

## Lists

insert :: (Ord a) => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
| (x > y) = y:(insert x ys)
| otherwise = x:y:ys


If item is inserted at the end of the list, this list will have to be replicated.

We can share one cell by this.

insert x l@(y:ys) | (x > y)   = y:(insert x ys)
| otherwise = x:l


A function that doesn't produce partial results (that is, it traverses the entire list before producing its result) is called a tail-strict function.

### Deforestation with lists: Avoid intermediate results.

For example, instead of (map (+2) . map (+3)), we transformed it into map (+5).

Burstall-Darlington transformation

### Removing appends (++)

[] ++ x = x
(x : y) ++ z = x : (y ++ z)
(x ++ y) ++ z = x ++ (y ++ z)


The aim of transformation is to eliminate ++ from form (f x ...) ++ yby making it equivalent to f' x ... y. Here, f' is also called generalization of f.

Example:

reverse [] = []
reverse (x : xs) = (reverse xs) ++ (x:[])


is optimized into:

reverse' [] y = y
reverse' (x : xs) y = reverse' xs (x : y)


Both space and time have been reduce from $O(n^2)$ to $O(n)$.

### Reduce the passes

Example:

average xs = sum xs / fromInt (length xs)


we can use tupling method to make two traversals into one.

average' xs = s / fromInt n
where
(s, n)    = av xs
av []     = (0, 0)
av (x:xs) = (x + s0, n0 + 1)
where
(s0, n0) = av xs


However, this solution needs extra space and might cause space leak.

We can parameterize the results:

average'' xs = av' xs 0 0
where
av' []       s n = s / fromInt n
av' (x : xs) s n = av' xs (x + s) (n + 1)


## Trees

In addition to lists and trees, the deforestation algorithm can deal with any other ADT.

The intra-traversal dependency:

comp'' _ Empty = (Empty, 0)
comp'' x (NodeBT v lf rt)
{-  = ( perc x (NodeBT v lf rt)
, tsum (NodeBT v lf rt))
= ( NodeBT (fromInt v / fromInt x)
(perc x lf) (perc x rt)
, v + tsum lf + tsum rt)
= ( NodeBT (fromInt v / fromInt x)
p1 p2
, v + s1 + s2)
where
(p1, s1) = (perc x lf, tsum lf)
(p2, s2) = (perc x rt, tsum rt) -}
= ( NodeBT (fromInt v / fromInt x)
p1 p2
, v + s1 + s2)
where
(p1, s1) = comp'' x lf
(p2, s2) = comp'' x rt

comp' t = t'
where
(t', x) = comp'' x t


Comment: the x in comp' looks a bit weird. It seems to be lazy -- i.e., the fromInt x used in comp'' are not evaluated until the outmost comp'' returns and the x on the left hand side is determined. And when it is determined, the other references to x can be resolved as WHNF.

### Removing appends

inorder Empty            = []
inorder (NodeBT a lf rt) = inorder lf ++ [a] ++ inorder rt


can be optimized into

inorder' t = inorder'' t []
where
inorder'' Empty z = z
inorder'' (NodeBT a lf rt) z =
inorder'' lf (a:(inorder'' rt z))


## Arrays

ixmap b f a = array b [ (k, a ! f k) | k <- range b ]

-- Matrix
row :: (Ix a, Ix b) => a -> Array (a, b) c -> Array b c
row i m = ixmap (l', u') (\j -> (i, j)) m
where ((l, l'), (u, u')) = bounds m


## Exercises

### 4.1

Compare efficiency implication of foldl and foldr.

First, the implementation of these functions are like:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f a []     = a
foldr f a (x:xs) = f x (foldr f a xs)


Although foldl is tail-recursive, but in a lazy language like Haskell, the foldl will never evaluate the f a x but left it as a thunk. Then, a tower of thunks is built

f (f (f a x) x') x'' ....


until the result of foldl can be used.

However, for foldr, f x is put at the head position. Think about map f xs = foldr (\x ys -> f x : ys) [] xs, the f x (foldr f a xs) is g x : (foldr g a xs). And the head, g x will be evaluated instantly as needed. And till the last foldr is resolved, the space needed for this expression is constant.

### 4.2

comp f g l = [ f (g x) | x <- l, x > 10 ]


### 4.3

#### (a)

split' x []     = ([], [])
split' x (a:as) = if a <= x
then (a : xs, ys)
else (xs, a : ys)
where
(xs, ys) = split' x l



#### (b)

split'' x [] ret          = ret
split'' x (a:as) (xs, ys) =
if a <= x
then split'' x as (a : xs, ys)
else split'' x as (xs, a : ys)


Ignored

### 4.5

isEqual :: BTree a -> Btree a -> Bool
isEqual Empty Empty = True
isEqual (BTNode _ l r) (BTNode _ l' r') =
isEqual l l' && isEqual r r'
isEqual _ _ = False


The isEqual will be recursively expanded in the second clause, till the leave node, which is a length propositional to the height of the tree.

Ingored