module Arithmetik where
import Prelude hiding (sum,foldr,foldl)
--pow = pow3
pow1 b 0 = 1
pow1 b e = b * pow1 b (e-1)
pow2 b 0 = 1
pow2 b e
-- | e `mod` 2 == 0
| even e = pow2 (b * b) (e `div` 2)
| otherwise = b * pow2 (b * b) (e `div` 2)
pow3 b e
| e < 0 = error "Exponent < 0"
| otherwise = pow3acc 1 b e
where pow3acc acc b 0 = acc
pow3acc acc b e
| even e = pow3acc acc (b * b) (e `div` 2)
| otherwise = pow3acc (acc * b) (b * b) (e `div` 2)
--sum [] = 0
--sum (x:xs) = x + sum xs
sumacc acc [] = acc
sumacc acc (x:xs) = (sumacc $! (acc + x)) xs
sum xs = sumacc 0 xs
root e r
| e < 1 = error "Zu kleiner Wurzelexponent"
| r < 0 = error "Negativer Radikand"
| otherwise = searchRoot 0 (r+1)
where searchRoot a b
| b - a == 1 = a
| pow3 half e <= r = searchRoot half b
| otherwise = searchRoot a half
where half = (a+b) `div` 2
isPrime n
| n < 2 = error "Zu kleine Zahl"
-- | otherwise = null (filter (\k -> n `mod` k == 0) [2..(root 2 n)])
| otherwise = all (\k -> n `mod` k > 0) [2..(root 2 n)]
--merge [] [] = []
merge xs [] = xs
merge [] ys = ys
--merge (x:xs) (y:ys) = if x < y then x : merge xs (y:ys) else y : merge (x:xs) ys
merge (x:xs) (y:ys)
| x < y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
mergeSort [] = []
mergeSort [x] = [x]
--mergeSort xs = let median = length xs `div` 2
-- in merge (mergeSort (take median xs)) (mergeSort (drop median xs))
mergeSort xs = merge (mergeSort a) (mergeSort b)
where (a,b) = splitAt (length xs `div` 2) xs
isSorted (x:y:xs)
| x <= y = isSorted (y:xs)
| otherwise = False
isSorted _ = True
mergeSortedIsSorted xs = (isSorted . mergeSort) xs
--mergeSortedIsSorted xs = isSorted (mergeSort xs)
--mergeSortedIsSorted = isSorted . mergeSort
foldr f y [] = y
foldr f y (x:xs) = x `f` foldr f y xs
foldl f y [] = y
foldl f y (x:xs) = foldl f (x `f` y) xs
andr = foldr (&&) True
andl = foldl (&&) True