SML track list-ops exercise has foldl wrong

Exercism Bugs & Feature Requests
1

In Standard ML, foldl doesn’t flip the order of operands vs foldr. It’s always operand from list first, then init or accumulator second, whether folding left or right. From the Standard ML Basis (and every textbook I’ve looked at):

foldl f init [x1, x2, ..., xn]
returns

f(xn,…,f(x2, f(x1, init))…)

or init if the list is empty.

foldr f init [x1, x2, ..., xn]
returns

f(x1, f(x2, …, f(xn, init)…))

or init if the list is empty.

(In Haskell, and maybe elsewhere, they flip, right? If this exercise is also in the Scheme track, it should probably be checked too, since it seems Scheme is like SML here.)

Thus foldl (op div) 5 [2, 5] (one of the test cases – but with the arguments as a tuple instead of curried) raises an exception for division by zero, but the test expects this to yield 0. The evalution goes 2 div 5 = 0, then 5 div 0, exception; not 5 div 2 = 2, then 2 div 5 = 0.

You can pass the tests if you write Haskell’s foldl instead SML’s, but that seems like a bad idea since the definition of Standard ML is famously not up for grabs.

2

Yes, in the Haskell language family in foldl we have f :: b -> a -> b, whereas apparently SML has f :: a -> b -> b.

The example solution uses the Haskell order. But as you already noted all requested functions are uncurried, so emulation of standard SML is out anyway.

This exercise was added in add list-ops, update generator and simplify difference-of-squares by snahor · Pull Request #74 · exercism/sml · GitHub, without documentation of reasoning. I don’t think the participants are active on this forum.

For some on the history of the design choices behind Haskell’s and ML’s foldl, see

3

Thanks for that. Some interesting stuff there. Another language that would have gotten the idea from Lisp is Smalltalk. The Squeak sources have this:

inject: thisValue into: binaryBlock 
	"Accumulate a running value associated with evaluating the argument, 
	binaryBlock, with the current value of the argument, thisValue, and the 
	receiver as block arguments. For instance, to sum the numeric elements 
	of a collection, aCollection inject: 0 into: [:subTotal :next | subTotal + 
	next]."

	| nextValue |
	nextValue := thisValue.
	self do: [:each | nextValue := binaryBlock value: nextValue value: each].
	^nextValue

So the Smalltalk way is to always present the arguments as init/accumulator first, collection member second – I guess anything at all could happen within binaryBlock, but I didn’t notice any sign of the left/right distinction.

Maybe the problem is just that this part of the exercise’s instructions turns out to be false:

The precise number and names of the operations to be implemented will be track dependent to avoid conflicts with existing names

SML includes length, map, filter, foldl, and foldr. No conflict with @, concat, or rev, but 5 out of 8 do conflict, and clobber the Standard Basis versions. (Which I discovered by working on the code in the toplevel and then trying to run the tests: you can’t because testlib.sml uses the standard foldr!)

If, for instance, you had to implement applyToAll or whatever, with a note that the library has something similar called map, then of course you could change the order of arguments, tuple them, whatever.

On the other hand, as your citation makes clear, the order of arguments for foldl is not quite a non-issue in functional programming: I expect Haskell people would be pretty annoyed if an exercise here casually reversed the decision of the Haskell community and implementers, who clearly put some thought into it, just as the ML and Scheme communities did.

Eh, I’ve blathered enough. Thanks for your thoughts.