Need some feedback on my fold_neighbours attempt on this problem in Ocaml

Question

This program is an attempt of reading and solving a sudoku board using recursion and graph coloring.

type vertex = int * int 

module Vertex = Map.Make(struct
  type t = vertex
  let compare = Stdlib.compare
  end)

let ascii_digit c = Char.code c - Char.code '0'

let read_matrix chan = 
  let rec loop i j grid = 
    match input_char chan with 
    | exception End_of_file -> grid
    | '\n' -> loop (i+1) 0 grid
    | '0'..'9' as c ->
      loop i (j+1) @@
      Vertex.add (i,j) (ascii_digit c) grid
    | _ -> invalid_arg "invalid input" in
  loop 0 0 Vertex.empty

let matrix_from_file file =
  let chan = open_in file in
  let r = read_matrix chan in
  close_in chan;
  r

(*Print grid method*)
let print_vertex vertex = 
  let print_node (x,y) g  = 
    Printf.printf "\n(%d, %d) = " x y;
    print_int g
  in
  Vertex.iter print_node vertex

(*Print pretty sudoku*)
let print_board vertex = 
  let print_node (_x,_y) _grid =
    if _y = 0 then 
      Printf.printf "\n | ";
      print_int _grid;
      print_string " | "
  in 
  Vertex.iter print_node vertex

Im trying to implement this fold_neighbours but i can't make it work with my (Map.Vertex). I think my logic is right, but gets a alot of errors etc. Maybe i should break out the functions into separate functionalities?

let fold_neighbours v gamma game =
  let in_quadrant (x1, y1) (x2, y2) = 
    x1/3 = x2/3 && y1/3 = y2/3 
  in 
  let is_neighbour v n = 
    in_quadrant v n || fst v = fst n || snd v = snd n
  in 
  let filter v gamma  = 
    if is_neighbour neigh v' then
      f v' g' a
    else 
      a
  in
  fold_vertices filter game

Answer 1

It is much easier than you think. To make it even easier let's split the tasks into simple sub-tasks, which we can't get wrong. First of all, let's define what are the neighbors. To make things visual let's denote positions with compass directions (we can use just up and down, instead, if you find it easier to understand)

let north (x,y) = (x+1,y) (* [north p] is to the north of [p] *)
let northeast (x,y) = (x+1,y+1) (* [north p] is to the north of [p] *)
...
let south (x,y) = (x-1,y) (* [north p] is to the north of [p] *)
...
let norhtwest (x,y) = (x-1,y+1) (* [north p] is to the north of [p] *)

Now, we can say that the set of neighbors is,

let neighbors p = [
  north p;
  northeast p;
  ...
  northwest p;
]

And we can write a function that takes a vertex and the game map and folds over all available neighbors,

let fold_neighbors vertex map ~init ~f =
  let visit s v = match Vertex.find_opt v map with
    | None -> s
    | Some d -> f v d s in
  List.fold_left visit init (neighbors vertex)

Notice, that I am passing to the visiting function f three parameters, the neighbor coordinates, the value of vertex in the game, and the state.

And the last bit. You might find that defining a list of neighbors in a such declarative way is not programmatical. Well, it is possible of course to write a function that will generate those eight vertices. For that we will employ generative recursion. It is usually hard to reason about it, but for the sake of learning let's try it, here is my take,

let neighbors (x,y) =
  let rec gen i j =
    if i = 0 && j = 0 then gen (i+1) j
    else if i < 2 then (x+i,y+j) :: gen (i+1) j
    else if j < 1 then gen (-1) (j+1)
    else [] in
  gen (-1) (-1)

Meh, looks ugly, but works. Could write it better? Try it and update my answer with a better version! :)