Beginners in functional programming (FP) who have already acquired some knowledge of imperative programming often ask about ways to construct for-loops and while-loops in FP. A commonly given answer is that loop constructs are unnecessary in FP as they can be readily replaced with higher-order functions. Let us first see some thorny issues with this answer.
The following code in C implements a function that returns the sum of the first n natural numbers when applied to a natural number n:
This function tally can be given the following equivalent implementation in ATS:fun tally ( n: int ) : int = loop (0, 0) where { fun loop (i: int, res: int): int = if i < n then loop (i + 1, res + i) else res }
When someone claims that loop constructs can be replaced with higher-order functions, he or she probably means to construct loops with a function like the following one:
fun for_loop ( count: int, limit: int, fwork: (int) -<cloref1> void ) : void = ( // if count < limit then (fwork(count); for_loop(count+1, limit, fwork)) else () // end of [if] ) (* end of [for_loop] *)
fun tally2 ( n: int ) : int = let val res = ref<int> (0) in for_loop (0, n, lam (i) => !res := !res + i); !res end // end of [tally2]
To eliminate the need for reference creation in tally2, we turn for_loop into the following function template for_loop2:
// fun{ env:t@ype } for_loop2 ( count: int, limit: int , env: &env >> _, fwork: (int, &env >> _) -<cloref1> void ) : void = ( // if count < limit then ( fwork(count, env); for_loop2<env> (count+1, limit, env, fwork) ) else () // end of [if] // ) (* end of [for_loop2] *)
fun tally3 ( n: int ) : int = let var res: int = 0 in for_loop2<int> (0, n, res, lam (i, res) => res := res + i); res end // end of [tally3]
fun{ env:t@ype } for_loop3 ( count: int, limit: int, env: &env >> _ ) : void = ( // if count < limit then ( for_loop3$fwork<env>(count, env); for_loop3<env>(count+1, limit, env) ) else () // end of [if] // ) (* end of [for_loop3] *)
fun tally4 ( n: int ) : int = let // var res: int = 0 // implement for_loop3$fwork<int> (i, res) = res := res + i // in for_loop3<int> (0, n, res); res end // end of [tally4]
By now, the reader probably agrees with me if I say the statement should at least be considered grossly inaccurate that claims loop constructs in FP can be readily replaced with higher-order functions. Please find on-line the file loopcons.dats containing the entirety of the code presented in this section plus some testing code.