r, `mark = Nothing || Just min {first<=x<=last, f x == EQ}`.
Exercise: How to find the largest index?
## Extended case 2: find turning point.
Description:
> At a given point: x, we break a strictly sorted list with length >= 3 into two parts: a and b, then append a to the end of b and get another list c. Now, the question is, given c, find the index of the smallest element in c(which is the head of original sorted list
Again, we will implement it with the help of `mark` variable.
```hs
import Data.Vector
import Data.Maybe
binSearch :: (Int -> Ordering) -> (Int, Int) -> Maybe Int
binSearch f (p,r) = go (p,r) Nothing
where go (p,r) mark | p > r = mark
| otherwise = case f m of
EQ -> Nothing
LT -> go (p, m-1) (Just m)
GT -> go (m+1, r) mark
where m = (p+r) `div` 2
-- special case for vector
binSearchInVec :: (Ord a) => Vector a -> (Int,Int) -> Maybe Int
binSearchInVec vec (p,r) = binSearch (\ m -> (vec!m) `compare` (vec!p)) (p,r)
main = case binSearchInVec (fromList [2,3,1]) (0,2) of
Nothing -> print "the list is not strictly increasing"
Just i -> print i
```
- When to return the result?
* When `p>r`, we have considered all elements, so we should return the `mark`.
* When `f m == EQ`, we know that either `m == first` or there exists $ i \in [first, last] $ and $ f i = f last $, both of which contradict with our question assumption (list should be strictly sorted and have a size >= 3). So we return Nothing.
- When to go to upper/lower range?
easy question
- How to change the range?
As I have always advocated, change the range aggressively to avoid infinite recursion.
## Extended case 3
Poj has an interesting [problem][poj1064]. My haskell implementation is as follows:
My solution:
```hs
-- lower bound binary search.
binSearch :: (Int -> Bool) -> (Int,Int) -> Maybe Int
binSearch f (p,r) = go (p,r) Nothing
where go (p,r) mark | p > r = mark
| otherwise = if f m then go (m+1,r) (Just m) else go (p,m-1) mark
where m = (p+r) `div` 2
-- Note I didn't follow the format requested by the problem.
cabalLength :: [Double] -> Int -> Double
cabalLength cables num_pieces = case binSearch validLength (1, 10000000) of
Nothing -> fromIntegral 0
Just v -> (fromIntegral v) / 100
where cabal_ints = map (floor . (*100)) cables
validLength len = (foldr (+) 0 (map (`div` len) cabal_ints)) >= num_pieces
main = print $ cabalLength [8.02,7.43,4.57,5.39] 11
```
# Tree traversal
Tree traversal is good example for recursive program design since it's intuitive. But the non-recursive version is not easy to understand, especially if it's implemented in some imperative programming languages like C. In this chapter, I will give the tail-recursive implementation(not in continuation passing style) of tree traversal in Haskell, which is easy to reimplement in C.
First, I will provide the recursive implementation, which will be used by quick check to test the tail-recursive version.
``` haskell
data BinTree a = EmptyTree
| Branch a (BinTree a) (BinTree a) deriving (Show)
preOrder :: BinTree a -> [a]
preOrder (EmptyTree) = []
preOrder (Branch a left right) = [a] ++ preOrder left ++ preOrder right
inOrder :: BinTree a -> [a]
inOrder (EmptyTree) = []
inOrder (Branch a left right) = inOrder left ++ [a] ++ inOrder right
postOrder :: BinTree a -> [a]
postOrder (EmptyTree) = []
postOrder (Branch a left right) = postOrder left ++ postOrder right ++ [a]
data BinTree a = EmptyTree
| Branch a (BinTree a) (BinTree a) deriving (Show)
preOrder :: BinTree a -> [a]
preOrder (EmptyTree) = []
preOrder (Branch a left right) = [a] ++ preOrder left ++ preOrder right
inOrder :: BinTree a -> [a]
inOrder (EmptyTree) = []
inOrder (Branch a left right) = inOrder left ++ [a] ++ inOrder right
postOrder :: BinTree a -> [a]
postOrder (EmptyTree) = []
postOrder (Branch a left right) = postOrder left ++ postOrder right ++ [a]
sampleTree :: BinTree Int
sampleTree = Branch 4 (Branch 2 (Branch 1 EmptyTree EmptyTree) (Branch 3 EmptyTree EmptyTree)) (Branch 6 (Branch 5 EmptyTree EmptyTree) (Branch 7 EmptyTree EmptyTree))
main = putStr (
"preorder: " ++ (show $ preOrder sampleTree) ++ "\n" ++
"inorder: " ++ (show $ inOrder sampleTree) ++ "\n" ++
"postorder: " ++ (show $ postOrder sampleTree) ++ "\n")
```
Tail-recursive version:
```hs
data BinTree a = EmptyTree
| Branch a (BinTree a) (BinTree a) deriving (Show)
preOrderT :: BinTree a -> [a]
preOrderT bt = go [bt] []
where go [] xs = reverse xs
go (EmptyTree:ts) xs = go ts xs
go (Branch v left right:ts) xs = go (left:right:ts) (v:xs)
inOrderT :: BinTree a -> [a]
inOrderT bt = go [bt] [] []
where go [] [] xs = reverse xs
go (EmptyTree:ts) [] xs = go ts [] xs
go (EmptyTree:ts) (v:left_acc) xs = go ts left_acc (v:xs)
go (Branch v left right:ts) left_acc xs = go (left:right:ts) (v:left_acc) xs
-- tail recursive post order traversal
postOrderT :: BinTree a -> [a]
postOrderT bt = go [bt] []
where go [] xs = xs
go (EmptyTree:ts) xs = go ts xs
go (Branch v left right:ts) xs = go (right:left:ts) (v:xs)
sampleTree :: BinTree Int
sampleTree = Branch 4 (Branch 2 (Branch 1 EmptyTree EmptyTree) (Branch 3 EmptyTree EmptyTree)) (Branch 6 (Branch 5 EmptyTree EmptyTree) (Branch 7 EmptyTree EmptyTree))
main = putStr (
"preorder: " ++ (show $ preOrderT sampleTree) ++ "\n" ++
"inorder: " ++ (show $ inOrderT sampleTree) ++ "\n" ++
"postorder: " ++ (show $ postOrderT sampleTree) ++ "\n")
```
The key point of tree traversal lies in visit order. For pre-order traversal, we should visit in the order of v -> left -> right. For in-order, it's left -> v -> right. For post-order, it should be left -> right -> v. The recursive version clearly shows the relationship. That's also why it's intuitive.
For the tail-recursive version, can we make it that clear? We know that stack can be used to implement function call. So we just need to use stack to store the context for visit order. Here, we use list to represent stack.
For `preOrderT`'s local function `go trees xs`:
* `trees`: list of trees to visit. Suppose `trees = (t:ts)`, i.e, `t` is in the left of `ts`. We maintain the order that `t` should always be visited before `ts`.
* `xs`: values of nodes that has already been visited. Suppose `xs = (v:vs)`. We maintain that `v` was visited before `vs`, i.e., when the program terminated, we should return `xs` in reverse order. Also, as `xs` keeps values of nodes visited, we know nodes of values in `xs` are visited before nodes in `trees`.
Therfore:
- `go [] xs` : we have no trees to visit, we return `xs` in reverse order.
- `go (EmptyTree:ts) xs` : currently on the top of the stack is an empty tree. We have nothing to record for it, so we continue with `ts`.
- `go (Branch v left right:ts) xs` : according to our definition, the visit order for a branch is `v -> left -> right`. Therefore, we put `v` in the visited nodes `xs` and continue the process with `left:right:ts`, which means `left` is visited before `right, which is also in front of `ts`. Everything is Clear!
postOrderT looks similar to preOrderT. Note that, the reverse visit order of post-order traversal is `v->right->left`. So we only need to adapt the pre-order algorithm so that right is visited before left, then the reverse of the result of pre-order should be the result of post-order. Clear!
For inOrderT, `go trees xs_acc xs`:
- `trees` and `xs` has the same meaning as preOrderT
- `xs_acc`: keeps values of nodes that we **will** visit. `xs_acc` is constructed during in-order traversal, it records the visiting context of node for the recursive definition. Suppose `xs_acc = (x:acc)`. Then `x` should be visited before `acc`. Also, for `trees = (t:ts)`, at the entry of function go, we should maintain `t -> v -> (ts join acc)`. Here, join means keep the order `t->v->...` for `ts` and `acc`. To simplify, we need to make sure that `t` is visited before `v` while `v` should be visited before all other nodes.
Therefore:
- `go [] [] xs` : nothing to visit, return `xs` in reverse order
- `go (EmptyTree:ts) [] xs` : this case happens when `ts = []`. As we have nothing to record for EmptyTree, we go with `ts`.
- `go (EmptyTree:ts) (v:left_acc) xs` : remember that we need to maintain order `t->v->rest`. Therefore, we first visit `EmptyTree`(nothing to do), then visit `v` by adding it to `xs`.
- `go (Branch v left right:ts) left_acc xs`: according to definition of in-order traversal, we need to make sure `left->v->right`. Therefore, we transfer it to `go (left:right:ts) (v:left_acc) xs`, which perfectly maintains our order `t -> v -> rest`. Clear!
The quick check property to help verify our implementation:
```hs
-- Note the following code can't be run independently.
randomTree :: [a] -> Gen (BinTree a)
randomTree [] = return EmptyTree
randomTree (x:xs) = do
k <- choose (0, (length xs)-1)
let (ls,rs) = splitAt k xs
left <- randomTree ls
right <- randomTree rs
return $ Branch x left right
instance Arbitrary a => Arbitrary (BinTree a) where
arbitrary = do
n <- choose (0, 10000)
lst <- vector n
randomTree lst
prop_postOrder bt = postOrder bt == postOrderT bt
where types = [bt :: BinTree Int]
prop_preOrder bt = preOrder bt == preOrderT bt
where types = [bt :: BinTree Int]
prop_inOrder bt = inOrder bt == inOrderT bt
where types = [bt :: BinTree Int]
```
Based on the tail-recursive implementation, it's easy to implement an iterative version in C/C++:
```cpp
#include