current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

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)

share|improve this question
    
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. –  Mike Hartl Aug 9 '13 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 Aug 9 '13 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). –  Mike Hartl Aug 9 '13 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 Aug 9 '13 at 6:56
1  
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 Aug 9 '13 at 7:34

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
up vote 0 down vote

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.