Stack Overflow
Stack Overflow

Questions tagged [fold]

In functional programming, a fold, also known variously as reduction, accumulation, or catamorphism, is a type of higher-order function that recursively applies a transformation to a data structure, "collapsing" it to a summary value

In functional programming, a fold, also known variously as , accumulation, or catamorphism, is a type of higher-order function that recursively applies a transformation to a data structure, "collapsing" it to a summary value.

1159 questions
218
votes
8 answers

difference between foldLeft and reduceLeft in Scala

I have learned the basic difference between foldLeft and reduceLeft foldLeft: initial value has to be passed reduceLeft: takes first element of the collection as initial value throws exception if collection is empty Is there any other difference…
Rajesh Pitty
  • 2,823
  • 2
  • 18
  • 28
202
votes
3 answers

Reduce, fold or scan (Left/Right)?

When should I use reduceLeft, reduceRight, foldLeft, foldRight, scanLeft or scanRight? I want an intuition/overview of their differences - possibly with some simple examples.
Marc Grue
  • 5,865
  • 3
  • 16
  • 23
201
votes
7 answers

Difference between fold and reduce in Kotlin, When to use which?

I am pretty confused with both functions fold() and reduce() in Kotlin, can anyone give me a concrete example that distinguishes both of them?
TapanHP
  • 5,969
  • 6
  • 37
  • 66
174
votes
8 answers

What is the 'pythonic' equivalent to the 'fold' function from functional programming?

What is the most idiomatic way to achieve something like the following, in Haskell: foldl (+) 0 [1,2,3,4,5] --> 15 Or its equivalent in Ruby: [1,2,3,4,5].inject(0) {|m,x| m + x} #> 15 Obviously, Python provides the reduce function, which is an…
mistertim
  • 5,123
  • 4
  • 20
  • 27
169
votes
7 answers

Implications of foldr vs. foldl (or foldl')

Firstly, Real World Haskell, which I am reading, says to never use foldl and instead use foldl'. So I trust it. But I'm hazy on when to use foldr vs. foldl'. Though I can see the structure of how they work differently laid out in front of me, I'm…
J Cooper
  • 16,891
  • 12
  • 65
  • 110
142
votes
5 answers

Difference between fold and reduce?

Trying to learn F# but got confused when trying to distinguish between fold and reduce. Fold seems to do the same thing but takes an extra parameter. Is there a legitimate reason for these two functions to exist or they are there to accommodate…
Wallace
  • 5,319
  • 4
  • 17
  • 9
134
votes
4 answers

foldl versus foldr behavior with infinite lists

The code for the myAny function in this question uses foldr. It stops processing an infinite list when the predicate is satisfied. I rewrote it using foldl: myAny :: (a -> Bool) -> [a] -> Bool myAny p list = foldl step False list where …
titaniumdecoy
  • 18,900
  • 17
  • 96
  • 133
110
votes
4 answers

How do you know when to use fold-left and when to use fold-right?

I'm aware that fold-left produces left-leaning trees and fold-right produces right-leaning trees, but when I reach for a fold, I sometimes find myself getting bogged down in headache-inducing thought trying to determine which kind of fold is…
Jeff
  • 14,831
  • 15
  • 49
  • 59
98
votes
4 answers

Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)?

Why do Scala and frameworks like Spark and Scalding have both reduce and foldLeft? So then what's the difference between reduce and fold?
samthebest
  • 30,803
  • 25
  • 102
  • 142
92
votes
11 answers

How does foldr work?

Can anybody explain how does foldr work? Take these examples: Prelude> foldr (-) 54 [10, 11] 53 Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6] 12.0 I am confused about these executions. Any suggestions?
dinsim
  • 2,395
  • 5
  • 24
  • 32
84
votes
7 answers

foldl is tail recursive, so how come foldr runs faster than foldl?

I wanted to test foldl vs foldr. From what I've seen you should use foldl over foldr when ever you can due to tail reccursion optimization. This makes sense. However, after running this test I am confused: foldr (takes 0.057s when using time…
Ori
  • 4,961
  • 10
  • 40
  • 39
82
votes
10 answers

Writing foldl using foldr

In Real World Haskell, Chapter 4. on Functional Programming: Write foldl with foldr: -- file: ch04/Fold.hs myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f z xs = foldr step id xs z where step x g a = g (f a x) The above code confused me a…
ylzhang
  • 1,108
  • 1
  • 8
  • 13
73
votes
5 answers

Left and Right Folding over an Infinite list

I have issues with the following passage from Learn You A Haskell (Great book imo, not dissing it): One big difference is that right folds work on infinite lists, whereas left ones don't! To put it plainly, if you take an infinite list at some…
TheIronKnuckle
  • 7,224
  • 4
  • 33
  • 56
71
votes
6 answers

How to fold/unfold HTML tags with Vim

Is there some plugin to fold HTML tags in Vim? Or there is another way to setup a shortcut to fold or unfold html tags? I would like to fold/unfold html tags just like I do with indentation folding.
nsbm
  • 5,842
  • 6
  • 30
  • 45
71
votes
1 answer

Haskell - foldl and foldr?

Is difference between foldl and foldr just the direction of looping? I thought there was a difference in what they did, not just in the direction?
Lethi
  • 1,167
  • 1
  • 10
  • 16
1
2 3
…
77 78