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