Branimir Maksimovic | 28 Nov 12:43 2012
Picon

How to incrementally update list

Problem is following short program:
list = [1,2,3,4,5]

advance l = map (\x -> x+1) l

run 0 s = s
run n s = run (n-1) $ advance s

main = do
        let s =  run 50000000 list
        putStrLn $ show s

I want to incrementally update list lot of times, but don't know
how to do this.
Since Haskell does not have loops I have to use recursion,
but problem is that recursive calls keep previous/state parameter
leading to excessive stack.and memory usage.
I don't know how to tell Haskell not to keep previous
state rather to release so memory consumption becomes
managable.

Is there some solution to this problem as I think it is rather
common?

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Benjamin Edwards | 28 Nov 13:07 2012
Picon

Re: How to incrementally update list

TCO + strictnesses annotations should take care of your problem.

On 28 Nov 2012 11:44, "Branimir Maksimovic" <bmaxa <at> hotmail.com> wrote:
Problem is following short program:
list = [1,2,3,4,5]

advance l = map (\x -> x+1) l

run 0 s = s
run n s = run (n-1) $ advance s

main = do
        let s =  run 50000000 list
        putStrLn $ show s

I want to incrementally update list lot of times, but don't know
how to do this.
Since Haskell does not have loops I have to use recursion,
but problem is that recursive calls keep previous/state parameter
leading to excessive stack.and memory usage.
I don't know how to tell Haskell not to keep previous
state rather to release so memory consumption becomes
managable.

Is there some solution to this problem as I think it is rather
common?


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Clark Gaebel | 28 Nov 14:01 2012
Picon
Picon

Re: How to incrementally update list

Here's a version that works:

import Control.DeepSeq

list = [1,2,3,4,5]

advance l = force $ map (\x -> x+1) l

run 0 s = s
run n s = run (n-1) $ advance s

main = do
        let s =  run 50000000 list
        putStrLn $ show s

The problem is that you build of a huge chain of updates to the list. If we just "commit" each update as it happens, we'll use a constant amount of memory.

Haskell's laziness is tricky to understand coming from imperative languages, but once you figure out its evaluation rules, you'll begin to see the elegance.

Ηope this helps,
  - Clark


On Wed, Nov 28, 2012 at 7:07 AM, Benjamin Edwards <edwards.benj <at> gmail.com> wrote:

TCO + strictnesses annotations should take care of your problem.

On 28 Nov 2012 11:44, "Branimir Maksimovic" <bmaxa <at> hotmail.com> wrote:
Problem is following short program:
list = [1,2,3,4,5]

advance l = map (\x -> x+1) l

run 0 s = s
run n s = run (n-1) $ advance s

main = do
        let s =  run 50000000 list
        putStrLn $ show s

I want to incrementally update list lot of times, but don't know
how to do this.
Since Haskell does not have loops I have to use recursion,
but problem is that recursive calls keep previous/state parameter
leading to excessive stack.and memory usage.
I don't know how to tell Haskell not to keep previous
state rather to release so memory consumption becomes
managable.

Is there some solution to this problem as I think it is rather
common?


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Branimir Maksimovic | 28 Nov 14:38 2012
Picon

Re: How to incrementally update list

Thank you very much! That solved it ;)
I had to put explicit type signature in front of advance in order to compile

From: cgaebel <at> uwaterloo.ca
Date: Wed, 28 Nov 2012 08:01:38 -0500
Subject: Re: [Haskell-cafe] How to incrementally update list
To: edwards.benj <at> gmail.com
CC: bmaxa <at> hotmail.com; haskell-cafe <at> haskell.org

Here's a version that works:

import Control.DeepSeq

list = [1,2,3,4,5]

advance l = force $ map (\x -> x+1) l

run 0 s = s
run n s = run (n-1) $ advance s

main = do
        let s =  run 50000000 list
        putStrLn $ show s

The problem is that you build of a huge chain of updates to the list. If we just "commit" each update as it happens, we'll use a constant amount of memory.

