-- $Id: FoldrExercise.hs,v 1.1 2019/10/15 21:36:13 leavens Exp leavens $
module FoldrExercise where
import Prelude hiding (foldr, map, filter, concatMap, sum)
-- recall:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr op z (x:xs) = op x (foldr op z xs)
-- the above is equivalent to the sugared version below
foldr' _ z [] = z
foldr' op z (x:xs) = x `op` (foldr' op z xs)
-- we recalled how to use foldr with the sum example
sum ls = foldr (+) 0
-- FOR YOU TO DO
-- Using foldr, write the following
map :: (a -> b) -> [a] -> [b]
-- similarly it's helpful to think about the fully recursive version of map'
map' _ [] = []
map' fun (x:xs) = (fun x) : (map' fun xs)
-- so the first argument to foldr is a lambda function that abstracts that
map fun ls = foldr (\elem -> \res -> (fun elem) : res) [] ls
concatMap :: (a -> [b]) -> [a] -> [b]
-- again, we first thought about the fully recursive version of concatMap'
concatMap' fun [] = []
concatMap' fun (x:xs) = (fun x) ++ (concatMap' fun xs)
-- so the first argument to foldr is a lambda function that abstracts that
concatMap fun ls = foldr (\elem -> \res -> (fun elem) ++ res) [] ls
filter :: (a -> Bool) -> [a] -> [a]
-- once more, first the fully recursive version
filter' _ [] = []
filter' pred (x:xs) = if (pred x) then x:(filter' pred xs) else filter' pred xs
-- then the following has a lambda function that abstracts the pattern above
filter pred ls = foldr (\elem -> (\res -> if (pred elem) then elem:res else res))
[]
ls
-- you can cancel the ls from both sides above, making the following equivalent
filter'' pred = foldr (\elem -> (\res -> if (pred elem) then elem:res else res))
[]