F# Wolf Goat Cabbage

Question

So first of all I am sorry for asking this question. But the "Escape from Zurg" article helped me a lot and I could write my own solution to the Wolf Goat Cabbage Problem. I am positing my code below. I want you to tell me

1. If my code is written in true spirit of F# and functional programming

2. It is an optimal and good solution to the problem

   open System
   
   (* 
     The type direction determines which direction the human is present.
     Left means that Human is present on the left side of the bank.
     Right means human is present on the right side of the bank.
   *)
   type Direction =
     | Left
     | Right
   
   (*
     Master list of animals
   *)
   let Animals = ["Wolf"; "Goat"; "Cabbage"]
   
   let DeadlyCombinations = [["Wolf"; "Goat"];["Goat"; "Cabbage"];]
   
   let isMoveDeadly list1 list2 =
     List.exists (fun n -> n = list1) list2
   
   let rec MoveRight animals =
     match animals with
       | [] -> []
       | head::tail -> 
         if (isMoveDeadly tail DeadlyCombinations) then
           MoveRight tail @ [head]
         else
           Console.WriteLine("Going to move " + head)
           tail
   
   let ListDiff list1 list2 = List.filter (fun n -> List.forall (fun x -> x <> n) list1) list2
   
   let MoveLeft animals = 
     let RightList = ListDiff animals Animals 
     let ShouldTakeAnimal = isMoveDeadly RightList DeadlyCombinations
     if (ShouldTakeAnimal) then
       let x = List.head RightList
       Console.WriteLine("Going to move " + x + " back")
       [x]
     else
       Console.WriteLine("Farmer goes back alone")
       []
   
   let rec Solve direction animals =
       match animals with 
       | [] -> Console.WriteLine("Solved")
       | _ ->
           match direction with
           | Left -> Solve Right (MoveRight animals) 
           | Right -> Solve Left (animals @ (MoveLeft animals))
   
   [<EntryPoint>]
   let main args =
       Solve Left Animals
       0
   

Answer 1

The code looks pretty functional. There are a few changes I'd make. Firstly, I'd use sets to represent moves and there are also a few minor suggestions...

Representation. You're representing deadly combinations using a list, so ["Goat"; "Wolf"] is not the same thing as ["Wolf"; "Goat"] and if your algorithm generates move in the other order, it will not detect it as deadly move. You should try to find representations where this cannot happen, so I would change the representation to use sets:

let DeadlyCombinations = [set ["Wolf"; "Goat"]; set ["Goat"; "Cabbage"];] 

In the isMoveDeadly function, you can then convert the move to a set using (but maybe it would be better to change the code to use sets everywhere):

let move = set list1

Unnecessary generalization. Aside, the function isMoveDeadly always takes DeadlyMoves as the second argument, so I would not pass it as an argument (that is unneeded generalization) and I'd write:

let isMoveDeadly list = 
  let move = set list
  DeadlyCombinations |> List.exists (fun n -> n = move) 

Efficiency tip. In the MoveRight function, you're using list @ [element] pattern which is very inefficient. It means you need to copy the entire list to append the element to the end. It is more efficient to add elements to the front using element::list (less copying) and then reverse the list. I suppose you do not even need to reverse the list if you represent deadly moves as a set, so I'd write:

let rec MoveRight animals = 
  match animals with 
    | [] -> [] 
    | head::tail ->  
      if (isMoveDeadly tail) then 
        head :: (MoveRight tail)
      else 
        Console.WriteLine("Going to move " + head) 
        tail 

Representation (again). You implemented your own ListDiff function to find out what animals are not in a given list. This suggests that using sets (instead of lists) would really be a better representation. If you switch to sets, you could use a built-in function Set.difference instead.