17 Nov
2006
17 Nov
'06
1:39 p.m.
On Fri, 17 Nov 2006, Clara Zamolo wrote:
Hello, i'd like to write a function that given a list like [1,2,3,4...] returns a list of couple where the first element is the corresponding element of the string, and the second is the sum of the previous elements. An example: input: [1,2,3,4] output: [(1,0)(2,1)(3,3)(4,6)]
The problem could seem trivial, and here's a first solution:
buildCouples = snd . foldl op (0,[]) where op (v,xs) x = (v+x,xs++[(x,v)])
The problem is that this solution is quadratic, and I want a solution that take time n (2n is not good either).
Any suggestion?
I suggest using 'scanl' and then 'zip' the result together with the original list.