[Haskell-cafe] working with lists of couples

[Clare]

Yes the code you are suggesting is certainly linear and it takes without
doubt time n.
But I was looking for a solution using foldl that of course takes time n.
The problem of the following solution is that it gives a reversed result,
and of course i can't just reverse the result.

couples = snd . foldl f (0,[])
    where
        f (s,[]) x = (s+x, [(x,0)])
        f (s,xs) x = (s+x, (:) (x,s) xs)

Clare

2006/11/17, Valentin Gjorgjioski <valentin.gjorgjioski at ijs.si>:
>
> On 17.11.2006 21:04 Clare wrote:
> > I'm not sure it takes time n couse of the operator ++ and the lazy
> > stuffs in haskell.
> Ok, you can use
> buildCouples (x:xs) s = (x,s) : (buildCouples xs (x+s))
> instead of ++
>
> this algorithm is linear, I don't know why(?) you think it is not.
>
> Valentin
>
> --
> Valentin Gjorgjioski
> Bachelor of Computer Science
> Department of Knowledge Technologies, Jozef Stefan Institute
> Jamova 39, SI-1000 Ljubljana, Slovenia
> Phone:  +386 1 477 3343
> Fax:    +386 1 477 3315
> Web:    http://kt.ijs.si/ValentinGjorgjioski/
> Email:  Valentin.Gjorgjioski at ijs.si
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20061123/886bb26e/attachment.htm