OCaml의 FIx 데이터 타입

Question

하스켈의 다음 데이터 타입은 어떻게 OCaml 또는 SML로 표현 될 수 있습니까?

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

Answer 1

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 = [[[...]]] 

저는 모듈 유형 전문가가 아닙니다. 모듈을 사용하여 이보다 더 가깝게 접근 할 수있는 방법이있을 것입니다. 모듈 시스템을 사용하면 모든 것이 가능해 보입니다.

Answer 2

나는 이미 answered this question on the mailing-list입니다. (그리고 나는 그럴 수있는 노력의 중복 때문에 좋은 하루를 지내지 않는 두 개의 다른 장소에서 질문을하는 것이 다소 불쾌합니다.)하지만 여기에서 재현 해 봅시다. .

OCaml이 더 높은 순위의 유형 변수를 지원하지 않기 때문에 여기에서 어려움이 있습니다. 이 선언에서 f은 "유형"이 아니며 " 유형의 연산자"(종류 * -> *)입니다. OCaml에서 같은 것을하기 위해서, 당신은 펑터를 사용할 수 있습니다 (OCaml에서 "functor"라는 단어는 다른 모듈/펑터에 의존하는 상위 모듈을 나타냄); 펑터는 더 높은 종류입니다.

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로는 오히려 당신이 각 재귀 계층에서 래퍼 "에서"를 제거 할 수 있습니다 이소 - 재귀 유형보다 동등 재귀를 지원한다는 것입니다. 이를 위해서는 increcting 모듈 (및 인터페이스를 통해이 equirecursion을 볼 수있는 모든 모듈)을 "-rectypes"옵션과 함께 컴파일해야합니다. 그러면 다음과 같이 쓸 수 있습니다 :

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 

모듈 구문이 매우 무거워서 무서울 수 있습니다. 당신이 1 급 모듈을 사용하여 이들 중 일부를 펑터에서 간단한 함수로 옮길 수 있다고 주장한다면. 먼저 "간단하게" 방법을 선택합니다.

높은-kinded 변수시기는 아마도 가장 심각한 질병 약 OCaml의 유형 숭배 (또는 Haskellers 그 기능 군의 이러한 부분에서 방황 온 일부 (좋아!) 이유 에 대한). 실제로 우리는 을 사용하지 않고도 문제가 없지만 모나드 변압기를 많이 사용하면은 매우 인기있는 스타일이 아닌이 Functor 단계에 의해 실제로 복잡해집니다. 높은 종류의 변수가 지원되는 언어로 불완전하다는 생각을하면 혼란 스러울 수도 있습니다. 임의의 유형 수준 함수가 아닌 생성자 다형성에 대한 제한은 사용자가 원하는 것보다 표현력이 부족합니다. 우리는 절대적으로 완벽한 고차원 타입 추상화에 대한 세부 사항을 연구 한 날에 OCaml이 그것에 뛰어들 것입니까?