# Writing Fold in terms of Map or MapThread?

Consider

Fold[f,z,{a,b,c}]
==> f[f[f[z,a],b,c]]


I'm looking for a way to write this (in general) using Map or MapThread (and perhaps Flatten[#,1]&, thinking of monadic bind a-la Haskell), and not using mutable variables. In other words, the following is too easy:

Module[{result = z},
Map[v \[Function]
result = f[result, v],
{a, b, c}]] // Last


and the following is not even wrong:

MapThread[f, {{z, f[z, a], f[f[z, a], b]}, {a, b, c}}] // Last


and the following is even more not even wrong (invoking Haskell's state monad); although it could be written recursively to be more general, the recursive form would just be a simulacrum of Fold with more functional garbage around the binding functions:

return[v_] := s \[Function] {v, s};
bind[m_, fv2m_] := s \[Function]
With[{vs0 = m[s]},
With[{
v0 = vs0[[1]],
s0 = vs0[[2]]},
fv2m[v0][s0]]]

bind[
bind[
bind[
return[z],
v \[Function] return[f[v, a]]],
v \[Function] return[f[v, b]]],
v \[Function] return[f[v, c]]][z] // First


I'm beginning to think that Fold is its own critter, kind of a state-monad-in-disguise, inherently recursive, and not representable by Map and friends, which are inherently iterative. But I haven't yet been able to prove that it's not possible, even though I haven't found a solution.

Anyone happen to know?

EDIT: the reason I'm looking for this is so I can build a reactive version around the Observable/Observer pattern, which is formally dual to the Iterable/Iterator pattern, and replaces Map with Subscribe, sort-of. I do not know a reactive partner to Fold, and that's the ultimate objective.

• I would like to help but I don't understand the computer science jargon. You can only use Map, MapThread, etc? Something recursive won't do the trick? Like fold[fun_, lhs_, {}] := lhs; fold[fun_, lhs_, {next_, rest___}] := fold[fun, fun[lhs, next], {rest}]; – Rojo Dec 22 '13 at 4:27
• Sorry to be ignorant, but what is Subscribe and what do you mean by reactive? – Mr.Wizard Dec 22 '13 at 6:53
• I'm sorry but what do you mean by subscribe, observable and observer? The only observable/observer I learnt are from quantum mechanic, and I'm pretty sure those have nothing to do with your question.. :( – Silvia Dec 22 '13 at 11:24
• If we think of {a, b, c} as a sequence of values distributed in memory, i.e., an "Iterable", then Map or ForEach is a higher-order function that applies another function f to the values, iteratively, by invoking an "Iterator". If we think of {a, b, c} as a sequence of values distributed in time, i.e., an "Observable", then Subscribe is a higher-order function that applies another function f to the values in callback fashion, and we call f an "Observer". Take a look here stanford.io/1kw535m – Reb.Cabin Dec 22 '13 at 13:40
• I'm working out an Observable/Observable pair in MMA similar to the Enumerable/Enumerator (i.e., Iterable/Iterator) pair I already worked out here bit.ly/1jwoVYa, with a view to doing online, incremental statistics, along these lines bit.ly/18GcHr5 – Reb.Cabin Dec 22 '13 at 13:51

If you accept to use function composition, you might use something like this:

g = Composition @@ (Function /@ MapThread[f, {{#, #, #}, Reverse@{a, b, c}}]);
g[z]


which is equal to Fold[f, z, {a, b, c}].

• Composition and Apply are definitely acceptable. I'm digesting this proposal some more; looks brilliant to me. – Reb.Cabin Dec 22 '13 at 14:18
• Noting also that we accomplish a right-fold by Composition@@(Function/@MapThread[Flip@f,{{#,#,#},{a,b,c}]) where Flip[f_]:={x,y}\[Function]f[y,x]. Applied to z, we get f[a,f[b,f[c,z]]] – Reb.Cabin Dec 22 '13 at 15:21
• Ok, here is a version that is pure functional and requires no rewriting tricks: Apply[Composition, Map[v \[Function] x \[Function] f[x, v], Reverse@{a, b, c}]][z] – Reb.Cabin Dec 22 '13 at 18:14

I've discovered a few more things about this, so I am putting my response at top level so that it doesn't get ignored in comments, even though @user8074 absolutely gave me the ice-breaking idea. I now believe that

(Composition @@ Function[v, Function[x, f[v, x]]] /@ {a, b, c})@z


that is,

Apply[Composition, Map[Function[v, Function[x, f[v, x]]], {a, b, c}]][z]


is exactly

FoldRight[f, z, {a, b, c}]


where

FoldRight[f_, z_, l_List] := Fold[Flip@f, z, Reverse@l]


and

Flip[f_] := Function[{x, y}, f[y, x]]


Note also that

Fold[f, z, l] === FoldRight[Flip@f, z, Reverse@l]


for any particular l, so FoldRight and Fold are symmetric, and Fold could be called FoldLeft.

I checked with some people and I think that it was thought to be impossible to express Fold in terms of Map, although this combination of Map, Composition, and Apply may be novel. I will continue to post here as I learn more from colleagues.

• @Red.Cabin actually, there is a difference between FoldRight and the version with Composition. The latter acts explicitely on the variable z while, in the former version, all the argurments are on the same footing. To some extent it seems like having "curried" FoldRight – user8074 Dec 22 '13 at 20:48
• I fixed my post (I forgot to include z :) I am pretty sure that FoldRight[f_,z_,l_List]:=(Composition@@Function[v,Function[x,f[v,x]]]/@l)@z is exactly Haskell's foldr (see stackoverflow.com/questions/3950508/…). I am pretty sure I can make it work on infinite, lazy lists, too. – Reb.Cabin Dec 23 '13 at 13:59
• @Reb.Cabin but Composition is a kind of fold when it is applied to a sequence of several arguments (traditionally function composition is a function of exactly 2 arguments and this is probably what a mathematician would understand by it). I think you'd need to post a more mathematical question in a different forum such as SX Mathematics if you want a precise answer to the question of expressivity of Map. – fairflow Apr 28 '14 at 10:45