Yes the code you are suggesting is certainly linear and it takes without doubt time n.<br>But I was looking for a solution using foldl that of course takes time n.<br>The problem of the following solution is that it gives a reversed result, and of course i can't just reverse the result.
<br><br>couples = snd . foldl f (0,[])<br> where<br> f (s,[]) x = (s+x, [(x,0)])<br> f (s,xs) x = (s+x, (:) (x,s) xs)<br><br>Clare<br><br><div><span class="gmail_quote">2006/11/17, Valentin Gjorgjioski <
<a href="mailto:valentin.gjorgjioski@ijs.si">valentin.gjorgjioski@ijs.si</a>>:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">On 17.11.2006
21:04 Clare wrote:<br>> I'm not sure it takes time n couse of the operator ++ and the lazy<br>> stuffs in haskell.<br>Ok, you can use<br>buildCouples (x:xs) s = (x,s) : (buildCouples xs (x+s))<br>instead of ++<br><br>
this algorithm is linear, I don't know why(?) you think it is not.<br><br>Valentin<br><br>--<br>Valentin Gjorgjioski<br>Bachelor of Computer Science<br>Department of Knowledge Technologies, Jozef Stefan Institute<br>Jamova 39, SI-1000 Ljubljana, Slovenia
<br>Phone: +386 1 477 3343<br>Fax: +386 1 477 3315<br>Web: <a href="http://kt.ijs.si/ValentinGjorgjioski/">http://kt.ijs.si/ValentinGjorgjioski/</a><br>Email: <a href="mailto:Valentin.Gjorgjioski@ijs.si">Valentin.Gjorgjioski@ijs.si
</a><br><br></blockquote></div><br>