{----------------------------------------------------------
    Datei mit Beispielen zur Lazy Evaluation 
----------------------------------------------------------}

----------------------------------------------------------
-- Definition unendlicher Datenstrukturen
-----------------------------------------

liste1 :: Num a => [a]
liste1 =  1 : liste1      -- [1,1..]

from   :: Num a =>  a -> [a]   
from n =  n : from (n+1)  -- [n..]

fibnbs     :: Num a => a -> a -> [a]   
fibnbs n m =  n : fibnbs m (n+m)


-- Bsp: Newtonsches Iterationsverfahren
-- ------------------------------------
-- Sei a > 0, x_0 > 0. Dann konvergiert die Folge
-- <x_i | i >= 0> mit x_{i+1} = (x_i + a/x_i) / 2 
-- gegen sqrt(a).

-- Iterationsfunktion
next     :: Fractional a => a -> a -> a
next a x =  (x + a/x) / 2

-- Folgendefinition
folge :: Fractional a => a -> a -> [a]
folge a x_0 = iterate (next a) x_0

-- Abbruchkriterium
within :: (Ord a, Num a) => a -> [a] -> a 
within eps (x1:x2:xs) 
    | abs (x2-x1) < eps  = x2
    | otherwise          = within eps (x2:xs)

-- Approximation der Quadratwurzel
mysqrt           :: (Ord a, Fractional a) => a -> a -> a -> a 
mysqrt x_0 eps a =  within eps (folge a x_0)


-----------------------------------------------------------
-- Problemloesen mit Generate-and-Test
-- -----------------------------------

gt :: (a -> [b]) -> (b -> Bool) -> a -> [b]
gt    generate      test           params 
    =  filter test (generate params)


-- Beispiel: Permutation Sort 
-----------------------------

-- Erzeugung aller Permutationen einer Liste
allPerms :: [a] -> [[a]]
allPerms []     = [[]]
allPerms (x:xs) = concat (map (distr x) (allPerms xs))
   where distr x []       = [[x]]
         distr x l@(y:ys) = (x:l):(map (y:) (distr x ys))

-- Teste, ob Liste sortiert ist
sorted          :: Ord a => [a] -> Bool
sorted []       =  True
sorted [x]      =  True
sorted (x:l@(y:xs)) 
    | x <= y    = sorted l
    | otherwise = False

-- Permutation Sort: 
-- generiere alle Permutationen und filtere sortierte heraus
psort :: Ord a => [a] -> [a]
psort =  head . (gt allPerms sorted)


-----------------------------------------------------------
-- Verarbeitung partieller Informationen
-- -------------------------------------

data Tree a = Leaf a | Node a (Tree a) (Tree a)
                deriving Show

-- Bsp: Bestimme mit nur einem Baumdurchlauf 
-- das Minimum in einem Baum und ersetze jeden
-- Eintrag durch diesen Wert

-- Ansatz: 
-- Minimum bestimmen
minTree              :: Ord a => Tree a -> a 
minTree (Leaf x)     =  x
minTree (Node x l r) =  min x (min (minTree l) (minTree r))

-- Knoteneintraege durch vorgegebenen Wert ersetzen
replace                :: Tree a -> b -> Tree b
replace (Leaf x)     y =  Leaf y
replace (Node x l r) y =  Node y (replace l y) (replace r y)

-- Alle Knoteneintraege durch Minimum ersetzen
replaceMin   :: Ord a => Tree a -> Tree a
replaceMin t =  replace t (minTree t)

---> diese Loesung benoetigt zwei Baumdurchlaeufe


-- Definiere durch Paarung von minTree und replace 
-- eine Funktion, die mit einem Baumdurchlauf auskommt

minReplace                :: Ord a => Tree a -> a -> (a, Tree a)
minReplace (Leaf x)     y =  (x, Leaf y)
minReplace (Node x l r) y =  (min x (min ml mr), Node y ly ry)
            where (ml,ly) =  minReplace l y
                  (mr,ry) =  minReplace r y
                  
-- ... und nun in einem Durchlauf:
replaceMin1   :: Ord a => Tree a -> Tree a
replaceMin1 t =  mt where (min, mt) = minReplace t min   
            

-- Testbaum

testbaum = Node 10 (Node 15 (Node 16 (Node 7 (Leaf 3) (Node 39 (Leaf 15) (Leaf 18)))
                                     (Node 17 (Leaf 13) (Node 9 (Leaf 11) (Leaf 2))))
                            (Leaf 18)) 
                   (Node 25 (Node  6 (Node 14 (Leaf 34) (Node 3 (Leaf 5) (Leaf 36)))
                                     (Node 80 (Leaf 26) (Node 19 (Leaf 4) (Leaf 12))))
                            (Leaf 99)) 




-----------------------------------------------------------
-- Prozessnetze
-- ------------

--
--           .---.    .---.   .-------------.
--  fibs <---| 1 |<---| 1 |<--| zipWith (+) |
--         | '---'  | '---'   '-------------'
--         |        |_____________^     ^
--         |____________________________|
--           

fibs = 1:1:zipWith (+) fibs (tail fibs)

--         .---.      .-------------.
-- ps  <---| 0 |<-----| zipWith (+) |<-- xs
--       | '---'      '-------------'
--       |                   ^
--       |___________________|
--

prefixSums    :: Num a => [a] -> [a]
prefixSums xs =  ps 
    where  ps =  0 : zipWith (+) xs ps