Haskell's laziness is tricky to understand coming from imperative languages, but once you figure out its evaluation rules, you'll begin to see the elegance.

Ηope this helps,
  - Clark


On Wed, Nov 28, 2012 at 7:07 AM, Benjamin Edwards <edwards.benj <at> gmail.com> wrote:

TCO + strictnesses annotations should take care of your problem.

On 28 Nov 2012 11:44, "Branimir Maksimovic" <bmaxa <at> hotmail.com> wrote:
Problem is following short program:
list = [1,2,3,4,5]

advance l = map (\x -> x+1) l

run 0 s = s
run n s = run (n-1) $ advance s

main = do
        let s =  run 50000000 list
        putStrLn $ show s

I want to incrementally update list lot of times, but don't know
how to do this.
Since Haskell does not have loops I have to use recursion,
but problem is that recursive calls keep previous/state parameter
leading to excessive stack.and memory usage.
I don't know how to tell Haskell not to keep previous
state rather to release so memory consumption becomes
managable.

Is there some solution to this problem as I think it is rather
common?


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Mark Thom | 30 Nov 19:16 2012
Picon

Re: How to incrementally update list


Haskell's laziness is tricky to understand coming from imperative languages, but once you figure out its evaluation rules, you'll begin to see the elegance.

Is there a paper or other single resource that will help me thoroughly understand non-strictness in Haskell? Once my programs hit a certain level of complexity, their behaviour becomes much harder for me to predict. I've been using the wiki pages up to this point, but apparently they haven't pushed my understanding of laziness nearly far enough.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Kim-Ee Yeoh | 30 Nov 21:01 2012

Re: How to incrementally update list

On Sat, Dec 1, 2012 at 1:16 AM, Mark Thom <markjordanthom <at> gmail.com> wrote:

> Is there a paper or other single resource that will help me thoroughly understand non-strictness in Haskell?

If performance is utterly vital the best resource is Core, as in, the ability to read it. The order of evaluation is all laid out there. Don [1] and Johan [2] have written variously about it.



-- Kim-Ee


On Sat, Dec 1, 2012 at 1:16 AM, Mark Thom <markjordanthom <at> gmail.com> wrote:

Haskell's laziness is tricky to understand coming from imperative languages, but once you figure out its evaluation rules, you'll begin to see the elegance.

Is there a paper or other single resource that will help me thoroughly understand non-strictness in Haskell? Once my programs hit a certain level of complexity, their behaviour becomes much harder for me to predict. I've been using the wiki pages up to this point, but apparently they haven't pushed my understanding of laziness nearly far enough.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Albert Y. C. Lai | 2 Dec 21:34 2012
Picon

Re: How to incrementally update list

On 12-11-30 01:16 PM, Mark Thom wrote:
> Is there a paper or other single resource that will help me thoroughly
> understand non-strictness in Haskell?

See my http://www.vex.net/~trebla/haskell/lazy.xhtml
Mark Thom | 3 Dec 01:09 2012
Picon

Re: How to incrementally update list

Thanks Albert, I believe that's the second time you've helped me this weekend. I'm meiji11 in #haskell.


Cheers.

On Sun, Dec 2, 2012 at 1:34 PM, Albert Y. C. Lai <trebla <at> vex.net> wrote:
On 12-11-30 01:16 PM, Mark Thom wrote:
Is there a paper or other single resource that will help me thoroughly
understand non-strictness in Haskell?

See my http://www.vex.net/~trebla/haskell/lazy.xhtml


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Mark Thom | 3 Dec 01:10 2012
Picon

Re: How to incrementally update list

And thanks to everyone for the links and other suggestions, of course.. 

On Sun, Dec 2, 2012 at 5:09 PM, Mark Thom <markjordanthom <at> gmail.com> wrote:
Thanks Albert, I believe that's the second time you've helped me this weekend. I'm meiji11 in #haskell.

Cheers.


