0

In Scala's foldLeft, I know how to access the accumulator and element values in Scala, but not Haskell.

I could use foldLeft to find out, between 1 and 100, how many numbers have a remainder of 1 when divided by 3:

scala> List.range(1, 101).foldLeft(0){ (acc, elem) =>
     |    if (elem % 3 == 1) acc + 1
     |    else acc
     | }
res2: Int = 33

How can I do the same in Haskell?

Kevin Meredith
  • 41,036
  • 63
  • 209
  • 384
  • `Data.List` has many useful functions similar to Scala's List. `Data.List.foldl` is scala's `List.foldLeft`. `foldl` is imported by `Prelude`, but watch out for other useful stuff - it may need importing explicitly. – Sassa NF Apr 14 '14 at 08:16

3 Answers3

5

There's essentially a 1-to-1 correspondence:

mySum :: [Int] -> Int
mySum xs = foldl (\acc elem ->
    if elem `mod` 3 == 1
        then acc + 1
        else acc
    ) 0 xs

Other than syntax and order of arguments, there's no real difference.

For future readers, it is recommended to avoid using foldl in practice. Due to laziness in foldl's implementation, space leaks can occur for large lists. Instead, there is a strict version foldl' which can be used as a drop-in replacement or the right fold foldr which has a bit format:

mySum xs = foldr (\elem acc ->    -- order of arguments swapped
    if elem `mod` 3 == 1
        then acc + 1
        else acc
    ) 0 xs
bheklilr
  • 53,530
  • 6
  • 107
  • 163
  • 1
    Also, you should point out that using `Data.List.foldl'` will avoid a space leak. – Gabriella Gonzalez Apr 14 '14 at 03:01
  • 1
    In fact `foldr` in this scenario will lead to stack space overflow on sufficiently large input (try [1..10000000]) while `foldl'` and `foldl` won't. I believe nowadays GHC with `-O2` now can figure out and remove unnecessary laziness, that is why `foldl` does not stack overflow here. – Ed'ka Apr 14 '14 at 03:43
  • @Ed'ka I am not certain why `foldl` would stack overflow. – Sassa NF Apr 14 '14 at 08:21
4

This is a direct translation of your Scala code to Haskell:

foldl (\acc x -> if x `mod` 3 == 1 then acc + 1 else acc) 0 [1..100]

In Haskell, because of laziness of it, using foldl usually is not a good idea, a better choose is foldl' or foldr, here is the foldr version:

foldr (\x acc -> if x `mod` 3 == 1 then acc + 1 else acc) 0 [1..100]
Community
  • 1
  • 1
Lee Duhem
  • 14,695
  • 3
  • 29
  • 47
  • Could you please elaborate on the "why" behind: `In Haskell, because of laziness of it, using foldl usually is not a good idea`? – Kevin Meredith Apr 14 '14 at 02:35
  • @KevinMeredith Because GHC is lazy, it will build up a very large list of "thunks", or computation promises with how `foldl` is implemented, and it won't evaluate them until the entire list has been traversed. The `foldl'` variant is strict in its arguments, so it will evaluate the fold while traversing the list, and `foldr`'s implementation lets it generate one thunk at a time rather than traversing the entire spine of the list in one go. – bheklilr Apr 14 '14 at 02:38
  • @KevinMeredith Beside the exaplation given by @bheklilr, you could also searcin in SO using keywords `[haskell] foldr foldl`, there are lots of relevant questions and answers. – Lee Duhem Apr 14 '14 at 02:43
0

It's rather similar:

foldl (\acc x -> if (x `mod` 3 == 1) then acc + 1 else acc) 0 [1..100]

The first argument to foldl is the lambda, the second is the accumulator 0 and the third is the range of values.

Refer to this question to understand the differences between foldl, foldl' and foldr.

Community
  • 1
  • 1
iamnat
  • 4,056
  • 1
  • 23
  • 36