[Haskell-cafe] working with lists of couples

[Valentin Gjorgjioski]

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