Hindley-Milner 유형 추론의 폴리 유형 이해하기

Question

Hindley–Milner Type Inference 위키 피 디아의 기사를 읽고 있습니다. 지금까지 내가 이해 한 바가 있습니다 :

1. 유형은 모노 타입 또는 폴리 타입으로 분류됩니다.
2. 모노 유형은 int 또는 string과 같은 유형 상수 또는 α 및 β과 같은 유형 변수로 분류됩니다.
3. 유형 상수는 콘크리트 유형 (예 : int 및 string)이거나 유형 생성자 (예 : Map 및 Set) 일 수 있습니다.
4. 유형 변수 (예 : α 및 β)는 콘크리트 유형 (예 : int 및 string)의 자리 표시 자로 작동합니다.

는 지금은 폴리 타입을 이해하는 약간의 어려움에 봉착하지만 하스켈의 비트를 학습 한 후이 내가 그것을 만들 것입니다 :

1. 유형 자체는 유형이있다. 공식적으로 유형의 유형을 유형이라고합니다 (즉, 여러 가지 유형이 있습니다).
2. 콘크리트 종류 (int와 string 등) 및 입력 변수 (α 및 β 등)의 종류 *이다.
3. 타입 생성자 (Map 및 Set 같은) 유형의 람다 추상화 (예를 들어 Set 종류 * -> *이며 Map* -> * -> * 종류이다).

한정자는 무엇을 의미합니까? 예를 들어 ∀α.σ은 무엇을 나타 냅니까? 반면> α 수 -

폴리 타입 ∀α.α있는 기능 : 나는 머리 나하고 더 내가 다음 단락은 더 혼란 내가 얻을 읽기의 꼬리를 만들 수없는 것 동일한 유형의 모든 값을 자체에 매핑하고 identity function은이 유형의 값입니다. 다른 예로서 ∀α. (집합 α) -> int은 모든 유한 집합을 정수로 매핑하는 함수 유형입니다. 구성원 수는이 유형의 값입니다. 예를 들어 유형이 ∀α.α -> ∀α.α과 같이 최상위 수준으로 만 표시 될 수 있으며 유형 구문에 의해 제외되며 해당 유형이 폴리 유형에 포함되므로 유형에 일반 양식 ∀α1. . . ∀αₙ.τ.

Answer 1

먼저 종류와 다형성 유형이 다릅니다. 모든 유형이 같은 종류 (*) 인 HM 유형 시스템을 가질 수 있습니다. 또한 다형성이 없지만 복잡한 유형의 시스템을 가질 수 있습니다.

용어 M 유형 ∀a.t의 경우

, 그것은 어떤 유형 s을 위해 우리가 t에 a에 대한 s을 대체 할 수 있습니다 (종종 t[a:=s]으로 작성하고 우리가 M 유형 t[a:=s]의 것을해야합니다 것을 의미한다. 이것은 다소 유사하다 우리가 여기에서 보편적으로 정량화 변수에 어떤 용어를 대체 할 수 있지만, 논리, 우리는 유형을 취급하고 있습니다.

이 그냥 하스켈에서 당신이 한정사가 표시되지 않습니다, 하스켈에서 일어나는 정확히 무엇이다. 모두 형식 시그니처에 나타나는 유형 변수는 암시 적으로 정량화됩니다. 당신 앞에 forall이 있으면 예를 들어, map이 암시 범용 정량없이

map :: forall a . forall b . (a -> b) -> [a] -> [b] 

등 형

가 입력 변수와 a b 일부 고정 된 의미를 갖는 것 및 map 다형성 않을 것이라고한다.

는

의 HM 알고리즘 구별 (한정사, monotypes없이) 유형 및 타입 스키마 (universaly 정량 유형 폴리 타입). 어떤 곳에서는 형식 스키마 (예 : let)를 사용하는 것이 중요하지만 다른 곳에서는 유형 만 허용됩니다. 이것은 모든 것을 결정할 수있게 만든다.

또한 System F에 대한 기사를 읽어 보시기 바랍니다. 더 복잡한 시스템이므로 유형이 다른 곳에서는 forall이 가능합니다 (따라서 유형은). 유형 유추/확인은 결정할 수 없습니다. forall의 작동 방식을 이해하는 데 도움이됩니다. 시스템 F는 Girard, Lafont and Taylor, Proofs and Types에서 자세하게 설명됩니다.

Answer 2

하스켈에서 l = \x -> t을 고려하십시오. 이것은 나중에 대체 될 변수 x (예 : l 1)이 포함 된 용어 인 t을 나타내는 람다입니다. 마찬가지로 ∀α.σ은 유형이 α 인 경우 α 유형, 즉 f : ∀α.σ 유형을 나타냅니다. 어떤 의미에서는 σ은 α에 달려 있으므로 σ(α) 값을 반환합니다. σ(α)에서 α을 나중에 대체하고 구체적인 유형을 얻습니다.

하스켈에서는 ∀을 생략하고 id : a -> a과 같은 기능을 정의 할 수 있습니다. 한정 기호를 생략 할 수있는 이유는 기본적으로 최상위 수준 (RankNTypes 확장 없음) 만 허용되기 때문입니다. 당신이 id (:t id)의 유형에 대한 ghci을 요구하는 경우에

id2 : a -> a -- I named it id2 since id is already defined in Prelude 
id2 x = x 

, 그것은 a -> a를 반환합니다 : 당신은이 코드 조각을 시도 할 수 있습니다. 보다 정확하게 (보다 이론적 인 유형으로), id의 유형은 ∀a. a -> a입니다.유형 Int이 σ로 대체 할 수 있도록,

val = id2 3 

, 3 종류 Int을 가지고 있으며, 우리는 구체적인 유형 Int -> Int을 얻을 것이다 : 지금, 당신은 당신의 코드를 추가합니다.