在Haskell中进行程序设计:如何在没有可变性的情况下进行模拟

25

我有一个关于在Haskell中设计程序的问题。我正在编写一个物理模拟器,在标准命令式语言中已经做过很多次了,通常主方法看起来像:

while True:
  simulationState = stepForward(simulationState)
  render(simulationState)
我想知道如何在Haskell中实现类似的功能。我有一个函数step :: SimState -> SimState和一个使用HOpenGL绘制模拟状态的函数display :: SimState -> IO (),但我不知道如何在类似"循环"的情况下完成这个操作,因为我能想到的所有解决方案都涉及某种形式的可变性。对于Haskell来说,我是一个新手,所以我可能忽略了一些非常明显的设计决策。如果整个程序的架构有更好的方式,我会很高兴听到您的意见。谢谢!
3个回答

23

在我看来,正确的思考这个问题的方法不是循环,而是列表或其他类似的无限流结构。我曾经给一个类似的问题提供了一个类似的答案;基本思路是,如C. A. McCann所写,使用iterate stepForward initialState,其中iterate :: (a -> a) -> a -> [a]“返回重复将 [stepForward] 应用于 [initialState] 的无限列表”。

这种方法的问题在于处理单子步骤时会遇到困难,特别是单子渲染函数。一种方法是提前使用所需的列表块(可能使用takeWhile函数,也可能手动递归),然后在其上mapM_ render。更好的方法是使用不同的、本质上是单子的流结构。我能想到的有四种:
  • iteratee包,最初设计用于流式IO。在这里,您的步骤将是源(enumerator),您的渲染将是汇(iteratee);然后,您可以使用一个管道(enumeratee)在中间应用函数和/或进行过滤。
  • 枚举器包,基于相同的思想;其中一个可能比另一个更干净。
  • 较新的pipes包,它自称为“正确完成iteratees”-它是较新的,但语义至少对我来说明显更清晰,名称也更清晰(ProducerConsumerPipe)。
  • List包,特别是其ListT单子变换器。该单子变换器旨在允许您创建具有比[m a]更有用结构的单子值列表;例如,处理无限单子列表变得更加可管理。该包还将许多列表上的函数泛化为一个新类型类。它提供了一个iterateM函数两次;第一次具有令人难以置信的通用性,第二次专门针对ListT。然后,您可以使用诸如takeWhileM之类的函数来进行过滤。
您将程序迭代以某种数据结构实体化的最大优势,而不仅仅是使用递归,是您的程序可以通过控制流来做有用的事情。当然,并不是什么宏伟的事情,但例如,它将“如何终止”决策与“如何生成”过程分开。现在,用户(即使只是您自己)可以单独决定何时停止:经过n步之后?状态是否满足某个谓词?没有理由让生成代码陷入这些决策中,因为它在逻辑上是一个独立的问题。

1
你的列表似乎缺少monad-loops,我认为这实际上是该方法最清晰的演示。 - C. A. McCann
太棒了——我一直在寻找学习迭代器的理由。我会看看pipes包。非常感谢! - Haldean Brown
3
这可能有些过头了,但为了那些可能会在之后查看此问题的人,我们应该特别提到函数响应式编程,尤其是Yampa/Animas - John F. Miller
1
@C.A.McCann:那个包似乎采用了稍微不同的方法(基于组合子而不是基于数据结构),我认为你的答案已经更好地涵盖了这一点。(我找不到任何类似于“迭代”的组合子。) - Antal Spector-Zabusky
@AntalS-Z:没错,但我认为这实际上是相同的基本方法——通过从这些组合器中具象化递归,与ListT的关系大致相同,就像Data.List中的递归组合器与普通列表的关系一样;同样,它们强调递归和最终结果,而流处理则强调中间步骤的方面。我认为理解每个方面可以更好地了解正在发生的事情。 - C. A. McCann

22

如果你只想绘制连续的状态,那就很简单了。首先,使用你的step函数和初始状态,使用 iterate函数。然后,iterate step initialState是一个(无限)列表,包含每个模拟状态。随后,你可以将display映射到其中,以获取绘制每个状态的IO操作,因此你会得到以下代码:

allStates :: [SimState]
allStates = iterate step initialState

displayedStates :: [IO ()]
displayedStates = fmap display allStates

运行它最简单的方式是使用 intersperse函数 在每个显示操作之间添加一个“延迟”动作,然后使用 sequence_函数 运行整个过程:

main :: IO ()
main = sequence_ $ intersperse (delay 20) displayedStates
当然这意味着你必须强制终止应用程序,并且排除了任何交互,所以一般来说这不是一个好的方法。
更明智的方法是在每个步骤中交错进行诸如“查看应用程序是否应该退出”之类的事情。您可以使用显式递归来完成:
runLoop :: SimState -> IO ()
runLoop st = do display st
                isDone <- checkInput
                if isDone then return () 
                          else delay 20 >> runLoop (step st)

我更喜欢编写非递归步骤,然后使用更抽象的循环组合器。不幸的是,在标准库中没有很好的支持这种方式,但它看起来应该是这样的:

runStep :: SimState -> IO SimState
runStep st = do display st
                delay 20
                return (step st)

runLoop :: SimState -> IO ()
runLoop initialState = iterUntilM_ checkInput runStep initialState

留下实现iterUntilM_函数的任务供读者完成, 呵呵。


迭代/映射解决方案很棒,但我会选择递归方法。非常感谢! - Haldean Brown

12

你的方法没问题,只需记住在Haskell中循环是用递归表示的:

simulation state = do
    let newState = stepForward state
    render newState
    simulation newState

(但你绝对需要一个结束循环的标准。)


只是确认一下,这不会因为尾递归而导致堆栈溢出吗? - Haldean Brown
3
它既不是尾递归,也不应该出现堆栈溢出的情况 :) 试试看,或者尝试另外一种将渲染状态列表进行排序的解决方案。 - Ingo
7
在Haskell中,由于惰性求值的原因,尾递归并不像在其他编程语言中那样有用或者重要,但它也不会导致栈溢出。 - user395760

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接