On Sun, Dec 2, 2012 at 1:34 PM, Albert Y. C. Lai <trebla <at> vex.net> wrote:
On 12-11-30 01:16 PM, Mark Thom wrote:
Is there a paper or other single resource that will help me thoroughly
understand non-strictness in Haskell?

See my http://www.vex.net/~trebla/haskell/lazy.xhtml


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Kim-Ee Yeoh | 28 Nov 14:19 2012

Re: How to incrementally update list

> I want to incrementally update list lot of times, but don't know how to do this.


Are you using the right data structure for the job? Maybe you want an array instead?

-- Kim-Ee


On Wed, Nov 28, 2012 at 6:43 PM, Branimir Maksimovic <bmaxa <at> hotmail.com> wrote:
Problem is following short program:
list = [1,2,3,4,5]

advance l = map (\x -> x+1) l

run 0 s = s
run n s = run (n-1) $ advance s

main = do
        let s =  run 50000000 list
        putStrLn $ show s

I want to incrementally update list lot of times, but don't know
how to do this.
Since Haskell does not have loops I have to use recursion,
but problem is that recursive calls keep previous/state parameter
leading to excessive stack.and memory usage.
I don't know how to tell Haskell not to keep previous
state rather to release so memory consumption becomes
managable.

Is there some solution to this problem as I think it is rather
common?


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
KC | 30 Nov 22:25 2012
Picon

Re: How to incrementally update list

Why do you want to incrementally update this list a lot of times?

The question would affect the answer you get; i.e. some context
(non-monadically speaking). :D

On Wed, Nov 28, 2012 at 3:43 AM, Branimir Maksimovic <bmaxa <at> hotmail.com> wrote:
> Problem is following short program:
> list = [1,2,3,4,5]
>
> advance l = map (\x -> x+1) l
>
> run 0 s = s
> run n s = run (n-1) $ advance s
>
> main = do
>         let s =  run 50000000 list
>         putStrLn $ show s
>
> I want to incrementally update list lot of times, but don't know
> how to do this.
> Since Haskell does not have loops I have to use recursion,
> but problem is that recursive calls keep previous/state parameter
> leading to excessive stack.and memory usage.
> I don't know how to tell Haskell not to keep previous
> state rather to release so memory consumption becomes
> managable.
>
> Is there some solution to this problem as I think it is rather
> common?
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

--

-- 
--
Regards,
KC
Branimir Maksimovic | 1 Dec 09:02 2012
Picon

Re: How to incrementally update list

I want to simulate some calculation that does that.
For example n-body simulation.
Anyway this is solved ;)


> Date: Fri, 30 Nov 2012 13:25:57 -0800
> Subject: Re: [Haskell-cafe] How to incrementally update list
> From: kc1956 <at> gmail.com
> To: bmaxa <at> hotmail.com
> CC: haskell-cafe <at> haskell.org
>
> Why do you want to incrementally update this list a lot of times?
>
> The question would affect the answer you get; i.e. some context
> (non-monadically speaking). :D
>
>
> On Wed, Nov 28, 2012 at 3:43 AM, Branimir Maksimovic <bmaxa <at> hotmail.com> wrote:
> > Problem is following short program:
> > list = [1,2,3,4,5]
> >
> > advance l = map (\x -> x+1) l
> >
> > run 0 s = s
> > run n s = run (n-1) $ advance s
> >
> > main = do
> > let s = run 50000000 list
> > putStrLn $ show s
> >
> > I want to incrementally update list lot of times, but don't know
> > how to do this.
> > Since Haskell does not have loops I have to use recursion,
> > but problem is that recursive calls keep previous/state parameter
> > leading to excessive stack.and memory usage.
> > I don't know how to tell Haskell not to keep previous
> > state rather to release so memory consumption becomes
> > managable.
> >
> > Is there some solution to this problem as I think it is rather
> > common?
> >
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
>
>
> --
> --
> Regards,
> KC
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane