data Pint = Zero | Succ Pint 
    deriving (Eq, Show)
    
istZahl x  =    case x of {Zero  -> True; Succ y ->  istZahl  y} 
 
peanoPlus x  y  =   if  istZahl  x &&  istZahl  y then pplus x  y 
                    else bot 
pplus x  y  =  case x of  Zero  -> y
                          Succ  z -> Succ (pplus z y)   

peanoleq x y = 
  (istZahl x) &&
  (istZahl y) &&
  (case  x of 
         {Zero -> True;
          Succ xx -> case  y of {Zero -> False; Succ yy  -> peanoleq xx yy}}) 


--
--  Succ Zero
--  Succ ((\x ->x) Zero)
--  Succ Zero
--  case (Succ bot) of {Zero->0;Succ x->1}
--  Succ bot
 


peanoMal x  y  =   if  istZahl  x &&  istZahl  y then pmal x  y 
                   else bot 
pmal x  y  =  case x of  Zero  -> Zero
                         Succ  z -> pplus (pmal z y)  y  

pfak x   =  case x of  Zero  -> Succ Zero
                       Succ  z ->  (pmal x (pfak z))              

peanoFak x = if  istZahl  x  then pfak x else bot
peanoToNum x = let ptn p y = case p of {Zero -> y; Succ p -> ptn p (y+1)}
                 in ptn x 0
numToPeano x = if x <= 0 then Zero else Succ (numToPeano (x-1))
        
testpeano = peanoToNum (peanoFak (numToPeano 8))       --    ergibt 40320     
           
fak 0  = 1
fak 1  = 1
fak n  = n* (fak (n-1))

schaltjahr x =  (x `mod` 4 == 0) && 
                   (((x `mod` 100) /= 0)  || (x `mod` 400 == 0)) 

quadrat x = x*x
                                      
---

reversequadr []     = []
reversequadr (x:xs) = reversequadr xs ++ [x]
                
reverseac x          = rev_accu x [] 
rev_accu xs stack    = case xs of {[] -> stack;  
                              h:t  ->  (rev_accu t (h:stack))} 
                              
bot = bot
hd xs          =  case xs of {h:t -> h; [] -> bot}
tl xs          =  case xs of {h:t -> t; [] -> bot} 

transpose xss  =  case xss of 
                    {[] -> bot;  
                     h:t -> 
                        case h of {[] -> []; 
                                   h:t -> (map hd xss) 
                                           : (transpose (map tl xss))}} 


transposetest = transpose [[1,2],[3,4]]


vectoradd_2            =  zipWith (+) 
 

---    zipWith ::(a -> b ->  c) -> [a] -> [b] -> [c] 
----
summe :: Num a => [a]->a
summe [] = 0
summe (x:xs) = x + summe xs


remove p xs =  filter (\x -> not (p(x))) xs
 
remove' p    =  filter ( not  . p)  

---- Quicksort 

partition p []     =  ([],[]) 
partition p (h:t) 
       | (p h)     =  (h:oks, noks) 
       | otherwise =  (oks, h:noks) 
           	            where (oks, noks) = partition p t 
 
quicksort []       = [] 
quicksort (h:t)    = quicksort kleine ++  (h :  (quicksort grosse)) 
                       where (kleine, grosse) =  partition (< h) t
 

--   Alternativ, unter Verwendung von  filter 
 
qs []             = [] 
qs (h:t)          = qs (filter (<= h) t) ++  
                     (h :  (qs (filter (> h) t))) 
 

eulerapprox = scanl (+) 0.0 (map (1.0 /) (scanl (*) 1.0 [1.0 ..]))


fakplp 0 = 1
fakplp (np@(n+1)) = np*(fakplp n)
------------------------------
strict f x   =  x `seq`  f x
foldls op  e  []     = e
foldls op  e  (h:t)  = strict (foldls op)  (e `op`  h)  t

lengthfl   =  foldl ladd  0 
                  where ladd  x _  = 1+x
                  
