haskell fold/scan reimplementation exercise

gistfile1.hs

module FoldScan where

import Prelude hiding (foldl, foldl', foldl1,
                       foldr, foldr', foldr1,
                       scanl, scanl1, scanr, scanr1)


-- (map fn list) -> list
-- map is (1:1) with the original list and returns a copy of a list after applying a fn to each element

-- (filter fn list) -> list
-- filter is (n:0..n) with the original list and only returns those elements of a list which match a predicate fn

-- (reduce fn initial list) -> result
-- reduce is (n:0..n) with the original list transformed in anyway possible,
-- by a user fn that receives each element *and* the accumulated result up to that point.
-- Having control over the accumulated result is what gives reduce great power.
-- map, filter, and others can easily be expressed in terms of reduce


-- foldl is synonymous with reduce, but requires the initial starting value.
-- foldr is synonymous with reduce, but with the args for the user fn flipped.
-- foldl1/foldr1 variants do not require the starting value.

--foldl (+) 0 [1..5] -- => 15
--foldr (+) 0 [1..5] -- => 15
--foldl (-) 0 [1..5] -- => -15
--foldr (-) 0 [1..5] -- => 3

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _  accumulator []     = accumulator
foldl fn accumulator (x:xs) = foldl fn (fn accumulator x) xs

-- std
foldr' :: (b -> a -> a) -> a -> [b] -> a
foldr' fn accumulator xs = foldl (flip fn) accumulator xs

-- tail-call
foldr :: (b -> a -> a) -> a -> [b] -> a
foldr fn accumulator = helper accumulator
  where
    helper accumulator []     = accumulator
    helper accumulator (x:xs) = helper (fn x accumulator) xs


-- scanl (+) 0 [10,20,30] => [0,10,30,60]
-- scanr (+) 0 [10,20,30] => [60,50,30,0]

-- returns the intermediate values during a reduce operation
-- includes the starting value "0" in the result, from the example above.
-- the last element in the list returned by scanl is the expected result of reduce for the same arguments.
-- the first (head) element in the list returned by scanr is the "..."

-- scanl is equivalent to http://clojuredocs.org/clojure.core/reductions
-- (reductions fn initial coll)

-- std; copied from Prelude with clearer naming; tied for speed with scanl'
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl fn accumulator xs = accumulator :
    (case xs of
      []     -> []
      (x:xs) -> scanl fn (fn accumulator x) xs)

-- tail-call; using cons; tied with scanl for speed; less memory usage
scanl' :: (a -> b -> a) -> a -> [b] -> [a]
scanl' fn accumulator = reverse . helper [accumulator] accumulator
  where
    helper ys _           []     = ys
    helper ys accumulator (x:xs) = helper (val : ys) val xs
      where
        val = fn accumulator x

-- tail-call; using concat; slowest and a memory hog
scanl'' :: (a -> b -> a) -> a -> [b] -> [a]
scanl'' fn accumulator = helper [accumulator] accumulator
  where
    helper ys _           []     = ys
    helper ys accumulator (x:xs) = helper (ys ++ [val]) val xs
      where
        val = fn accumulator x


-- scanl (+) 0 [1..50000]
-- memory: 441.22 mb
-- time:  2.02 sec

-- scanl' (+) 0 [1..50000]
-- memory: 439.522 mb
-- time: 2.02 sec

-- scanl'' (+) 0 [1..50000]
-- memory: 111.126 gb
-- time: 370 sec

-- memory diff is stable: scanl' wins
-- time diff is tied between scanl and scanl' (at various input sizes)
-- winner overall: scanl'
-- note: used (:set +s) to measure time/memory;
-- note: granularity for time is too imprecise at small input sizes to comment

scanr :: (b -> a -> a) -> a -> [b] -> [a]
scanr fn initial xs = reverse $ scanl (flip fn) initial (reverse xs)

-- (hard) exercise for the reader: implement scanr more efficiently