What is the name of the reduce operator on lists in ATS?

Question

Say I want to sum up the integers in a list. I can do this by applying the reduce operator on the list with the initial value 0 and the addition function. What is the name of the reduce operator in ATS?

Answer 1

The name 'reduce' is a bit ambiguous. It could mean either reduceLeft or reduceRight. In ATS, 'reduce' is called 'fold'. There are 'foldleft' and 'foldright', where the former is tail-recursive but the latter is not. For instance, sumup can be implemented as follows:

//
fun
sumup(xs: list0(int)): int =
  (xs).foldleft(TYPE{int})(0, lam(r, x) => r+x)
//
// If dot-notation is to be spared, please write:
fun
sumup(xs: list0(int)): int =
   list0_foldleft<int><int>(xs, 0, lam(r, x) => r+x)
//

One can also use foldright:

fun
sumup(xs: list0(int)): int =
  (xs).foldright(TYPE{int})(lam(r, x) => r+x, 0)

but this version of sumup can potentially cause stack overflow if xs is a very long list (e.g., containing 1 million elements).