4

次の Haskell のデータ型は、OCaml または SML でどのように表現できますか?

newtype Fix f = In (f (Fix f))
4

2 に答える 2

18

私はすでにメーリングリストでこの質問に答えました(そして、あなたが2つの異なる場所で2、3日遅れることなく質問をすることを少し不快に思っていると言わなければなりません.ここで再現します。

OCaml は上位の型変数をサポートしていないため、ここで問題が発生します。この宣言でfは、 は「型」ではなく、「型演算子」 (kind * -> *) です。OCaml で同じことを行うには、ファンクターを使用できます (Haskell ファンクターではありません。OCaml では、「ファンクター」という言葉は、他のモジュール/ファンクターに依存する可能性のある高次モジュールを示します)。ファンクターは高カインドです。

module type ParamType = sig
  type ('a, 'b) t
end

module Fix (M : ParamType) = struct
  type 'b fix = In of ('b fix, 'b) M.t
end

module List = struct
  module Param = struct
    type ('a, 'b) t = Nil | Cons of 'b * 'a
  end
  include Fix(Param)
end

open List.Param
open List

let rec to_usual_list =
  function
  | In Nil -> []
  | In (Cons (x, xs)) -> x :: to_usual_list xs

良いニュースは、OCaml が iso-recursive 型ではなく equi-recursive 型もサポートしていることです。これにより、各再帰レイヤーで "In" ラッパーを削除できます。そのためには、「-rectypes」オプションを使用して、incumbing モジュール (およびインターフェイスを介してこの等再帰も参照するすべてのモジュール) をコンパイルする必要があります。次に、次のように記述できます。

module type ParamType = sig
  type ('a, 'b) t
end

module EqFix (M : ParamType) = struct
  type 'b fix = ('b fix, 'b) M.t
end

module EqList = struct
  module Param = struct
    type ('a, 'b) t = Nil | Cons of 'b * 'a
  end
  include EqFix(Param)
end

open EqList.Param

let rec to_usual_list =
  function
  | Nil -> []
  | (Cons (x, xs)) -> x :: to_usual_list xs

モジュールの構文は非常に重く、恐ろしく見えるかもしれません。ファーストクラスのモジュールを使用して、これらの用途の一部をファンクターから単純な関数に移すことができます。最初は「簡単な」方法から始めることにしました。

より高次の変数への羨望は、OCaml 型の崇拝者 (または、何らかの (良い!) 理由で Functional County のこれらの地域をさまようようになった Haskeller) にとっておそらく最も深刻な病気です。実際には、これを使わなくてもそれほど問題はありませんが、モナド変換子を多用すると、このファンクターのステップによって実際に複雑になります。これが、ここではあまり一般的なスタイルではない理由の 1 つです。また、それらをサポートしている言語の高カインド変数の不完全性について考えることで、気を散らすこともできます。任意の型レベル関数ではなく、コンストラクターのポリモーフィズムへの制限により、必要以上に表現力が低下します。完全に完璧な高階型の抽象化の詳細にたどり着いた日には、OCaml がそこに飛びつくのではないでしょうか?

于 2012-10-21T08:28:15.647 に答える
2

OCaml では型コンストラクタを抽象化できないと思います。Fix の特定のアプリケーションでは、 を使用して同様の効果を得ることができる-rectypesと思います。

$ ghci
GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> newtype Fix f = In (f (Fix f))
Prelude> type L = Fix []
Prelude> let w = In [] :: L
Prelude> let x = In [x] :: L

$ ocaml -rectypes
        OCaml version 4.00.0

# type l = l list;;
type l = l list
# ([] : l);;
- : l = []
# let rec x = [x];;
val x : 'a list as 'a = [[[...]]]
# (x : l);;
- : l = [[[...]]]

私はモジュール タイプの専門家ではありません。おそらく、モジュールを使用してこれよりも近づく方法があります。モジュールシステムを使用すると、すべてが可能に見えます。

于 2012-10-21T05:24:13.743 に答える