3

cycleHaskell関数のアナログを実装したいと思います。

リスト要素を明示的に渡すと、それは些細なことのように思えます:

let cycle a b c =
  let rec l = a::b::c::l in
  l

cycle 1 2 3再帰リストを生成します1, 2, 3, 1...

しかし、別の通常のリストに基づいて再帰リストを生成するにはどうすればよいでしょうか?

let cycle lst = ...

使用法

cycle [1;2;3]

4

5 に答える 5

3

ML のような熱心な言語では、ストリームを使用する必要があります。例えば

# let cycle = Stream.from (fun n -> Some (List.nth [1;2;3] (n mod 3)));;
val cycle : int Stream.t = <abstr>
# Stream.npeek 10 cycle;;
- : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1]
于 2013-10-18T20:02:56.830 に答える
1

私の知る限り、OCaml は、言語の安全でない部分に踏み込みたくない限り、この種のコーディングには向いていません。

cycle言語の安全な部分にこだわって (ただし、第 7 章の拡張機能を使用して)、長さ 3 までのリストに対して機能する (あまり印象的ではない) バージョンを次に示します。

let cycle = function
    | [] -> []
    | [x] -> let rec res = x :: res in res
    | [x; y] -> let rec res = x :: q and q = y :: res in res
    | [x; y; z] -> let rec res = x :: t and t = y :: v and v = z :: res in res
    | _ -> failwith "list too long"

これを任意の長さに拡張する方法は簡単にわかりますが、任意の長さに拡張することはできません。

関数を使用したセッションは次のとおりです。

# #use "cyc.ml";;
val cycle : 'a list -> 'a list = <fun>
# cycle [1;2;3];;
- : int list =
[1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1;
 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2;
 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3;
 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1;
 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2;
 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; ...]

とにかく、これが私にできる最善のことです。お役に立てば幸いです。

于 2013-10-18T19:48:41.713 に答える
1

このような再帰リストを作成する唯一の方法は、Objモジュールを使用することです。

リストをコピーして再帰的にする

let cycle lst = match lst with
  | [] -> []
  | _ ->
    let rec get_last_cell = function
      | [] -> assert false
      | _::[] as last -> last
      | _::tl -> (get_last_cell tl)
    in
    let new_lst = List.map (fun x -> x) lst in
    let last_cell = get_last_cell new_lst in
    Obj.set_field (Obj.repr last_cell) 1 (Obj.repr new_lst);
    new_lst

再帰リストを作成し、新しいコンス セルを挿入する

let cycle lst = match lst with
  | [] -> []
  | hd::tl ->
      let rec loop cell lst =
        match lst with
        | [] -> ()
        | hd::tl ->
            let new_cell = [hd] in
            let new_cell_obj = Obj.repr new_cell in
            let cell_obj = Obj.repr cell in
            Obj.set_field new_cell_obj 1 (Obj.field cell_obj 1);
            Obj.set_field cell_obj 1 new_cell_obj;
            loop new_cell tl
      in
      let rec cyc_lst = hd::cyc_lst in
      loop cyc_lst tl;
      cyc_lst

アイデアは非常に簡単です。

  1. cyc_lst要素が 1 つだけの再帰リストを作成します。
  2. の末尾の直前に 1 つ以上の新しいコンス セルを挿入しcyc_lstます。

例

cycle [1;2]

  1. 再帰リストを作成しますcyc_lst。メモリ内では自己再帰的なコンス セルとして表されます。

    let rec cyc_lst = hd::cyc_lst

.--------.
| | | |
| | +---+-|-+
`->| 1 | * | |
   +---+---+

  2. new_cell2 を唯一の要素として使用して作成する

    let new_cell = [hd]

   セル new_cell
.--------.
| | | |
| | +---+-|-+ +---+---+
`->| 1 | * | | | | 2 | X |
   +---+---+ +---+---+

  3. new_cellテール ポインターを最初のセルに設定する

    Obj.set_field new_cell_obj 1 (Obj.field cell_obj 1)

   セル new_cell
.--------.--------------.
| | | | | |
| | +---+-|-+ +---+-|-+
`->| 1 | * | | | | 2 | * | |
   +---+---+ +---+---+

  4. テールcellポインタをnew_cell

    Obj.set_field cell_obj 1 new_cell_obj

   セル new_cell
-----------------------。
| | | |
| | +---+---+ +---+-|-+
`->| 1 | *------>| 2 | * | |
   +---+---+ +---+---+

このようなリスト操作で GC が問題ないことを願っています。そうでない場合はお知らせください。

于 2013-10-18T22:23:33.353 に答える
0

別の回答のようにストリーム、または遅延リストが必要です。

type 'a llist = LNil | LCons of 'a * 'a llist Lazy.t
let cycle = function
| [] -> invalid_arg "cycle: empty list"
| hd::tl ->
  let rec result =
    LCons (hd, lazy (aux tl))
  and aux = function
    | [] -> result
    | x::xs -> LCons (x, lazy (aux xs)) in
  result
于 2013-10-20T15:35:14.653 に答える
0

そのように定義することもできます

# let cycle items =
    let buf = ref [] in
    let rec next i =
      if !buf = [] then buf := items;
      match !buf with
        | h :: t -> (buf := t; Some h)
        | [] -> None in
    Stream.from next;;
val cycle : 'a list -> 'a Stream.t = <fun>

utop # let test = cycle [1; 2; 3];;
val test : int Stream.t = <abstr> 
utop # Stream.npeek 10 test;;
- : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1]

これは次のとおりです。

http://ocaml.org/tutorials/streams.html

于 2013-10-18T21:02:48.283 に答える