Beispiele zu zirkulaeren Programmen und Datenstrukturen:

\begin{code}
module CircPrgs where

import Char
import List hiding (nub)
import BinTree

nats :: [Integer]
nats = 1:(map (+1) nats)

fibs :: [Int]
fibs = 1:1:(zipWith (+) fibs (tail fibs))

fib :: Int -> Int
fib n = fibs!!n

fib' :: Int -> Int
fib' 0 = 1
fib' 1 = 1
fib' n = fib' (n-1) + fib' (n-2)

-- see Exercise P-1
nub :: [Integer] -> [Integer]
nub [] = []
nub [x] = [x]
nub (x:xs)  | x `elem` xs     = nub xs
            | otherwise       = x:(nub xs)

-- this deletes duplicates from the end (could use reverse library function)
-- NB: this generates intermediate data-structures
nub' :: [Integer] -> [Integer]
nub' = reverse . nub . reverse

-- NB: quadratic complexity due to repeated filters
nub1 :: [Integer] -> [Integer]
nub1 []      = []
nub1 (x:xs)  = x:(nub1 (filter (/= x) xs))

nub2 :: [Integer] -> [Integer]
nub2 xs = res
          where res = build xs 0
                build [] n      = [] 
                build (x:xs) n  | mem x res n = build xs n 
                                | otherwise = x:(build xs (n+1))
                mem _ _ 0               = False
                mem x (y:ys) n  | x==y  = True
                                | otherwise = mem x ys (n-1)

-- Bird's traversal elimination
treemin :: (Ord a) => BinTree a -> a
treemin (Leaf x) = x
treemin (Node l r) = min (treemin l) (treemin r)
-- treemin = foldTree min

replace :: BinTree a -> a -> BinTree a
replace (Leaf _)   m  = Leaf m
replace (Node l r) m  = Node (replace l m) (replace r m)
-- replace = mapTree return

transform2p :: (Ord a) => BinTree a -> BinTree a
transform2p t = replace t (treemin t)

-- repmin fuses the above functions into one
repmin :: (Ord a) => BinTree a -> a -> (BinTree a, a)
repmin (Leaf x)   m   = (Leaf m, x)
repmin (Node l r) m   =  (l', ml) `comb` (r', mr)
                         where (l', ml) = repmin l m
                               (r', mr) = repmin r m
                               comb (l', ml) (r', mr) = (Node l' r', min ml mr)

transform1p :: (Ord a) => BinTree a -> BinTree a
transform1p t = fst p
                where p = repmin t (snd p)                                

\end{code}