In Haskell it's generally considered bad form to omit type annotations for your top-level functions. There is even a compiler warning for this sort of thing. Thankfully, the Haskell plugins for good editors (vim or emacs) provide hotkeys to automatically insert an inferred type annotation for a function you specify.
It's a bit tongue-in-cheek to compare this to Edward Kmett's FP Complete articles on Cellular Automata, but they're a really interesting read if you want to get your feet wet with some advanced Haskell programming
The series began as trying to explain the value of the Store Comonad for generalizing the "Cellular Automata are Comonads" notion, but then dipped into how to build resumable folds to implement CRC hashing for pngs.
The final article pulls a really great trick out where by writing down a very general type for cellular automata as comonads it was possible to automatically generate code which generalizes CAs to stranger topologies (like a cylinder).
The final code including the CA code, the strange topologies, the PNG encoder, and a webserver to display the whole thing online is all probably shorter than the Java CA code would have been here.
> I couldn't bring myself to do a Java version but I'd expect it to be several times larger
I'm a big fan of Clojure and don't have much love for Java, but this is a little unfair. I especially think doing a Java 8 version with lambdas would be an interesting comparison.
The code is up at https://github.com/logaan/typed-game-of-life and I'd be very happy to accept a pull request with a Java example. I've done a few side by side comparisons of Clojure / Scala / Java and the Java has always been several times larger than Cloure / Scala. In a couple of cases it was 20-30x larger.
Java 8 may indeed improve this situation. Does it also introduce higher order functions for working with collections?
I don't actually identify as Gen Y (I had to look up the dates) or as a particularly distractible person. I just wanted a pithy way of saying that the protocol issue I hit wasn't necessarily an inherent issue, but rather that I chose not to deal with it.
I've always liked the Game of Life implemented with stencil convolution[1]. It's very declarative.
Stencil convolution[2] transforms a matrix (often an image) by taking a small matrix--the stencil--and using it as a set of weights to add all that cell's neighbors. Let's imagine our stencil is the following matrix:
1 2 3
4 5 6
7 8 9
Then, to process each cell in the big matrix, we start by putting the 5 over that cell. The new value for the cell is going to be 1 times the cell up and to the left plus 2 times the cell directly above plus 3 times the cell up and to the right and so on.
If we represent the Game of Life as a matrix--a two dimensional array of Ints--we can use a stencil to easily compute the neighbor count. We would use this matrix:
1 1 1
1 0 1
1 1 1
Applying this stencil gives us a function that goes from the matrix of alive cells to a matrix of neighbor counts. Then, to do a step in the game of life, we just zip the two matrices together with the transition function.
The neat bit is that the real code looks pretty close to what I have just said! For example, here is how the stencil looks:
neighbors = [stencil2|1 1 1
1 0 1
1 1 1|]
We can use basically the same transition function as in the post:
transition a 2 = a
transition _ 3 = 1
transition _ _ = 0
(BoundConst 0) just tells the stencil to treat every square outside the large input matrix as 0. R.computeUnboxedS just turns the result of zipWith back into an unboxed array.
Now, the computeUnboxedS function call is not really intuitive. Unless you knew how the API was supposed to work, you would not think of it. This is where Haskell's types come in, acting like active documentation: you can see that you need the computeUnboxedS function because that's the only way to get from the type at the result of zipWith to the type you actually want!
Anyhow, this is not the best way to implement life, admittedly. The biggest shortcoming is that, since you're using an array, the field is always bounded to the same size and you're always representing every cell, even ones that won't be alive for generations. Mostly, this is just a great example to see how stencil convolution works!
The list comprehension is great, but man is prefix ((.).(.)) scary. I always rename that to (.:), use it infix, define it pointfully, and comment calling it "two-argument compose".
22 comments
[ 3.6 ms ] story [ 64.9 ms ] thread[1] https://github.com/logaan/typed-game-of-life/blob/master/src...
I'm not so proficient a developer that I could write any amount of Haskell code without being acutely aware of its statically typed nature.
https://www.fpcomplete.com/user/edwardk/cellular-automata
The series began as trying to explain the value of the Store Comonad for generalizing the "Cellular Automata are Comonads" notion, but then dipped into how to build resumable folds to implement CRC hashing for pngs.
The final article pulls a really great trick out where by writing down a very general type for cellular automata as comonads it was possible to automatically generate code which generalizes CAs to stranger topologies (like a cylinder).
The final code including the CA code, the strange topologies, the PNG encoder, and a webserver to display the whole thing online is all probably shorter than the Java CA code would have been here.
I'm a big fan of Clojure and don't have much love for Java, but this is a little unfair. I especially think doing a Java 8 version with lambdas would be an interesting comparison.
Java 8 may indeed improve this situation. Does it also introduce higher order functions for working with collections?
I can't believe people internalize this "Gen Y" shit. It's just ageism. There's always been something to distract us.
Stencil convolution[2] transforms a matrix (often an image) by taking a small matrix--the stencil--and using it as a set of weights to add all that cell's neighbors. Let's imagine our stencil is the following matrix:
Then, to process each cell in the big matrix, we start by putting the 5 over that cell. The new value for the cell is going to be 1 times the cell up and to the left plus 2 times the cell directly above plus 3 times the cell up and to the right and so on.If we represent the Game of Life as a matrix--a two dimensional array of Ints--we can use a stencil to easily compute the neighbor count. We would use this matrix:
Applying this stencil gives us a function that goes from the matrix of alive cells to a matrix of neighbor counts. Then, to do a step in the game of life, we just zip the two matrices together with the transition function.The neat bit is that the real code looks pretty close to what I have just said! For example, here is how the stencil looks:
We can use basically the same transition function as in the post: And the actual step algorithm: (BoundConst 0) just tells the stencil to treat every square outside the large input matrix as 0. R.computeUnboxedS just turns the result of zipWith back into an unboxed array.Now, the computeUnboxedS function call is not really intuitive. Unless you knew how the API was supposed to work, you would not think of it. This is where Haskell's types come in, acting like active documentation: you can see that you need the computeUnboxedS function because that's the only way to get from the type at the result of zipWith to the type you actually want!
Anyhow, this is not the best way to implement life, admittedly. The biggest shortcoming is that, since you're using an array, the field is always bounded to the same size and you're always representing every cell, even ones that won't be alive for generations. Mostly, this is just a great example to see how stencil convolution works!
[1]: http://www.slideshare.net/kizzx2/repagolpdf
[2]: http://research.microsoft.com/en-us/um/people/simonpj/papers...
Here's one I found online http://dfns.dyalog.com/s_life.htm
Completely awesome convolution method.I have no idea what the inputs need to be. I coded by types. Code compiles but has never been tested but probably works. (Ha, gotta love haskell)
edit: Think it works