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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe