Fix off-by-one bug in `range/fold*`

[samosica]

range/fold(start, end, init, f) is described as follows:

https://github.com/koka-lang/koka/blob/f48555f1e2ba211f3e86524a15668597cad19118/lib/std/core.kk#L157

But end is not actually included. For instance, range/fold(1, 3, 0, (+)) is expected to evaluate to 6 (= 1+2+3), but it evaluates to 3 (= 1+2) (in version 3.0.4). The same issue exists in range/fold-while.

This PR fixes the off-by-one bug.

Note: perhaps I should also fix fold-int* and fold-while-int* (* = 32 or 64) for consistency. However these functions do not have spec comments and I am not certain of the expected behavior. Moreover some programs in this repository expect them to end with end - 1 (not end).

Examples:

https://github.com/koka-lang/koka/blob/f48555f1e2ba211f3e86524a15668597cad19118/lib/std/num/random.kk#L57 https://github.com/koka-lang/koka/blob/f48555f1e2ba211f3e86524a15668597cad19118/test/fip/src/tmap/tmap-fip.kk#L40

[TimWhiting]

Yeah, this is something Daan @daanx would have to weigh in on. I don't know if we need to change the implementation to match the documentation or the documentation to match the implementation. It would probably be good to have both versions. Maybe a fold-to or something for the inclusive version? Not sure about the naming.

[daanx]

Yikes -- such an embarrassing bug. I have been a bit on the fence whether to include the end in ranged folds and went back and forth a few times. It is a bit weird to include end since languages like C never include it (ranging from 0 to end-1).
In Koka the idea is to have that using a regular for which has just an n argument and range from 0 to n-1 (as in C). And we also have range/for etc. which have a start and end and are inclusive -- for example, with list(1,10) you get the list [1..10]. Still I feel a bit hesitant about it though as it feels inconsistent to some degree... I'll make up my mind soon but for now include your fix so the documentation matches implementation :-)

[anfelor]

FWIW, in Python the end is exclusive, which seems to be due to the parallel to subsequencing a[i:j], where j is exclusive. See also this discussion and GvR's opinion

[daanx]

Thanks @anfelor ! Fun to read that. However the discussion in Python land is a bit different though -- there is no disagreement we should index starting at 0 (see also https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF). So the bare for and fold-int take just an n and iterate over the integer 0 to n-1. It is the ranged versions that take a start and end where it is perhaps less clear cut. I am thinking mostly of list(1,10) which I often use in examples for the list [1..10] (in Haskell (inclusive!!) notation). Currently (with end inclusive) we have: list(1,10).sum = range/fold-int(1,10, 0, (+) ). And if we range over an array, we can write that without a start element for a total count: fold-int( a.length, 0, fn(acc,i) acc + a[i] ) where i ranges between 0 and a.length-1 (included).
So, if we decide to be not inclusive at the end, we should probably adapt list as well to return the list [1..9] for list(1,10). Mmm

(maybe for the next release I make the ranged functions private so we buy ourselves some time :-) I guess these functions are just not used much in typical Koka code as we usually do not index but directly fold over inductive structures anyways)