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.

On 17.11.2006 19:29 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). time n = time 2*n because of O(n)=O(2*n)

So, this algorithm should work fine for you buildCouples :: [Int]->Int->[(Int,Int)] buildCouples (x:[]) s = [(x,s)] buildCouples (x:xs) s = [(x,s)] ++ (buildCouples xs (x+s)). buildCouples [1,2,3,4,5,6] 0 [(1,0),(2,1),(3,3),(4,6),(5,10),(6,15)] Valentin