1

初めに、このような質問をして申し訳ありません。しかし、「Zurg からの脱出」の記事は私を大いに助け、オオカミやぎのキャベツ問題に対する独自の解決策を書くことができました。私は自分のコードを下に置いています。教えてほしい

  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
4

1 に答える 1

6

コードはかなり機能的に見えます。私が行ういくつかの変更があります。まず、セットを使用して動きを表現します。いくつかのマイナーな提案もあります...

表現。リストを使用して致命的な組み合わせを表しているため["Goat"; "Wolf"]、["Wolf"; "Goat"]アルゴリズムが他の順序で動きを生成した場合、それは致命的な動きとして検出されません。これが発生しない表現を見つけようとする必要があるため、表現をセットを使用するように変更します。

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

関数ではisMoveDeadly、次を使用して移動をセットに変換できます (ただし、どこでもセットを使用するようにコードを変更する方がよい場合があります)。

let move = set list1

不必要な一般化。余談ですが、関数isMoveDeadlyは常にDeadlyMoves2 番目の引数を取るので、引数として渡さず (これは不要な一般化です)、次のように記述します。

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代わりに組み込み関数を使用できます。

于 2012-07-15T11:24:18.220 に答える