Intuition behind FoldPair and SequenceFold?
Fold[f, u, list]
is Nest[f, u, n]
with in addition the possibily to inject in f
a value from list
at each iteration.
That is to say, at each iteration, the input of f
is feed with :
- the preceding output of
f
exactly - a value of
list
.
FoldPair
is designed to reinject a value that is different from the exact ouput of f
.
That is to say, at each iteration, the input of f
is feed with :
- the first part of output of
f
. Indeed, the use ofFoldPair
assumes thatf
returns a pair of data. - a value of
list
.
It is easy to implement FoldPair
with Fold
, but the syntax is not straightforward to understand.
The problem with FoldPair
is that it is not very clear too.
FoldPair[{p[#1, #2], q[#1, #2]} &, u, {1, 2, 3, 4}]
p[q[q[q[u, 1], 2], 3], 4]
FoldPair
implemented with Fold
:
First @ Fold[{p[#1[[1]], #2], q[#1[[1]], #2]} &, {u,}, {1, 2, 3, 4}]
p[q[q[q[u, 1], 2], 3], 4]
That's the main ideas. The rest is a matter of ordering and desencapsulation of a pair of data in a List
(choice beetween f[#1,#2] @@ {data1,data2}
or f[#[[1]],#[[2]]] @ {data1,data2}
.
FoldPairList
is the list of the successives outputs that FoldPair
would give for each sublist.
FoldPair
is a special case of FoldPairList
that discards all but the last element, so we should first create intuition for FoldPairList
.
Understanding FoldPairList
FoldPairList
either "slices off from" or "builds up" an intermediate result. I will use an example from the v12.0 documentation to illustrate each paradigm.
"Slicing off"
Break an amount of money into bills of given values:
FoldPairList[QuotientRemainder, 498, {100, 50, 20, 5, 1}] (* {4, 1, 2, 1, 3} *)
QuotientRemainder
is equivalent to {Quotient@##, Remainder@##}&
. Here, FoldPairList
outputs the Quotient
at each step, passing the Remainder
to the next value of f
. Generalizing:
In FoldPairList[f, y0, {a1, ..., an}]
,
f
is of the form{result[#,#2], remainder[#,#2]}&
, whereresult
andremainder
are two closely related functions.- At each iteration,
f
uses an elementai
to "slice off" aresult
and passes theremainder
to the next iteration. FoldPairList
returns all of the slices.FoldList
returns theremainder
after taking each slice.FoldPair
returns the last slice (it's rare that you need just this).Fold
returns the scraps left after the last slice is taken.
"Building up"
For each element of a list, return True if it is larger than all previous ones, and False otherwise:
FoldPairList[{#2 > #1, Max[#1, #2]} &, {1, 1, 2, 5, 2, 2, 9, 1, 2, 11}] (* {False, True, True, False, False, True, False, False, True} *)
At each step, FoldPairList
outputs whether #2
is greater than the accumulator, and sets the accumulator to Max[accumulator, #2]
. Generalizing:
f
is of the form{result[#,#2], combine[#, #2]}
.- At each iteration,
f
outputs someresult
, andcombine
s an elementai
into the accumulator. FoldPairList
returns all of the outputs.FoldList
returns each value of the accumulator.FoldPair
returns the last output.Fold
returns the final value of the accumulator.
Examples
Almost every use of FoldPairList
I could find follows either the "slicing off" pattern or the "building up" pattern.
With
TakeDrop
(a common idiom beforeTakeList
was introduced)- Slice off
Take[#,#2]
, the first#2
elements of a list. - Keep
Drop[#,#2]
, the rest of the list.
- Slice off
With
pickPair
pickPair does the following.
Removes the restricted value from the sample space.
Converts the sample space such any remaining items will not be picked twice.
With
{f[#2] - Count[#, #2], Append[#, #2]} &
- Output
f[#2] - Count[#,#2]
, the adjusted count of a variable#2
in an expression. - "Build up" the expression by appending
#2
.
- Output
With
{Abs@Total[#2 - #1], #2} &
:- Output the diagonal distance between a point and the accumulator.
- Set the accumulator to the next point.
- This does not use the full power of
FoldPairList
, and so can be written asBlockMap[...,2]
in modern Mathematica.
Say you earn a certain income and pay federal, state, and local tax in that order, by some function
f[remainingIncome, taxRate]
.FoldPairList[{f@##, #2-f@##}&, grossIncome, taxRates]
is how much you owe in each tax.FoldList[#2-f@##&, grossIncome, taxRates]
is your remaining income after each tax is applied.FoldPair[{f@##, #2-f@##}&, grossIncome, taxRates]
is you how much you owe in local tax.Fold[#2-f@##&, grossIncome, taxRates]
is your net income.
Conclusions
It is not surprising that FoldPairList
is mysterious to many people. We usually think of Fold
in the "building up" paradigm, whereas FoldPairList
is most often useful in the "slicing off" paradigm.
FoldPair
is even more obscure since one typically does not need the last result by itself in either the "building up" or "slicing off" paradigm. Constructing a use case always seems contrived. For this reason, it seems FoldPair
exists mainly as a companion to FoldPairList
, FoldList
, and Fold
, rather than being useful in itself.