module ExampleFolds
where

{- Example uses of fold functions.  Some of these were mentioned in
   CSci 450/503 class on 22 September 2014.

   Initial: 22 Sep 2014
   Revised: 24 Sep 2014  Added comments, length'', sumcount'
   H. Conrad Cunningham

-}

-- not in standard Prelude, import only foldl' from standard module
import Data.List (foldl')

-- length using foldl
lengthl :: [a] -> Int
lengthl xs = foldl count 0 xs
             where count n x = n+1

-- length using foldr
lengthr :: [a] -> Int
lengthr xs = foldr count 0 xs
             where count x n = n+1

-- length using foldl and lambda expression to count
lengthl' :: [a] -> Int 
lengthl' xs = foldl (\ n _ -> n+1) 0 xs

-- length using foldl' and lambda expression to count
lengthl'' :: [a] -> Int 
lengthl'' xs = foldl' (\ n _ -> n+1) 0 xs

-- Note: Because the "count" operation is strict in both arguments,
-- using foldl' is a bit more efficient.

-- maximum in a list using foldr
maxlist :: Ord a => [a] -> a
maxlist []     = error "maxlist undefined for emply list"
maxlist (x:xs) = foldr max x xs

-- maximum in a list using foldl1
-- foldl1 requires nonempty list, does not require value for []
maxlist' :: Ord a => [a] -> a
maxlist' [] = error "maxlist' undefined for emply list"
maxlist' xs = foldl1 max xs




-- compute sum and length in one pass, returning tuple
sumcount :: Num a => [a] -> (a,a)
sumcount xs = foldl' sc (0,0) xs
              where sc (s,c) x = (s+x,c+1)

-- compute sum and length using lambda expression
sumcount' :: Num a => [a] -> (a,a)
sumcount' xs = foldl' (\sc x -> (fst sc + x, snd sc + 1)) (0,0) xs

-- what does qqq do?
qqq :: Ord a => [a] => [a]
qqq xs = foldr xxx [] xs
         where xxx y []        = [y]
               xxx y (z:zs)
                   | y <= z    = (y:z:zs)
                   | otherwise = z : xxx y zs