Intuition behind FoldPair and SequenceFold?

Question

In trawling through the documentation I've found the functions FoldPairList and SequenceFoldList. Examples are given of how to use FoldPairList:

• Partition a list into sublists of different lengths using TakeDrop
• Break an amount of money into bills of given values using QuotientRemainder
• A discrete-time state-space system is represented using a state equation and output equation. (see wikipedia)

and for SequenceFoldList (both using Plus):

• an implementation of the Fibonacci sequence
• Show convergence to the exact solution when increasing the order of extrapolation.

These examples show some utility of these functions, but ultimately are not illuminating.

I'm looking for intuition behind these potentially useful functions.

It should be possible to view these functions through the paradigm of functional program (or Category Theory). In particular:

• Are these functions particular types of Catamorphism?
• Are these functions related to Tree-Like Folds?

I'm no expert in any of this stuff. My guess is that these functions are included in Mathematica more as utility functions used internally for implementing other functions.

Answer 1

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 of FoldPair assumes that f 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.

Answer 2

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]}&, where result and remainder are two closely related functions.
• At each iteration, f uses an element ai to "slice off" a result and passes the remainder to the next iteration.
• FoldPairList returns all of the slices.
• FoldList returns the remainder 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 some result, and combines an element ai into the accumulator.
• FoldPairList returns all of the outputs.
• FoldList returns each value of the accumulator.
• FoldPairreturns 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 before TakeList was introduced)

  • Slice off Take[#,#2], the first #2 elements of a list.
  • Keep Drop[#,#2], the rest of the list.

• With pickPair

pickPair does the following.

1. Removes the restricted value from the sample space.

2. 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.

• 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 as BlockMap[...,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.