MaxPrefixSum_Fold.hs

module Blueprint where
import Test.SmallCheck
import qualified Test.SmallCheck.Property

import Data.List ( inits )

fold_balanced :: b -> (b -> b -> b) -> [b] -> b
fold_balanced z f xs = case xs of
    [ ] -> z
    [x] -> x
    _   -> let (l, r) = splitAt (div (length xs) 2) xs
           in  f (fold_balanced z f l) (fold_balanced z f r)

mps_specification :: [ Int ] -> Int
mps_specification = maximum 
        . map sum 
        . inits 

mps_implementation :: [ Int ] -> Int
mps_implementation = snd 
        . fold_balanced z f
        . map (\x -> (x, max 0 x))

z :: (Int,Int)
z = (0, 0)

f :: (Int,Int) -> (Int,Int) -> (Int,Int)
f = \ (sl, ml) (sr, mr) -> (sl + sr, max ml (sl + mr))

test :: Bool
test = and 
     [ check 2 $ \ a b c -> f a (f b c) == f (f a b) c
     , check 5 $ \ xs -> mps_specification xs == mps_implementation xs 
     ] 

-- damit man die fehlschlagenden Tests in ghci sieht:
-- smallCheckI  $ \ a b c -> f a (f b c) == f (f a b) c

check depth prop = 
  and $ map ( Test.SmallCheck.Property.resultIsOk . Test.SmallCheck.Property.result ) 
      $ Test.SmallCheck.Property.test prop depth