Heavily inspired by Manuel Rotter's HackerNews post: Conways Game of Life in Clojure. You should definitely check that out.In fact, I intersperse his Clojure code with my Scala code, so you can compare & contrast the two.
Scala's green italics, Clojure's plain blue.
Fire up the Scala REPL.
Welcome to Scala version 2.9.2 (Java HotSpot(TM) 64Bit Server VM, Java 1.7.0_04).
Type in expressions to have them evaluated.
Type :help for more information.
scala>
1. Define a function to create a rectangular world with live cells "X", dead cells " ".
In Clojure:
(defn createworld
[w h & livingcells]
(vec (for [y (range w)]
(vec (for [x (range h)]
(if (contains? (first livingcells) [y x]) "X" " "))))))
A straightforward oneliner in Scala:
def cw (w:Int, h:Int, living:List[(Int,Int)]) = { List.tabulate [String] (w,h) ( (x,y) => if ( living.contains(x,y)) "X" else " " )}
Note: createworld isn't a legit scala identifier 'cause the minus sign...so I've named it cw.
2. Create a 16 cell square with alives along the diagonals.
(createworld 4 4 #{[0 0], [1 1], [2 2], [3 3]}) =>
[["X" " " " " " "] [" " "X" " " " "] [" " " " "X" " "] [" " " " " " "X"]]
cw (4, 4, List((0,0),(1,1),(2,2),(3,3)) )
List[List[String]] = List(List(X, " ", " ", " "), List(" ", X, " "," "), List(" ", " ", X, " "), List(" ", " ", " ", X))
3. Determine all the neighbors of a cell
(defn neighbours
[[x y]]
(for [dx [1 0 1] dy [1 0 1] :when (not= 0 dx dy)]
[(+ dx x) (+ dy y)]))
def nbrs (x: Int,y: Int)=for (dx<List(1, 0, 1);dy<List(1,0,1) if (!(dx==0 && dy==0))) yield (x+dx, y +dy)
Note: If the above Scala syntax is unfamiliar, we're using sequence comprehensions with guards.
What are all the neighbors of the location (1/1)?
(neighbours [1 1]) =>
([0 0] [0 1] [0 2] [1 0] [1 2] [2 0] [2 1] [2 2])
nbrs(1,1)
List[(Int, Int)] = List((0,0), (0,1), (0,2), (1,0), (1,2), (2,0), (2,1),(2,2))
4. Write a higherorder function that takes three arguments: A function to determine the neighbors, a predicate which determines whether a cell shall be given life, and one predicate that determines whether a cell survives to the next generation.
It then returns a function which calculates the next generation according to the given rules.
(defn stepper
[neighbours birth? survive?]
(fn [cells]
(set (for [[loc n] (frequencies (mapcat neighbours cells))
:when (if (cells loc) (survive? n) (birth? n))]
loc))))
type nbr_type = (Int,Int)=>List[(Int,Int)]
type birth_type = Int => Boolean
type survive_type = Int => Boolean
type nextgen_type = List[(Int,Int)] => List[(Int,Int)]
def stepper( nbrs:nbr_type, birth:birth_type, survive:survive_type): nextgen_type = {
((alive:List[(Int,Int)]) => {
val dead = alive.map( c=> nbrs(c._1,c._2)).flatten.removeDuplicates.filterNot( x=> alive.contains(x))
List( (alive, survive), (dead, birth) ).map( x =>
(x._1.map ( a=> (a,nbrs(a._1,a._2).intersect( alive ).size )).filter( a=> x._2(a._2)).map( a => a._1))).flatten
})}
Usage: To get the second state of a blinker pattern, we give our stepper the coordinates of the livings cells for the vertical position of the blinker (  )
((stepper neighbours #{3} #{2 3}) #{[1 0] [1 1] [1 2]}) =>
#{[2 1] [1 1] [0 1]}
stepper( nbrs _, List(3).contains _, List(2,3).contains _)( List((1,0),(1,1),(1,2)))
res19: List[(Int, Int)] = List((1,1), (0,1), (2,1))
Voila !!! Identical results! And we're done!!!
But how does that piece of Scala code work ?!!
Okay, this one's quite hard if you've never done this sort of thing before. So lemme dumb this down a bit: A higherorder function is a function that takes a function as input and/or returns a function as output. Most imperative languages either don't provide for higherorder functions, or do so in a convoluted fashion so nobody uses the facility. otoh, the hallmark of a functional language is the ease with which you can create higherorder functions.
Now, the stepper function is a higher order function takes three input functions and returns one output function.
1. The first input function must determine the neighbors of a cell, given the cell's x & y locations. The locations are in an Int tuple, and the neighbors would be a list of 8 Int tuples.
So its type would be
type nbr_type = (Int,Int)=>List[(Int,Int)]
2. The second input function is a predicate. It must take in a list of neighbor counts, and based on the count, return a boolean if a cell comes alive. For example  Conway says "if a cell has three live neighbors it comes alive, as if by reproduction".
Given a neighbor count, the predicate would return true only if the count was equal to 3, by doing a check against the contains() function of List(3)
type birth_type = Int => Boolean
3. The third input function is a predicate. It must take in a list of neighbor counts, and based on the count, return a boolean if a cell survives another generation. For example  Conway says "Any live cell with 2 or 3 live neighbors lives on to the next generation".
Given a neighbor count, the predicate would return true only if the count was either 2 or 3, by doing a check against the contains() function of List(2,3)
type survive_type = Int => Boolean
BTW: survive_type is identical to birth_type, so just use one of them, as I've done below.
4. The output function must calculate the next generation given the previous generation. A generation is simply a list of integer tuples. So the mapping is pretty straightforward.
type nextgen_type = List[(Int,Int)] => List[(Int,Int)]
BTW: You can omit nextgen_type because return types are inferred in Scala, and I've done so below.
So, how does the stepper function actually work ?
Let's first define a dumb stepper. The dumb stepper simply returns the current generation unchanged as the next generation. The identity function, so to speak.
def stepper( nbr:nbr_type, birth:birth_type, survive:survive_type): nextgen_type = {
val nextgen = ((currgen:List[(Int,Int)]) => {currgen})
nextgen
}
Now let's give it the desired smarts.
Well, you give it a list of integer tuples that indicate the cells alive in the current generation ( alive )
((alive:List[(Int,Int)]) =>
The dead cells are the unique neighbors of the alive cells. We first get these neighbors, which is a list of lists, flatten it out & remove the duplicates and filter out the neighbors that happen to be alive.
val dead = alive.map( c=> nbrs(c._1,c._2)).flatten.removeDuplicates.filterNot( x=> alive.contains(x))
At this point you have a partition = two sets = the alive set & the dead set.
Given a live cell from the alive set, you find its live neighbors by doing an intersection of its neighborsset with aliveset.
You count its live neighbors by invoking size.
You run this count by the survive predicate, and that tells you if this live cell survives another generation.
Given a dead cell from the dead set, you find its live neighbors by doing an intersection of its neighborsset with aliveset.
You count its live neighbors by invoking size.
You run this count by the birth predicate, and that tells you if this dead cell is reborn in the next generation.
So you see, you do the same exact thing for both sets in the partition, except for one tiny difference.
The alive set is checked against the survive predicate, and the dead cells against the birth predicate.
So start out by bundling each set with its appropriate predicate.
List( (alive, survive), (dead, birth) )
Now iterate over this list, find the neighbors, do the intersect, count, countcheck etc...
List( (alive, survive), (dead, birth) ).map( x =>
(x._1.map ( a=> (a,nbrs(a._1,a._2).intersect( alive ).size )).filter( a=> x._2(a._2)).map( a => a._1))).flatten
5. At this point, we're done! We could define yet another convenience wrapper to iterate over stepper...this last function just helps us to determine the evolution according to Conway's Game of Life by giving it the size of the world, an initial pattern and the number of the generation we want to see.
(defn conway
"Generates world of given size with initial pattern in specified generation"
[[w h] pattern iterations]
(>> (iterate conwaystepper pattern)
(drop iterations)
first
(createworld w h)
(map println)))
The Scala version of this convenience wrapper is left as an exercise for the patient reader :)
Scala's green italics, Clojure's plain blue.
Fire up the Scala REPL.
Welcome to Scala version 2.9.2 (Java HotSpot(TM) 64Bit Server VM, Java 1.7.0_04).
Type in expressions to have them evaluated.
Type :help for more information.
scala>
1. Define a function to create a rectangular world with live cells "X", dead cells " ".
In Clojure:
(defn createworld
[w h & livingcells]
(vec (for [y (range w)]
(vec (for [x (range h)]
(if (contains? (first livingcells) [y x]) "X" " "))))))
A straightforward oneliner in Scala:
def cw (w:Int, h:Int, living:List[(Int,Int)]) = { List.tabulate [String] (w,h) ( (x,y) => if ( living.contains(x,y)) "X" else " " )}
Note: createworld isn't a legit scala identifier 'cause the minus sign...so I've named it cw.
2. Create a 16 cell square with alives along the diagonals.
(createworld 4 4 #{[0 0], [1 1], [2 2], [3 3]}) =>
[["X" " " " " " "] [" " "X" " " " "] [" " " " "X" " "] [" " " " " " "X"]]
cw (4, 4, List((0,0),(1,1),(2,2),(3,3)) )
List[List[String]] = List(List(X, " ", " ", " "), List(" ", X, " "," "), List(" ", " ", X, " "), List(" ", " ", " ", X))
3. Determine all the neighbors of a cell
(defn neighbours
[[x y]]
(for [dx [1 0 1] dy [1 0 1] :when (not= 0 dx dy)]
[(+ dx x) (+ dy y)]))
def nbrs (x: Int,y: Int)=for (dx<List(1, 0, 1);dy<List(1,0,1) if (!(dx==0 && dy==0))) yield (x+dx, y +dy)
Note: If the above Scala syntax is unfamiliar, we're using sequence comprehensions with guards.
What are all the neighbors of the location (1/1)?
(neighbours [1 1]) =>
([0 0] [0 1] [0 2] [1 0] [1 2] [2 0] [2 1] [2 2])
nbrs(1,1)
List[(Int, Int)] = List((0,0), (0,1), (0,2), (1,0), (1,2), (2,0), (2,1),(2,2))
4. Write a higherorder function that takes three arguments: A function to determine the neighbors, a predicate which determines whether a cell shall be given life, and one predicate that determines whether a cell survives to the next generation.
It then returns a function which calculates the next generation according to the given rules.
(defn stepper
[neighbours birth? survive?]
(fn [cells]
(set (for [[loc n] (frequencies (mapcat neighbours cells))
:when (if (cells loc) (survive? n) (birth? n))]
loc))))
type nbr_type = (Int,Int)=>List[(Int,Int)]
type birth_type = Int => Boolean
type survive_type = Int => Boolean
type nextgen_type = List[(Int,Int)] => List[(Int,Int)]
def stepper( nbrs:nbr_type, birth:birth_type, survive:survive_type): nextgen_type = {
((alive:List[(Int,Int)]) => {
val dead = alive.map( c=> nbrs(c._1,c._2)).flatten.removeDuplicates.filterNot( x=> alive.contains(x))
List( (alive, survive), (dead, birth) ).map( x =>
(x._1.map ( a=> (a,nbrs(a._1,a._2).intersect( alive ).size )).filter( a=> x._2(a._2)).map( a => a._1))).flatten
})}
Usage: To get the second state of a blinker pattern, we give our stepper the coordinates of the livings cells for the vertical position of the blinker (  )
((stepper neighbours #{3} #{2 3}) #{[1 0] [1 1] [1 2]}) =>
#{[2 1] [1 1] [0 1]}
stepper( nbrs _, List(3).contains _, List(2,3).contains _)( List((1,0),(1,1),(1,2)))
res19: List[(Int, Int)] = List((1,1), (0,1), (2,1))
Voila !!! Identical results! And we're done!!!
But how does that piece of Scala code work ?!!
Okay, this one's quite hard if you've never done this sort of thing before. So lemme dumb this down a bit: A higherorder function is a function that takes a function as input and/or returns a function as output. Most imperative languages either don't provide for higherorder functions, or do so in a convoluted fashion so nobody uses the facility. otoh, the hallmark of a functional language is the ease with which you can create higherorder functions.
Now, the stepper function is a higher order function takes three input functions and returns one output function.
1. The first input function must determine the neighbors of a cell, given the cell's x & y locations. The locations are in an Int tuple, and the neighbors would be a list of 8 Int tuples.
So its type would be
type nbr_type = (Int,Int)=>List[(Int,Int)]
2. The second input function is a predicate. It must take in a list of neighbor counts, and based on the count, return a boolean if a cell comes alive. For example  Conway says "if a cell has three live neighbors it comes alive, as if by reproduction".
Given a neighbor count, the predicate would return true only if the count was equal to 3, by doing a check against the contains() function of List(3)
type birth_type = Int => Boolean
3. The third input function is a predicate. It must take in a list of neighbor counts, and based on the count, return a boolean if a cell survives another generation. For example  Conway says "Any live cell with 2 or 3 live neighbors lives on to the next generation".
Given a neighbor count, the predicate would return true only if the count was either 2 or 3, by doing a check against the contains() function of List(2,3)
type survive_type = Int => Boolean
BTW: survive_type is identical to birth_type, so just use one of them, as I've done below.
4. The output function must calculate the next generation given the previous generation. A generation is simply a list of integer tuples. So the mapping is pretty straightforward.
type nextgen_type = List[(Int,Int)] => List[(Int,Int)]
BTW: You can omit nextgen_type because return types are inferred in Scala, and I've done so below.
So, how does the stepper function actually work ?
Let's first define a dumb stepper. The dumb stepper simply returns the current generation unchanged as the next generation. The identity function, so to speak.
def stepper( nbr:nbr_type, birth:birth_type, survive:survive_type): nextgen_type = {
val nextgen = ((currgen:List[(Int,Int)]) => {currgen})
nextgen
}
Now let's give it the desired smarts.
Well, you give it a list of integer tuples that indicate the cells alive in the current generation ( alive )
((alive:List[(Int,Int)]) =>
The dead cells are the unique neighbors of the alive cells. We first get these neighbors, which is a list of lists, flatten it out & remove the duplicates and filter out the neighbors that happen to be alive.
val dead = alive.map( c=> nbrs(c._1,c._2)).flatten.removeDuplicates.filterNot( x=> alive.contains(x))
At this point you have a partition = two sets = the alive set & the dead set.
Given a live cell from the alive set, you find its live neighbors by doing an intersection of its neighborsset with aliveset.
You count its live neighbors by invoking size.
You run this count by the survive predicate, and that tells you if this live cell survives another generation.
Given a dead cell from the dead set, you find its live neighbors by doing an intersection of its neighborsset with aliveset.
You count its live neighbors by invoking size.
You run this count by the birth predicate, and that tells you if this dead cell is reborn in the next generation.
So you see, you do the same exact thing for both sets in the partition, except for one tiny difference.
The alive set is checked against the survive predicate, and the dead cells against the birth predicate.
So start out by bundling each set with its appropriate predicate.
List( (alive, survive), (dead, birth) )
Now iterate over this list, find the neighbors, do the intersect, count, countcheck etc...
List( (alive, survive), (dead, birth) ).map( x =>
(x._1.map ( a=> (a,nbrs(a._1,a._2).intersect( alive ).size )).filter( a=> x._2(a._2)).map( a => a._1))).flatten
5. At this point, we're done! We could define yet another convenience wrapper to iterate over stepper...this last function just helps us to determine the evolution according to Conway's Game of Life by giving it the size of the world, an initial pattern and the number of the generation we want to see.
(defn conway
"Generates world of given size with initial pattern in specified generation"
[[w h] pattern iterations]
(>> (iterate conwaystepper pattern)
(drop iterations)
first
(createworld w h)
(map println)))
The Scala version of this convenience wrapper is left as an exercise for the patient reader :)
in 17 lines of Clojure, courtesy Manuel Rotter :
 (defn createworld
 [w h & livingcells]
 (vec (for [y (range w)]
 (vec (for [x (range w)]
 (if (contains? (first livingcells) [y x]) "X" " "))))))

 (defn neighbours
 [[x y]]
 (for [dx [1 0 1] dy [1 0 1] :when (not= 0 dx dy)]
 [(+ dx x) (+ dy y)]))

 (defn stepper
 [neighbours birth? survive?]
 (fn [cells]
 (set (for [[loc n] (frequencies (mapcat neighbours cells))
 :when (if (cells loc) (survive? n) (birth? n))]
 loc))))
in 10 lines of Scala, by Krishnan Raman
 def cw (w:Int, h:Int, curr:List[(Int,Int)]) = { List.tabulate [String] (w,h) ( (x,y) => if ( curr.contains(x,y)) "X" else " " )}
 def nbrs (x: Int,y: Int)=for (dx<List(1, 0, 1);dy<List(1,0,1) if (!(dx==0 && dy==0))) yield (x+dx, y +dy)
 type nbr_type = (Int,Int)=>List[(Int,Int)]
 type birth_type = Int => Boolean
 def stepper( nbrs:nbr_type, birth:birth_type, survive:birth_type) = {
 ((alive:List[(Int,Int)]) => {
 val dead = alive.map( c=> nbrs(c._1,c._2)).flatten.removeDuplicates.filterNot( x=> alive.contains(x))
 List( (alive, survive), (dead, birth) ).map( x =>
 (x._1.map ( a=> (a,nbrs(a._1,a._2).intersect( alive ).size )).filter( a=> x._2(a._2)).map( a => a._1))).flatten
 })}