I’m not sure if this is the place for this, but I wanted to start a discussion
that would end up being sort of a sprawling code review of a toy problem.
I’m just learning OCaml.
One of the exciting techniques I’ve read about in using a language that support
abstract data types is the fact that you can model your problem in a way that
the type system makes it impossible to represent invalid application states.
This is something that I’ve seen only a couple examples of and I want to try to
find more ways to learn how to do this better.
I’m working on a side project gathering a collection of coding puzzles to solve
in OCaml and I came up with a couple implementations of one that might be
approaching something manageable but I still feel like it’s falling short.
To take you through the iterations, I’m working on a way to generate a solution
to this simple logic puzzle involving a fox, a goose, a bag of corn, and a
river. You can only transport one animal at a time, and leaving the animals
alone on one side of the river will allow that animal to eat another animal (or
the corn).
I’ve come up with a couple ways to represent this that are varying degrees along
the spectrum of the code allowing for invalid states to still be possible.
(* naiive and error prone *)
type player = Fox | Goose | Corn | Person
type riverbank = Bank of player list
type boat = Boat player list
type game = riverbank * boat * riverbank
let first_game_state = (
[Fox; Goose; Corn; Person],
[],
[]
)
(* check if someone's getting eaten *)
let is_dangerous g = true (* would need to check list contents etc *)
let generate_solution first_state = [first_state]
(* would generate a list of states that get to the solution state *)
This is how I would probably model it in most languages, but there are a number
of invalid states you could create from this model. For example if the solution
generator’s second step looked like this:
(
[Fox; Fox; Corn; ],
[Person; Goose],
[],
)
We know something’s wrong since there can only be one Fox
in the game. Also I
think the act of iterating over a list of things isn’t that great. I would
rather be able to use some pattern matching.
The next data model I came up with has slots for each of the members. At this
point I noticed that a boat also has the constraint of only either being empty
or having a player or an animal.
type not_player = Fox | Goose | Corn | Empty
type fox_spot = HasFox | NoFox
type goose_spot = HasGoose | NoGoose
type corn_spot = HasCorn | NoCorn
type player_spot = HasPlayer | NoPlayer
type river_side = (fox_spot * goose_spot * corn_spot * player_spot)
type boat = EmptyBoat | Boat of player_spot * not_player
type game_state = river_side * boat * river_side
And some tests to verify safe and unsafe game states:
open OUnit
open Solutions.Foxgoosecorn
type step_result = Safe | Unsafe
let check_side side = match side with
| (_, _, _, HasPlayer) -> Safe
| (HasFox, HasGoose, _, NoPlayer) -> Unsafe
| (_, HasGoose, HasCorn, NoPlayer) -> Unsafe
| _ -> Safe
let check game = match game with
(left, boat, right) -> match (check_side left, check_side right) with
| (_, Unsafe) -> Unsafe
| (Unsafe, _) -> Unsafe
| _ -> Safe
let suite = "FoxGooseCorn">::: [
"fox eats goose">:: (fun c ->
assert_equal
Unsafe
(check (
(HasFox, HasGoose, NoCorn, NoPlayer),
Boat (HasPlayer, Corn),
(NoFox, NoGoose, NoCorn, NoPlayer)
))
);
"safe state1">:: (fun c ->
assert_equal
Safe
(check (
(HasFox, HasGoose, HasCorn, HasPlayer),
Boat (NoPlayer, Empty),
(NoFox, NoGoose, NoCorn, NoPlayer)
))
);
"safe state2">:: (fun c ->
assert_equal
Safe
(check (
(HasFox, NoGoose, HasCorn, NoPlayer),
Boat (HasPlayer, Goose),
(NoFox, NoGoose, NoCorn, NoPlayer)
))
);
]
This feels better to me, but I still can represent a character being in more
than one place at the same time:
(
(HasFox, NoGoose, HasCorn, NoPlayer),
Boat (HasPlayer, Fox),
(HasFox, NoGoose, NoCorn, NoPlayer)
)
While this gives me a more declarative way to define unsafe states, it still
allows me to put a character in more than one place at a time, leading me to
this implementation:
type position = LeftBank | RightBank | Boat
type game_state = {
fox: position;
goose: position;
corn: position;
player: position
}
And rewriting the tests:
open OUnit
open Solutions.Foxgoosecorn
type step_result = Safe | Unsafe
let combine_check a b = match (a, b) with
| (Safe, x) -> x
| (Unsafe, _) -> Unsafe
let check_fox g = match g with
| {
player = p;
fox = f;
goose = g; _ }
when f == g && f != p -> Unsafe
| _ -> Safe
let check_goose g = match g with
| {
player = p;
corn = c;
goose = g; _ }
when c == g && c != p -> Unsafe
| _ -> Safe
let check game = combine_check (check_fox game) (check_goose game)
let suite = "FoxGooseCorn">::: [
"fox eats goose">:: (fun c ->
assert_equal
Unsafe
(check {
player= Boat;
fox= LeftBank;
goose= LeftBank;
corn= Boat
})
);
"safe state1">:: (fun c ->
assert_equal
Safe
(check {
player= LeftBank;
fox= LeftBank;
goose= LeftBank;
corn= LeftBank
})
);
"safe state2">:: (fun c ->
assert_equal
Safe
(check {
player= Boat;
fox= LeftBank;
goose= Boat;
corn= LeftBank
})
);
]
Since there’s a fixed set of characters in the game, I can limit the game state
to tracking their current position explicitly, and re-adapt the pattern matching
to check for unsafe states.
I’m not happy with the fact that I have to write a function to check each
character explicitly. Also, it’s still possible for several characters to be in
the boat at the same time, even though there should only be the character plus
an extra at most.
Is there a way to encode that constraint as well?
And my next question is, can I make an unsafe state – a valid state which results
in a failure, an illegal state?
I figure there is probably a completely different approach involved where the
type system doesn’t even look similar to the problem, and where there wouldn’t
even be work for the user to do in the puzzle to generate the intermediate
states, but what would it look like?