DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
11 Monitoring and Observability Tools for 2023
Learn more
  1. DZone
  2. Software Design and Architecture
  3. Integration
  4. Game of life in Haskell

Game of life in Haskell

Giorgio Sironi user avatar by
Giorgio Sironi
·
May. 13, 13 · Interview
Like (0)
Save
Tweet
Share
8.06K Views

Join the DZone community and get the full member experience.

Join For Free

The Game of Life kata is a reference problem that can be solved many different ways, to experience a new language, methodology, testing framework, IDE, or else. Keeping the problem fixed while changing one factor into the equation lets you avoid many (but not all) confounding variables.

I had the suspect that functional implementations of the Game of Life would be very concise, having the problem a mathematical formulation. After some functional PHP code , this time I tried Haskell, a famous statically typed functional language.

The basic types

In Haskell, we can define enumerative data types. The state of a cell in the Game of Life can be modelled with a boolean, or more precisely with any type containing just two values. So it makes sense to give names to the possible states instead of using True and False.

data CellState = Dead | Alive

More complex data types can be built by composing a list of existing types. On the right side of = Position is a constructor that specifies this "Value Object" is composed by 2 Integers, representing in fact the position of a cell in the infinite 2D plane.

data Position = Position Integer Integer

Functions also have types: I define a Generation as a snapshot of the plane at one moment in time. A way to fully describe a generation is of providing a function that maps each possible instance of Position to a CellState, either Dead or Alive.

type Generation = Position -> CellState

Leaf functions

I don't know if there's a technical term, but even while developing outside-in we have to arrive at some functions that do not call other ones.

is_alive is a simple map from a CellState to a boolean value; we need it because primitives like filter need a Bool as an input (more precisely as the return type of the function taken as an input):

is_alive :: CellState -> Bool
is_alive Alive = True
is_alive Dead = False

neighbors is capable of generating a list of Position values from a single one, a list of 8 values actually. I didn't find a simpler solution than generating it by hand, but this case-based definition can be probably shortened:

neighbors :: Position -> [Position]
neighbors (Position x y) =
  [(Position (x-1) (y-1)), (Position x (y-1)),  (Position (x+1) (y-1)), (Position (x+1) y),
  (Position (x+1) (y+1)), (Position x (y+1)), (Position (x-1) (y+1)), (Position (x-1) y)]

Composing

The alive_neighbors function takes a Generation and a Position, and it tells you how many of the 8 cells near to the chosen Position are Alive in that Generation.

alive_neighbors :: Generation -> Position -> Int
alive_neighbors generation position = length (filter is_alive (map generation (neighbors position)))

Reading the function from the inside: first neighbors is applied to the Position, and generation is mapped on the result: at that point we have a list of CellState values. filter produces a new list containing only Alive values, and length counts them.

You can notice in the type signature how a multiple-argument function is specified, by separating arguments and the return type with ->:

alive_neighbors :: Generation -> Position -> Int

The reason is due to currying as each function in Haskell has only one argument, and what we are writing is a function that takes a Generation and returns a functon that takes a Position. But this is not important right now: this notation just means we have two arguments, and the returned value will be an Int.

Right now we are ready to solve the full problem: our evolution function takes a Generation and produce another Generation. It's an higher-order function like map and filter, because it takes a lower-level function as an argument instead of just using it.

evolution :: Generation -> Generation
evolution generation position =
  case (alive_neighbors generation position) of
  2 -> if (is_alive (generation position)) then Alive else Dead
  3 -> Alive
  _ -> Dead

Here the magic of currying happens. The type signature for evolution can be read as:

evolution :: Generation -> Position -> CellState

So in order to "return" a new Generation from an old Generation we can define a function that takes the old Generation and a Position as inputs and returns a CellState. Seems magic, but it's really consistent.

The rest of the function is just a switch statement, returning the new state as Alive or Dead depending on the current CellState and the number of alive_neighbors.

Displaying

Since I do not know yet how to write unit tests (or property-based tests) in Haskell, the only way to experiment with my implementation while coding was to visualize the results.

These functions take a Generation and visualize it in a 10x10 grid starting at the (1, 1) coordinates.

visualize_generation generation =
  map (visualize_line generation) [1..10]

visualize_line :: Generation -> Integer -> String
visualize_line generation y =
  concat (map (visualize_cell generation y) [1..10])

visualize_cell generation y x =
  case (generation (Position x y)) of
  Alive -> ['X']
  Dead -> [' ']

Here is the classic bar structure, a sequence of three alive cells that rotates by 90° at each new Generation:

bar (Position 1 2) = Alive
bar (Position 2 2) = Alive
bar (Position 3 2) = Alive
bar (Position x y) = Dead

Here is the bar rotating:

*Main> mapM_ print (visualize_generation bar)
"  "
"XXX  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "
*Main> mapM_ print (visualize_generation (evolution bar))
" X  "
" X  "
" X  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "
*Main> mapM_ print (visualize_generation (evolution (evolution bar)))
"  "
"XXX  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "

Conclusions

Functional approaches sometimes are much faster. I would like currying with no syntax overhead to be available in imperative languages, to easily transform method calls into closures.

Haskell syntax in fact match the functional style very well. Its programs usually run correctly, the moment you can get them to compile.

Haskell (programming language)

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • JWT Authentication and Authorization: A Detailed Introduction
  • Building the Next-Generation Data Lakehouse: 10X Performance
  • 3 Main Pillars in ReactJS
  • A Beginner's Guide to Infrastructure as Code

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: