3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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}]; $\endgroup$ – Rojo Dec 22 '13 at 4:27
  • 2
    $\begingroup$ Sorry to be ignorant, but what is Subscribe and what do you mean by reactive? $\endgroup$ – Mr.Wizard Dec 22 '13 at 6:53
  • 1
    $\begingroup$ 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.. :( $\endgroup$ – Silvia Dec 22 '13 at 11:24
  • 1
    $\begingroup$ 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 $\endgroup$ – Reb.Cabin Dec 22 '13 at 13:40
  • 1
    $\begingroup$ 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 $\endgroup$ – Reb.Cabin Dec 22 '13 at 13:51
4
$\begingroup$

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}].

$\endgroup$
  • $\begingroup$ Composition and Apply are definitely acceptable. I'm digesting this proposal some more; looks brilliant to me. $\endgroup$ – Reb.Cabin Dec 22 '13 at 14:18
  • $\begingroup$ 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]]] $\endgroup$ – Reb.Cabin Dec 22 '13 at 15:21
  • $\begingroup$ 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] $\endgroup$ – Reb.Cabin Dec 22 '13 at 18:14
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @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 $\endgroup$ – user8074 Dec 22 '13 at 20:48
  • $\begingroup$ 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. $\endgroup$ – Reb.Cabin Dec 23 '13 at 13:59
  • 1
    $\begingroup$ @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. $\endgroup$ – fairflow Apr 28 '14 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.