F#狼山羊白菜

Question

首先,我很抱歉提出这个问题.但是"逃离Zurg"文章给了我很多帮助,我可以为Wolf Goat Cabbage问题编写自己的解决方案.我在下面提出我的代码.我要你告诉我

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.