[Haskell-cafe] working with lists of couples
Clara Zamolo
zacara at gmail.com
Fri Nov 17 13:29:25 EST 2006
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?
Thanks,
Clare.
More information about the Haskell-Cafe
mailing list