lengthfls   =  foldls ladd  0 
                  where ladd  x _  = 1+x
 
lengthfr =  foldr radd  0 
		       where radd  _  x =  1+x 
		       
---------------------------		     	       
inits []    = [[]]
inits (h:t) = []: (map (h:) (inits t))

scanlini f e   = map (foldl f e) . inits 


tails  []    = [[]]
tails (x:xs) = (x:xs) : tails xs

scanrtls f e    = (map (foldr f e)) . tails
       
------------------------------

asumme []     =  0
asumme (x:xs) = x+asumme xs

---------Mengen 

 
data Menge a = Set [a]
 --   deriving Show

instance Eq a => Eq (Menge a)  where
       Set xs == Set ys  = subset xs ys && subset ys xs

subset:: Eq a => [a] -> [a] -> Bool
subset xs ys = all  (`elem` ys)  xs

--  richtige Instazdef, da Ord nur bedingt fuer partielle Ordnungen geeignet
instance (Ord a) => Ord (Menge a)  where
      Set xs <= Set ys = subset xs ys
      Set xs >= Set ys = subset ys xs
      Set xs < Set ys  = subset xs ys && not (subset ys xs)
      Set xs > Set ys  = subset ys xs && not (subset xs ys)
      min (Set xs) (Set ys) = if subset xs ys then Set xs else
                              if subset ys xs then Set ys else error "subset nicht total"
      max (Set xs) (Set ys) = if subset ys xs then Set xs else
                              if subset xs ys then Set ys else error "subset nicht total"
      compare (Set xs) (Set ys) = if xs == ys then EQ else if subset xs ys then LT
                                  else if   subset ys xs then GT else error "subset nicht total"
 
instance (Eq a,Show a) => Show (Menge a) where
  showsPrec p xs = showMenge xs

showMenge:: (Eq a, Show a) =>
                  Menge a -> String -> String
showMenge xs = showMengeR (constructMenge xs)
showMengeR (Set [])     = showString "{}"
showMengeR (Set (x:xs)) = showChar '{' . shows x . showm xs
		      where showm []     = showChar '}'
			    showm (x:xs) = showChar ',' . shows x . showm xs
			    
constructMenge (Set xs) = constructMengeR xs []
constructMengeR [] ys = Set (reverse ys)
constructMengeR (x:xs) ys = if x `elem` ys then constructMengeR xs ys
                            else constructMengeR xs (x:ys)			    
			                     
 --------------
class Finite a  where members :: [a]
      

instance Finite Bool where members = [True, False] 

instance (Finite a, Finite b) => Finite (a, b)  where 
      members = [(x,y) | x <- members, y <- members] 

instance Finite a => Finite [a] 
     where  members = potenzmenge  members 
potenzmenge [] = [[]]
potenzmenge (x:xs) = let p = potenzmenge xs 
                      in p ++ (map (x:) p)
     
--  members::Bool  -> [ True, False]  
--  length (members :: [((Bool, Bool), (Bool, Bool)]])  --->  16

instance Finite a => Finite (Menge a) 
      where  members = map Set (potenzmenge members)  


powerSet (Set [])     = Set [Set []]
powerSet (Set (x:xs)) = let Set p = powerSet (Set xs)
                            consSet x (Set xs) = Set (x:xs)
                          in Set (p ++  (map (consSet x) p)) 


testSet = powerSet (Set [1,2,3]) == powerSet (Set [3,2,1])


-------
data Baum a = Blatt a | Knoten (Baum a) (Baum a)
      deriving (Eq, Show)

instance Functor Baum where
    fmap = baummap
    
    
baummap f (Blatt a) = Blatt (f a)
baummap f (Knoten x y) = Knoten (baummap f x) (baummap f y)

--  testbaum2 = 
testbaum  = fmap quadrat (Knoten (Knoten (Blatt 1) (Blatt 2)) (Blatt 3))  


ttest1 x = if x == [] then 1 else 2
ttest2 x = if [] == ([]::[Int]) then 1 else 2