使用可变状态在haskell中实现主循环

Question

我正在尝试在Haskell中实现一个主循环,在CI中会像这样写:

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);
    }
}

所以我试图通过使帧成为递归函数在haskell中复制它:

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

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

但这只会导致堆栈溢出如预期的那样,所以我的问题是在haskell中使用可变状态执行主循环的propper方法是什么？

(我已经在C编程作为业余爱好4年了,我刚开始学习haskell)

Answer 1

这是一个有趣的现象,只会在这个空洞的例子中击中你.

首先,这是一个最小的例子:

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

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

如果我运行它runghc,我会出现内存不足错误.但是,这些工作中的任何一个:(如果使用ghc -O2编译它们,实际上可能会得到输出<<loop>>并且程序终止.runghc虽然没有检测到循环,但您可以看到程序在恒定空间中运行.)

一个)

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 [] 

这是什么原因？那么,尾递归本身不是问题.没有堆栈溢出,但内存不足错误.为什么,如果每个循环迭代都没有实际更改您的列表？

好吧,他们是!函数应用程序本身会构建未评估的thunk,因为你永远不会使用这些值!在所有工作示例中,唯一的区别是实际评估了值并删除了thunk.

因此,函数调用的序列在错误的示例中看起来像这样:

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

但是在工作示例中这样:

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

尽管thunk对自己来说并不太贵,但在无限循环中,如果有足够的时间,它们将不可避免地占用你所有的记忆.