I'm struggling with this one because I'm unsure how to implement it recursively (I can do it imperatively).
The prefix-sum of a list l is a list s where the ith index element of s is the sum of the first i + 1 elements of l.
I have to use the addToEach function, which I've written as follows:
fun addToEach(number : int, nil : int list) : int list = nil
| addToEach(number : int, x::y : int list) =
(x + number)::addToEach(number, y);
What I'd like to do is loop through my list l and, suppose I'm at index j, add the number at index j to all elements 0 - (j-1) in my list s. Not really sure how to do this recursively, though.
Thanks for the help!
The point it to add the number at a given index to the rest of the list (to index j+1,j+2,... rather than 0,...,j-1):
fun prefixSum [] = []
| prefixSum (x::xs) = x::addToEach(x, prefixSum xs);
Here is a way without addToEach which uses a tail-recursive helper function:
fun prefixSum' (sums, []) = sums
| prefixSum' ([], x::xs) = prefixSum' ([x],xs)
| prefixSum' (y::ys, x::xs) = prefixSum' ((x+y)::y::ys,xs);
For example, prefixSum' [2,3,4,5] = [14,9,5,2] -- which is backwards (a common problem when you built up a list with a tail-recursive function). So -- just reverse it in the main function:
fun prefixSum xs = rev (prefixSum'([],xs));