Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Program design in Haskell: how to do simulation without mutability

Tags:

I have a question about the best way to design a program I'm working on in Haskell. I'm writing a physics simulator, which is something I've done a bunch in standard imperative languages, and usually the main method looks something like:

while True:   simulationState = stepForward(simulationState)   render(simulationState) 

And I'm wondering how to do something similar in Haskell. I have a function step :: SimState -> SimState and a function display :: SimState -> IO () that uses HOpenGL to draw a simulation state, but I'm at a loss as to how to do this in a "loop" of sorts, as all of the solutions I can come up with involve some sort of mutability. I'm a bit of a noob when it comes to Haskell, so it's entirely possible that I'm missing a very obvious design decision. Also, if there's a better way to architect my program as a whole, I'd be glad to hear it.

Thanks in advance!

like image 700
Haldean Brown Avatar asked Mar 03 '12 18:03

Haldean Brown


1 Answers

In my opinion, the right way to think about this problem is not as a loop, but as a list or other such infinite streaming structure. I gave a similar answer to a similar question; the basic idea is, as C. A. McCann wrote, to use iterate stepForward initialState, where iterate :: (a -> a) -> a -> [a] “returns an infinite list of repeated applications of [stepForward] to [initialState]”.

The problem with this approach is that you have trouble dealing with a monadic step, and in particular a monadic rendering function. One approach would just be to take the desired chunk of the list in advance (possibly with a function like takeWhile, possibly with manual recursion) and then mapM_ render on that. A better approach would be to use a different, intrinsically monadic, streaming structure. The four that I can think of are:

  • The iteratee package, which was originally designed for streaming IO. I think here, your steps would be a source (enumerator) and your rendering would be a sink (iteratee); you could then use a pipe (an enumeratee) to apply functions and/or do filtering in the middle.
  • The enumerator package, based on the same ideas; one might be cleaner than the other.
  • The newer pipes package, which bills itself as “iteratees done right”—it's newer, but the semantics are, at least to me, significantly clearer, as are the names (Producer, Consumer, and Pipe).
  • The List package, in particular its ListT monad transformer. This monad transformer is designed to allow you to create lists of monadic values with more useful structure than [m a]; for instance, working with infinite monadic lists becomes more manageable. The package also generalizes many functions on lists into a new type class. It provides an iterateM function twice; the first time in incredible generality, and the second time specialized to ListT. You can then use functions such as takeWhileM to do your filtering.

The big advantage to reifying your program’s iteration in some data structure, rather than simply using recursion, is that your program can then do useful things with control flow. Nothing too grandiose, of course, but for instance, it separates the “how to terminate” decision from the “how to generate” process. Now, the user (even if it's just you) can separately decide when to stop: after n steps? After the state satisfies a certain predicate? There's no reason to bog down your generating code with these decisions, as it's logically a separate concern.

like image 71
Antal Spector-Zabusky Avatar answered Sep 22 '22 14:09

Antal Spector-Zabusky