Re: [Haskell-cafe] working with lists of couples
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
Re: [Haskell-cafe] working with lists of couples
On 11/17/06, Henning Thielemann [EMAIL PROTECTED] wrote: On Fri, 17 Nov 2006, Clara Zamolo wrote: buildCouples = snd . foldl op (0,[]) where op (v,xs) x = (v+x,xs++[(x,v)]) You could make something like this that doesn't have quadratic-type appends by accumulating functions instead of lists: Prelude snd (foldl (\(s,f) x - (x+s,f . ((x,s):))) (0,id) [1..6]) [] [(1,0),(2,1),(3,3),(4,6),(5,10),(6,15)] but this is better: I suggest using 'scanl' and then 'zip' the result together with the original list. Or, equivalently, use mapAccumL from the Data.List library: Prelude Data.List snd $ mapAccumL (\s x - (s + x,(x,s))) 0 [1..6] [(1,0),(2,1),(3,3),(4,6),(5,10),(6,15)] /g ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] working with lists of couples
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] working with lists of couples
On Fri, 17 Nov 2006, 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). Any suggestion? I suggest using 'scanl' and then 'zip' the result together with the original list. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] working with lists of couples
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] working with lists of couples
On 17.11.2006 19:51 Valentin Gjorgjioski wrote: 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)). Please ignore the . at the end, it is a typo :( Sorry again... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
