6

変更可能な参照に頼る必要なく、let rec を使用して無限の循環リストを作成することが可能です。

let rec xs = 1 :: 0 :: xs ;;

しかし、これと同じ手法を使用して、有限リストを受け取り、その無限循環バージョンを返す関数を作成できますか? 書いてみた

let rec cycle xs = 
    let rec result = go xs and
            go = function
              | [] -> result
              | (y::ys) -> y :: go ys in
    result
;;

しかし、次のエラーが発生しました

エラー: この種の式は `let rec' の右辺として使用できません

4

3 に答える 3

5

黒魔術を使用してもかまわない場合は、次のコードを試すことができます。

let cycle l =
  if l = [] then invalid_arg "cycle" else
  let l' = List.map (fun x -> x) l in   (* copy the list *)
  let rec aux = function
    | [] -> assert false
    | [_] as lst ->   (* find the last cons cell *)
        (* and set the last pointer to the beginning of the list *)
        Obj.set_field (Obj.repr lst) 1 (Obj.repr l')
    | _::t -> aux t
  in aux l'; l'

Obj モジュールを使用しないことを強くお勧めします。一方で、この種の禁じられた芸術を使用することが知られている強力なプログラムとライブラリ (Coq、Jane Street's Core、Batterys を含む) があります。

于 2016-02-15T23:25:13.380 に答える
3

camlspotterの答えはすでに十分です。ここでさらにいくつかのポイントを追加したいと思います。

まず、 の問題についてはwrite a function that receives a finite list and returns an infinite, circular version of it、コード/実装レベルで実行できますが、実際に関数を使用すると、スタックオーバーフローの問題が発生し、決して返されません。

あなたがやろうとしていたことの簡単なバージョンは次のようなものです:

let rec circle1 xs = List.rev_append (List.rev xs) (circle1 xs)
val circle: 'a list -> 'a list = <fun>

コンパイルでき、理論的には正しいです。[1;2;3]で、生成するはずです[1;2;3;1;2;3;1;2;3;1;2;3;...]。

ただし、その実行は無限であり、最終的にはスタックオーバーフローになるため、もちろん失敗します。

では、なぜlet rec circle2 = 1::2::3::circle2機能するのでしょうか。

実行するとどうなるか見てみましょう。

まず、circle2は値で、リストです。OCaml がこの情報を取得すると、リストのメモリ表現を使用して circle2 の静的アドレスを作成できます。

つまり、int 1 のノードと int 2 のノードのアドレスと int 3 のノードのアドレスと circle2 のアドレス1::2::3::circle2です。Node (1, Node (2, Node (3, circle2)))でも、circle2 のアドレスはもう知っていますよね？OCaml は circle2 のアドレスをそこに置くだけです。

すべてが機能します。

また、この例を通して、このように定義された無限の円で囲まれたリストは、実際には限られたメモリを消費しないという事実も知ることができます。すべてのメモリを消費する実際の無限リストを生成するのではなく、円が終了すると、リストの先頭に「戻る」だけです。

の例に戻りましょうcircle1。Circle1 は関数です。はい、アドレスがありますが、それは必要ありません。必要なのは、関数 application のアドレスですcircle1 xs。これは circle2 とは異なり、アドレスを取得するために何かを計算する必要があることを意味する関数アプリケーションです。そう、

OCaml は を実行しList.rev xs、次にアドレスを取得しようとし、circle1 xsそれから繰り返し、繰り返します。

では、なぜ私たちは時々 を得るのError: This kind of expression is not allowed as right-hand side of 'let rec'ですか?

http://caml.inria.fr/pub/docs/manual-ocaml/extn.html#s%3aletrecvaluesから

let rec バインディング構造は、再帰関数の定義に加えて、次のような非関数値の再帰定義の特定のクラスもサポートします。

let rec name1 = 1 :: name2 and name2 = 2 :: name1 を expr 内で循環リスト 1::2::1::2::… にバインドし、name2 を循環リスト 2::1:: にバインドします。 2::1::…非公式には、受け入れられる定義のクラスは、定義された名前が関数本体内またはデータ コンストラクターへの引数としてのみ発生する定義で構成されます。

let recバインディングを定義するために使用する場合は、 let rec name. これnameは、関数本体またはデータ コンストラクターのいずれかでのみ使用できます。

前の 2 つの例でcircle1は、 は関数本体 ( let rec circle1 = fun xs -> ...)circle2内にあり、データ コンストラクター内にあります。

を行うlet rec circle = circleと、円が 2 つの許可されたケースにないため、エラーが発生します。let rec x = let y = x in y繰り返しますが、 x はコンストラクターまたは関数にないため、どちらも行いません。

ここにも明確な説明があります：

https://realworldocaml.org/v1/en/html/imperative-programming-1.html

セクションLimitations of let rec

于 2014-10-21T12:20:18.533 に答える