What's the most efficient way to implement Haskell's foldl1 in J?

Question

In Haskell there are two functions that allow one to perform an operation on a list of items in order to reduce it to a single value. (There are more than two, of course, but these are the two I'm interested in.) They are foldl1 and foldr1. If the operation to be performed is commutative (such as addition), it doesn't matter which of these you use. The result will be the same. However, if the operation is not commutative (e.g., subtraction), then the two produce very different results. For example:

foldr1 (-) [1..9]
foldl1 (-) [1..9]

The answer to the first one is 5 and to the second, -43. The J equivalent of foldr1 is the insert adverb, /, e.g.,

-/ 1+i.9

which is the equivalent of foldr1 (-) [1..9]. I want to create an adverb in J that works like the insert adverb, but folds left instead of right. The best I could come up with is the following:

foldl =: 1 : 'u~/@|.'

Thus, one could say:

- foldl 1+i.9

and get -43 as the answer, which is what is expected from a left fold.

Is there a better way to do this in J? For some reason, reversing the y argument does not seem efficient to me. Perhaps there is a way to do this without having to resort to that.

Answer 1

I don't think there is a better way to fold left than that you describe:

(v~) / (|. list)

It is a very natural way, an almost "literal" implementation of the definition. The cost of reversing the list is very small (imo).

The other obvious way of implementing the left fold is to set

new_list = (first v second) v rest

eg:

foldl_once =: 1 :'(u / 0 1 { y), (2}. y)'
foldl =: 1 :'(u foldl_once)^:(<:#y) y'

so:

- foldl >:i.9
_43

but your way performs much better than this both in space and time.

Answer 2

   ($:@}:-{:)^:(1<#) 1+i.9
_43

No idea if it's any more (or less) efficient.