fun row_size mat = length mat;
fun col_size [] = 0
| col_size (m::mat) = length m;

fun valid_index mat (r,c) = if r<0 orelse r>((row_size mat)-1) orelse c<0 orelse c>((col_size mat)-1) then false else true;

fun is_alive [] _ = false
    | is_alive (x::xs) (0,0) = if x=[] then false else hd(x)
    | is_alive (x::xs) (0,y) = if (valid_index (x::xs) (0,y)) then hd(List.drop(x,y))
                             else false
    | is_alive (m::ms) (x,y) = if (valid_index (m::ms) (x,y)) then (is_alive ms (x-1,y))
                             else false;

fun live_neighbours mat (r,c) =
let
    val arr = [(~1,~1),(~1,0),(~1,1),(0,~1),(0,1),(1,~1),(1,0),(1,1)]
    fun add_to_index xs (r,c) = map (fn (a,b) => (a+r,b+c)) xs
    fun is_alive_aux mat (r,c) = if(is_alive mat (r,c)) then 1 else 0
    fun live_neighbours_aux mat (r,c) = map(is_alive_aux mat)(add_to_index arr (r,c))
    fun sum lst = foldl op+ 0 lst;
in
    if(valid_index mat (r,c)) then sum(live_neighbours_aux mat (r,c)) else ~1
end;

fun rule mat false i j = live_neighbours mat (i,j) = 3
    | rule mat true i j = (live_neighbours mat (i,j)) = 3 orelse (live_neighbours mat (i,j)) = 2;

fun next_state_aux [] _ _= []
    | next_state_aux mat i j = if (valid_index mat (i,j)) then
      (rule mat (hd(List.drop(hd(List.drop(mat,i)),j))) i j)::(next_state_aux mat i (j + 1))
      else [];

fun next_state [] _ = []
    | next_state mat i= if (valid_index mat (i,0)) then (next_state_aux mat i 0) :: (next_state mat (i+1)) else [];

fun start_game mat 0 = mat
    | start_game mat i = start_game (next_state mat 0) (i-1);