Skip to content

Instantly share code, notes, and snippets.

@ordoghl
Created October 17, 2018 08:53
Show Gist options
  • Save ordoghl/08a30d3483ac72f3a7ca24869d80b1a0 to your computer and use it in GitHub Desktop.
Save ordoghl/08a30d3483ac72f3a7ca24869d80b1a0 to your computer and use it in GitHub Desktop.
Haskell foldl and foldr implementation
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' fn acc [] = acc
foldl' fn acc (x:xs) = foldl' fn (fn acc x) xs
foldr' :: (a -> b -> b) -> b -> [a] -> b
foldr' fn acc [] = acc
foldr' fn acc (x:xs) = fn x (foldr' fn acc xs)
f :: Double -> Double -> Double
f = \acc x -> acc / x + 1
main :: IO ()
main = do
print (foldl' f 0 [1,2,3])
print (foldr' f 0 [1,2,3])
print (foldr' (/) 1 [2,4,8])
@asarkar
Copy link

asarkar commented Jan 2, 2023

Your implementation of foldl' is incorrect because the function operation is not strict as required by the specification.
https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-List.html#v:foldl-39-

You can test it using evaluate (foldl' (const id) () [throw StrictException, ()]) which is supposed to throw exception but won't. To fix, define as foldl' f z (x : xs) = let z' = f z x in z' seq foldl' f z' xs. See https://wiki.haskell.org/Seq

@KitsuneSamaIX
Copy link

@asarkar the foldl' from Data.List you are referring to is indeed the strict version of foldl but the original creator of this post was clearly referring to the standard versions of foldl and foldr as he also said in the title of the post.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment