7

私はOCamlを初めて使用し、 list のxインデックスで特定のリストの要素のリストを返す関数を実装しようとしていますy。

たとえば、その関数は次の計算を実行する必要があります。[5,6,7,8], [0, 3] => [5, 8]

一時変数を ML に保存する方法がわかりません。また、それがどのように機能するかについても明確な考えがありません。ただし、指定されたインデックスを指定してリストから要素を見つける方法は知っています。

Listどんなアイデアでも大歓迎ですが、再帰関数を使用してモジュールを避けたいと思います。

4

4 に答える 4

7

一時変数は必要ありません。再帰を使用するだけです。

# let rec indices xs = function
    | i :: is -> (List.nth xs i) :: indices xs is
    | [] -> []
  ;;
val indices : 'a list -> int list -> 'a list = <fun>

# indices [5;6;7;8] [0;3] ;;
- int list = [5; 8]

提供された各インデックスを調べて、次のステップで返されるリストにそれをconsingすることで、リストを構築します。

うまくいけば、これも末尾再帰形式に最適化されますが、それについてはよくわかりません。適切に末尾再帰になるように変更することもできますが、それはあなたに任せます。

于 2012-03-21T05:10:12.837 に答える
3

私は@ftkに提案したジッパーソリューションを誘惑して実装しました。

(* A 'zipper' on the data structure "foo" is a derived data structure
   that represents a position in the data structure "foo", that can be
   filled with an element. You can think of this as a "cursor" on some
   element in the structure, that can moved in various directions to
   point to other elements of the structure. If the structure "foo"
   does not have random access, keeping a zipper allows to access the
   pointed element quickly (instead of having to look at it from the
   top of the structure again each time); its neighbors can be
   acccessed as well by moving the zipper.

   A cursor on a list has this form:

        cursor
          v
   [a; b; c; d; e; f]

   It can be represented as a value of type
     'a list * 'a * 'a list

   where the first list denotes the element before the cursor, and the
   second the elements after it. To be able to access the left
   neighbor of the cursor in constant time, we store the left elements
   in reverse order (rightmost first), so the zipper actually is

   ([b; a], c, [d; e; f])

   Zippers can be adapted to lot of data structures, including in
   particular trees. There are neat ways to define them as the
   "derivative" (in a calculus-like sense) of datatypes. See
   http://en.wikipedia.org/wiki/Zipper_(data_structure) for more
   information.
*)
let move_right = function
  | (left, x, x' :: right) -> (x :: left, x', right)
  | (_, _, []) -> raise Not_found

let move_left = function
  | (x' :: left, x, right) -> (left, x', x :: right)
  | ([], _, _) -> raise Not_found

let elem (left, e, right) = e

(* zipper of a list *)
let zipper = function
  | [] -> raise Not_found
  | x :: xs -> ([], x, xs)

let rec iterate f x = function
  | 0 -> x
  | n -> iterate f (f x) (n - 1)

let get_all data indices =
  let get_next index (pos, zip, acc) =
    let zip' =
      let move = if index < pos then move_left else move_right in
      try iterate move zip (abs (index - pos))
      with Not_found -> invalid_arg ("invalid index " ^ string_of_int index) in
    (index, zip', elem zip' :: acc) in
  let (_pos, _zip, result) =
    List.fold_right get_next indices (0, zipper data, []) in
  result

使用例：

# get_all [0;2;4;6;8;10] [2;0;1;4];;
- : int list = [4; 0; 2; 8]
# get_all [0;2;4;6;8;10] [2;0;1;6;4];;
Exception: Invalid_argument "invalid index 6".

要素を取得する場所のリストが大きい場合は、次のリストよりも大幅に高速になる可能性がありますList.map (List.nth data)。

let slow_get_all data indices = List.map (List.nth data) indices

let init n = Array.to_list (Array.init n (fun i -> i))
let data = init 100_000
let indices = List.map (( * ) 100) (init 1000)

(* some seconds *)
let _ = slow_get_all data indices

(* immediate *)
let _ = get_all data indices

もちろん、これはすべて演習です。実際には、パフォーマンスが重要な場合は、データを配列などのランダムアクセスにより効率的なデータ構造に変換します。

于 2012-03-21T22:13:38.987 に答える
2

mange の答えは、関数型プログラミングの力をうまく示しています。要点を繰り返します。一時変数は必要ありません。 recursion を使用するだけです。

最後のライブラリ呼び出しを取り除きたい場合はList、次のことができます。

  1. mange のindices関数を使用して、関数を再実装しList.nthます。これはあまり楽しいことではなく、xリストの各要素についてリストを体系的に再スキャンすることを避けたいと思うかもしれませんy。

  2. x再帰関数を使用して、とyリストの両方を同時にスキャンします。たとえば、次のことが必要な場合があります。

    • xリストの最初の要素の値と同じ回数だけリストの要素をポップしyます。
    • 残りの listxで、最初の要素を予約し、 の先頭をポップし、残りのとyを続けます。xy

普段のように悪魔が住んでいるので、詳細はお任せします。

于 2012-03-21T15:31:07.370 に答える
1

2 つのリストの関数が必要です。2 番目のリストは、最初のリストのインデックスを提供します。2 つの可能性があります。2 番目のリストが昇順でソートされているか、2 番目のリストがまったくソートされていません。2 番目のリストがソートされている場合、関数はより効率的になります。これは、リストを左から右に効率的にトラバースできるためです。ただし、特定のインデックスを持つ要素へのランダム アクセスは迅速ではありません。

いずれにせよ、末尾再帰ソリューションが可能です。（これは宿題の質問だと思います...）

アイデアは、一時的な変数を使用するのではなく、リストを調べながら結果を構築することです。数学的帰納法の観点から問題を考えてみてください。誘導のベースは何ですか？インデックスの空のリストは空の結果を返します。誘導のステップは何ですか？2 番目のリストから次の指定されたインデックスを取得し、最初のリストの 1 つの要素を結果に追加し、(帰納法により) 他のすべてのインデックスが正しく処理されると想定します。

2 番目のリストが昇順で並べ替えられ、要素が繰り返されていない場合にできることを次に示します。indices_tr4 つの引数を持つ末尾再帰関数です。resultは以前に蓄積された結果のリスト、xsは最初のリストの残りの部分、 はnそのリストの現在のインデックス、 はisインデックスのリストの残りの部分です。

let indices xs is = 
 let rec indices_tr result (x::xs) n = function
   | [] -> result
   | i::is when i==n -> indices_tr (x::result) xs (n+1) is
   | is -> indices_tr result xs (n+1) is
 in
 indices_tr [] xs 0 is
;;

空のリストは処理されないという警告があります。

結果は逆順のリストです。

 # indices [1;3;5;7] [0;1;2];;
 - : int list = [5; 3; 1]

純粋な末尾再帰ソリューションでは、これ以上のことはできません。もちろん、それに List.rev を適用することもできます。

于 2012-03-21T17:13:20.237 に答える