Implement main loop in haskell using mutable state

Question

I'm trying to implement a main loop of sorts in Haskell, in C I would write it like this:

EntityInteraction *frame(Entity *eList, EntityInteraction *iList) {
    parseInteractions(eList, iList);
    return simulateEntities(eList);
}

int main() {
    Entity eList[] = {...}
    EntityInteraction *iList = NULL;
    while(true) {
        iList = frame(eList, iList);
    }
}

So I attempted to replicate this in haskell by making frame a recursive function:

frame :: [Entity] -> [EntityInteraction] -> IO ()
frame eList iList = do
    frame (parseInteractions iList eList) (simulateEntities eList)

main :: IO ()
main = do
    let entList = [...]
    frame entList []

But this just results in a stack overflow as expected, so my question is what is the propper way to do a main loop in haskell that uses mutable state?

(I've been programming in C as a hobby for 4 years and I'm just starting to learn haskell)

Tail recursion such as this shouldn't result in a stack overflow. Maybe you elist or ilist just grows too big at some point? Also, how did you compile your program? Try with ghc -O2 just to make sure. — firefrorefiddle
– firefrorefiddle, Commented Aug 9, 2013 at 6:29
eList, and iList never gets added to. I tried with the -O2 switch and it still gives me the message: "main: out of memory" — Tom Tetlaw
– Tom Tetlaw, Commented Aug 9, 2013 at 6:34
Maybe you can provide a complete, compilable, minimal example. I just tried main = frame ; frame = return () >> frame, and while this obviously burns the cpu, it happily runs forever in constant space (using 800k memory). — firefrorefiddle
– firefrorefiddle, Commented Aug 9, 2013 at 6:51
The entire source code is here: pastebin.com/FrnyLb4e it's meant to be a functionally pure entity system, at the moment it does nothing though — Tom Tetlaw
– Tom Tetlaw, Commented Aug 9, 2013 at 6:56
The trouble is you are just recursing forever without ever outputting ("observing") anything. Add a print before the recursive call to frame, and you'll see that it's doing just fine. (Laziness does change the nature of "mutable" state -- i.e. you are building up thunks rather than computing anything -- but you are on the right track, and observing the results will help) — luqui
– luqui, Commented Aug 9, 2013 at 7:34

firefrorefiddle · Accepted Answer · 2013-08-09 07:51:27Z

It's an interesting phenomenon which only hits you in this empty example.

First, here is a minimal example:

frame :: [a] -> IO ()
frame eList = do    
    frame (id eList) 

main :: IO ()
main = do        
    frame []

If I run this with runghc, I get an out of memory error. However, either of these works: (if you compile them with ghc -O2, you might actually get the output <<loop>> and the program terminating. runghc doesn't detect the loop though and you can see the program running in constant space.)

A)

frame :: [a] -> IO ()
frame eList = do   
    frame eList

main :: IO ()
main = do        
    frame []

B)

frame :: [a] -> IO ()
frame eList = do    
    print eList
    frame (id eList) 

main :: IO ()
main = do        
    frame []

C)

frame :: [a] -> IO ()
frame eList = do   
    eList `seq` frame (id eList) 

main :: IO ()
main = do        
    frame []

What's the reason for this? Well, tail recursion per se is not the problem. There is no stack overflow, but an out of memory error. Why, if your lists are not actually changed with every loop iteration?

Well, they are! The function application itself builds up unevaluated thunks because you are never using the values! In all of the working examples, the only difference is that the values are actually evaluated and the thunks removed.

So the sequence of functions calls looks something like this in the erronous example:

frame []
frame (id [])
frame (id (id []))
frame (id (id (id []))) -- the argument takes more memory with every iteration
...

But like this in the working examples:

frame []
frame []
frame []
frame []
frame []
frame []                -- argument stays the same as 'id' is evaluated away.

Even though the thunks are not too expensive for themselves, in an infinite loop they will inevitable eat up all your memory, given enough time.

Ingo · Accepted Answer · 2013-08-09 08:35:56Z

0

You need this, I think:

frame :: [Entity] -> [EntityInteraction] -> IO ()
frame eList iList = do
    parseInteractions iList eList
    simulateEntities eList

main :: IO ()
main = do
    let entList = [...]
    forever $ frame entList []

Though it seems not to make much sense, for example, elist is always the empty list and so could be omitted. But if parseInteractions in your C solution produces/fills eList, then probably

eList <- parseInteractions iList

In this case, the question is if parseInteractions really needs to do IO?

answered Aug 9, 2013 at 8:35

Ingo

36.4k6 gold badges57 silver badges102 bronze badges

Collectives™ on Stack Overflow

Implement main loop in haskell using mutable state

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related