2009/5/13 Raul Miller <[email protected]>:
> I believe APL's reduce predates fold (and was probably the
> inspiration for fold).
That's for sure. A notable example is FP's combining form named
(differently from APL and the same way as J now) ‘insert’: for a
function f, /f inserts f in a sequence. In turn, many later
functional languages were partly influenced by Backus's FP, thus
ultimately by APL.
> But since operations on arrays are
> so foreign to other languages, people sort of jammed a
> lot of "related-seeming" features into fold because the
> languages which would be implementing fold could not
> provide them.
That is possible in principle, but I am not sure what specific
features you mean. Could you give an example?
And although J surely has no equals as far as array manipulation
is concerned, the variety of folds and fold-related features in
other languages cannot be explained by just saying ‘they can't do
arrays properly’.
The real source of diversity seems to be that, in deciding what
a fold is, at least the following issues are involved:
• assymetry of lists (efficiency issues arising thereof);
• lazyness;
• infiniteness of lists;
• datatype-related issues (arrays/lists and functions on them
may have types);
• issues concerning initial values vs. neutral elements of
the operation being applied.
> J, on the other hand, can reverse the direction of processing
> (in two senses of the word, yielding four possibilities
> involving reversal or not).
> ..........................
> ;~/@|.2 3 5
> ..........................
I don't see this as a feature unique to J. There is hardly a
language that has (or can implement) a fold but not reverse,
for whatever kind of sequences it happens to deal with. So
doing foldl through composing foldr over reverse is easy in
any language once it has foldr. In fact, there are (as mentioned
above) other reasons why many languages have both foldl and foldr.
As for flipping the two arguments of a function, this too is
trivial in any functional language.
> Also, for any well behaved function, the initial value
> can be supplied in the list itself.
Yes, but that often leads to certain inconveniences, e.g. having
to unbox/box the current result within every application of the
inserted function (consider inserting over a numeric list with
an initial value an array).
(I find K more convenient in this respect. Its ‘over dyad’
adverb does allow specifying an initial value.)
> Anyways, according to the wiki page, fold is a
> family of higher-order functions, so technically
> speaking no language ever implements fold --
> instead, each language implements members
> of the fold family.
A fairly complete coverage of all variants in one function is
Common Lisp's reduce:
http://www.lispworks.com/documentation/HyperSpec/Body/f_reduce.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
