F# волк козья капуста

Question

Поэтому прежде всего я прошу прощения за этот вопрос. Но статья "Побег из Цурга" мне очень помогла, и я мог написать свое собственное решение проблемы капусты козьего волка. Я размещаю свой код ниже. Я хочу, чтобы ты сказал мне

1. Если мой код написан в истинном духе F# и функционального программирования

2. Это оптимальное и хорошее решение проблемы

   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

Код выглядит довольно функционально. Я бы внес несколько изменений. Во-первых, я бы использовал наборы для представления ходов, а также есть несколько небольших предложений...

Представление. Вы представляете смертельные комбинации, используя список, так ["Goat"; "Wolf"] это не то же самое, что ["Wolf"; "Goat"] и если ваш алгоритм генерирует ход в другом порядке, он не будет определять его как смертельный ход. Вы должны попытаться найти представления, где это не может произойти, поэтому я бы изменил представление, чтобы использовать наборы:

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

в isMoveDeadly Затем вы можете преобразовать перемещение в набор, используя (но, возможно, было бы лучше изменить код, чтобы использовать наборы везде):

let move = set list1

Ненужное обобщение. Помимо функции isMoveDeadly всегда занимает DeadlyMoves в качестве второго аргумента, чтобы я не передавал его в качестве аргумента (это ненужное обобщение), и я написал бы:

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

Совет по эффективности. в MoveRight функция, которую вы используете list @ [element] шаблон, который очень неэффективен. Это означает, что вам нужно скопировать весь list добавить элемент в конец. Более эффективно добавлять элементы вперед, используя element::list (меньше копирование), а затем перевернуть список. Я полагаю, вам даже не нужно переворачивать список, если вы представляете смертельные ходы в виде набора, поэтому я бы написал:

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

Представление (снова). Вы реализовали свой собственный ListDiff Функция, чтобы узнать, каких животных нет в данном списке. Это говорит о том, что использование наборов (вместо списков) действительно будет лучшим представлением. Если вы переключаетесь на наборы, вы можете использовать встроенную функцию Set.difference вместо.