module Exercise_14 where

import Test.QuickCheck

{- Library DO NOT CHANGE -}
data Color = Red | Black deriving (Eq, Show)
data Tree a = Empty | Node Color a (Tree a) (Tree a) deriving (Eq, Show)

prop_fromList :: (Ord a, Show a, Arbitrary a) => ([a] -> Tree a) -> Property
prop_fromList f = property (my_prop_fromList f)
{- End Library -}

{-H14.1-}
f :: ([a] -> Integer) -> [a] -> (Integer -> Integer) -> Integer -> Integer
f h xs g 0 = 1
f h xs g 1 = 1 + h xs
f h xs g n
    | g n > - g n = f h xs g (n - 1) + 2* (h xs - f h xs g (n - 2))
    | otherwise =   f h xs g (n - 1) - h xs + g n

{-H14.2-}

-- Dieser Test ist etwas abstrakter als gewöhnlich.
--
-- Folgendes ist festgelegt:
-- * Ihr Test bekommt als Eingabe eine Funktion vom Typ '[a] -> Tree a', die
--   eine Liste in einen Baum konvertieren soll.
-- * Die Rückgabe Ihres Tests muss eine gültige QuickCheck-Eigenschaft sein.
--
-- Alles andere darf frei festgelegt werden. Zum Beispiel können Sie sich von
-- QuickCheck zusätzliche Parameter generieren lassen. Die einzige Bedinung
-- ist, dass diese Datei kompilieren muss.
--
-- Wie kann man nun 'prop_fromList' implementieren? Sie können sich z.B. von
-- QuickCheck eine zufällige Liste '[a]' als Eingabe übergeben lassen. Ein
-- Beispiel:
--
-- my_prop_fromList f xs =
--   do_something_with (f xs)
--
-- Ferner dürfen Sie auch Vorbedingungen angeben:
--
-- my_prop_fromList f xs =
--   something_about xs ==>
--     do_something_with (f xs)

my_prop_fromList f = True