GraphLife

[kpreid]

This is a somewhat odd cellular automaton implementation in Haskell. It encodes the shape of the world, and the stepping rule, in the data structure. Briefly:

data Cell v n = Cell {
  value     :: v,
  neighbors :: n (Cell v n),
  future    :: Cell v n }

-- Build a cell and its chain of futures, given its rule, similar neighbors,
-- and initial value.
mkCell :: Functor n => (v -> n v -> v) -> v -> n (Cell v n) -> Cell v n
mkCell rule val nei = initial
  where initial = Cell val nei (calcFuture initial)
        calcFuture c = c'
          where c' = Cell (rule (value c) (fmap value (neighbors c)))
                          (fmap future (neighbors c))
                          (calcFuture c')

data Moore c = Moore c c c c c c c c

-- Conway's Life
evalLife :: Bool -> Moore Bool -> Bool
evalLife v n = f v (sumN fromEnum n)
  where f _    3 = True
        f True 2 = True
        f _    _ = False

The remainder of the code is routines for setting up worlds and displaying them.

• GraphLife.hs — The core and text-based display
• GraphLifeGL.hs — OpenGL display

Comments

Nice

[(Anonymous)]

That is very cool.

Just when I think I know haskell, I see something like this and am reminded that I am not Enlightened.

If you get time, could you post a brief explanation of how it works?

Re: Nice

[(Anonymous)]

For easier understanding it might be useful to replace n by [] in the preceding program, indeed [] is a Functor and a Foldable thus it won't change anything to the code except it's generality and it's safety under incorrect input (for example Moore has a hardwired eight elements in it where list length cannot be constrained by typing).

data Cell v = Cell { value     :: v,
                     neighbors :: [Cell v],
                     future    :: Cell v }

-- Build a cell and its chain of futures, given its rule, similar neighbors,
-- and initial value.
-- It is important to note that laziness means that the future won't be 
-- really constructed until we ask for it
mkCell :: (v -> [v] -> v) -> v -> [Cell v] -> Cell v
mkCell rule val nei = initial
  where initial = Cell val nei (calcFuture initial)
        calcFuture c = c'
          where c' = Cell (rule (value c) (map value (neighbors c)))
                          (map future (neighbors c))
                          (calcFuture c')
-- the cell value evolve according to the rule given to mkCell
-- the neighbors evolve into their future selves
-- and we recursively compute the future of our future


-- By changing to list we lose the typing constraint that Moore brought us
-- note that Moore is a Functor and a Foldable instance in the original
-- code (a NFoldable instance in fact, why not Foldable ?)
-- data Moore c = Moore c c c c c c c c

-- the "rule" we'll give mkCell to create a board following Conway's game of
-- life rules
evalLife :: Bool -> [Bool] -> Bool
evalLife v n = f v (sum $ map fromEnum n)
  where f _    3 = True
        f True 2 = True
        f _    _ = False

That's it, is it clearer for you with this ? (Or have I just made it even more foggy ?)

--
Jedaï

[ahefner.livejournal.com]

No screenshot?

[kpreid.livejournal.com]

How's that?

Of course, it's indistinguishable from any other un-fancified Life implementation, but hey.