단 형성 제한이란 무엇입니까?

단 형성 제한이란 무엇입니까?

---

예를 들어 포인트 프리 정의를 사용할 때 하스켈 컴파일러가 내가 예상했던 것보다 덜 다형성 인 유형을 추론하는 방법에 대해 궁금합니다.

문제는 이전 버전의 컴파일러에서 기본적으로 설정되어있는 "단 형성 제한"인 것 같습니다.

다음 하스켈 프로그램을 고려하십시오.

{-# LANGUAGE MonomorphismRestriction #-}

import Data.List(sortBy)

plus = (+)
plus' x = (+ x)

sort = sortBy compare

main = do
  print $ plus' 1.0 2.0
  print $ plus 1.0 2.0
  print $ sort [3, 1, 2]

이것을 컴파일하면 ghc오류가 발생하지 않고 실행 파일의 출력은 다음과 같습니다.

3.0
3.0
[1,2,3]

main본문을 다음과 같이 변경하면 :

main = do
  print $ plus' 1.0 2.0
  print $ plus (1 :: Int) 2
  print $ sort [3, 1, 2]

컴파일 시간 오류가 발생하지 않고 출력은 다음과 같습니다.

3.0
3
[1,2,3]

예상대로. 그러나 다음과 같이 변경하려고하면 :

main = do
  print $ plus' 1.0 2.0
  print $ plus (1 :: Int) 2
  print $ plus 1.0 2.0
  print $ sort [3, 1, 2]

유형 오류가 발생합니다.

test.hs:13:16:
    No instance for (Fractional Int) arising from the literal ‘1.0’
    In the first argument of ‘plus’, namely ‘1.0’
    In the second argument of ‘($)’, namely ‘plus 1.0 2.0’
    In a stmt of a 'do' block: print $ plus 1.0 2.0

sort다른 유형으로 두 번 호출하려고 할 때도 마찬가지입니다 .

main = do
  print $ plus' 1.0 2.0
  print $ plus 1.0 2.0
  print $ sort [3, 1, 2]
  print $ sort "cba"

다음 오류가 발생합니다.

test.hs:14:17:
    No instance for (Num Char) arising from the literal ‘3’
    In the expression: 3
    In the first argument of ‘sort’, namely ‘[3, 1, 2]’
    In the second argument of ‘($)’, namely ‘sort [3, 1, 2]’

• 왜 ghc갑자기 그것이 plus다형성이 아니며 Int논쟁이 필요 하다고 생각 합니까? 에 대한 유일한 참조 Int는 의 응용 프로그램 에 plus있습니다. 정의가 명확하게 다형성 일 때 어떻게 문제가 될 수 있습니까?
• 왜 ghc갑자기 인스턴스 가 sort필요 하다고 생각 Num Char합니까?

또한 다음과 같이 함수 정의를 자체 모듈에 배치하려고하면

{-# LANGUAGE MonomorphismRestriction #-}

module TestMono where

import Data.List(sortBy)

plus = (+)
plus' x = (+ x)

sort = sortBy compare

컴파일 할 때 다음 오류가 발생합니다.

TestMono.hs:10:15:
    No instance for (Ord a0) arising from a use of ‘compare’
    The type variable ‘a0’ is ambiguous
    Relevant bindings include
      sort :: [a0] -> [a0] (bound at TestMono.hs:10:1)
    Note: there are several potential instances:
      instance Integral a => Ord (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      instance Ord () -- Defined in ‘GHC.Classes’
      instance (Ord a, Ord b) => Ord (a, b) -- Defined in ‘GHC.Classes’
      ...plus 23 others
    In the first argument of ‘sortBy’, namely ‘compare’
    In the expression: sortBy compare
    In an equation for ‘sort’: sort = sortBy compare

• 왜이다 ghc다형성 유형을 사용할 수 Ord a => [a] -> [a]에 대한 sort?
• 왜 않는 ghc치료를 plus하고 plus'다르게? plus다형성 유형을 가져야 Num a => a -> a -> a하고 이것이 유형 과 어떻게 다른지 실제로 알지 못하지만 오류 sort만 sort발생합니다.

마지막으로 sort, 파일 의 정의를 주석으로 처리하면 컴파일됩니다. 그러나 내가 그것을로드하고 ghci내가 얻는 유형을 확인 하려고 하면 :

*TestMono> :t plus
plus :: Integer -> Integer -> Integer
*TestMono> :t plus'
plus' :: Num a => a -> a -> a

유형이 plus다형성 이 아닌 이유는 무엇 입니까?

---

^{이것은 메타 질문 에서 논의 된 하스켈의 단 형성 제한에 대한 표준 질문 입니다.}

---

단 형성 제한이란 무엇입니까?

단사 사상 제한 하스켈 위키에 의해 명시된 바와 같이이다 :

Haskell 유형 추론의 반 직관적 인 규칙. 유형 서명을 제공하는 것을 잊은 경우이 규칙은 "유형 기본값"규칙을 사용하여 특정 유형으로 자유 유형 변수를 채 웁니다.

이것이 의미하는 바는 어떤 상황 에서 타입이 모호하면 (즉, 다형성) 컴파일러가 그 타입을 모호하지 않은 것으로 인스턴스화 하도록 선택 한다는 것입니다.

어떻게 고치나요?

우선 항상 명시 적으로 형식 서명을 제공 할 수 있으며 이렇게하면 제한 트리거를 피할 수 있습니다.

plus :: Num a => a -> a -> a
plus = (+)    -- Okay!

-- Runs as:
Prelude> plus 1.0 1
2.0

또는 함수를 정의하는 경우 점없는 스타일을 피하고 예를 들어 다음과 같이 작성할 수 있습니다.

plus x y = x + y

끄기

제한을 해제하기 만하면 코드를 수정하기 위해 아무 작업도 수행 할 필요가 없습니다. 동작은 두 가지 확장에 의해 제어됩니다. MonomorphismRestriction활성화 (기본값)하고 NoMonomorphismRestriction비활성화합니다.

파일 맨 위에 다음 행을 넣을 수 있습니다.

{-# LANGUAGE NoMonomorphismRestriction #-}

GHCi를 사용하는 경우 다음 :set명령을 사용하여 확장을 활성화 할 수 있습니다 .

Prelude> :set -XNoMonomorphismRestriction

ghc명령 줄에서 확장을 활성화하도록 지정할 수도 있습니다 .

ghc ... -XNoMonomorphismRestriction

참고 : 명령 줄 옵션을 통해 확장을 선택하는 것보다 첫 번째 옵션을 선호해야합니다.

이것 및 기타 확장에 대한 설명은 GHC 페이지 를 참조하십시오 .

완전한 설명

모노 모피 즘 제한이 무엇인지, 왜 도입되었고 어떻게 작동하는지 이해하기 위해 알아야 할 모든 것을 아래에 요약하려고합니다.

예

다음과 같은 사소한 정의를 사용하십시오.

plus = (+)

당신의 모든 발생을 교체 할 수 있도록 생각할 것 +와를 plus. 특히 이후 (+) :: Num a => a -> a -> a당신은 또한 가지고 기대 plus :: Num a => a -> a -> a.

불행히도 이것은 사실이 아닙니다. 예를 들어 GHCi에서 다음을 시도합니다.

Prelude> let plus = (+)
Prelude> plus 1.0 1

다음과 같은 출력을 얻습니다.

<interactive>:4:6:
    No instance for (Fractional Integer) arising from the literal ‘1.0’
    In the first argument of ‘plus’, namely ‘1.0’
    In the expression: plus 1.0 1
    In an equation for ‘it’: it = plus 1.0 1

^{:set -XMonomorphismRestriction최신 GHCi 버전 이 필요할 수 있습니다 .}

그리고 실제로 유형이 plus우리가 기대하는 것과 다르다는 것을 알 수 있습니다.

Prelude> :t plus
plus :: Integer -> Integer -> Integer

무슨 일이 있었는지 컴파일러 plus는 type Num a => a -> a -> a, 다형성 유형을 보았습니다 . 또한 위의 정의는 나중에 설명 할 규칙에 해당하므로 type 변수 를 기본값 으로 사용하여 유형을 단일형으로 만들기로 결정했습니다 a. 기본값은 Integer우리가 볼 수있는 것입니다.

위의 코드를 사용하여 컴파일 하려고 ghc하면 오류가 발생하지 않습니다. 이는 대화 형 정의를 처리 하는 방법 ghci(및 처리 해야 함 ) 때문입니다. 기본적으로 입력 된 모든 문 은 다음 사항을 고려하기 전에 완전히 유형 검사 ghci되어야합니다 . 즉, 모든 문이 별도의 모듈 에있는 것과 같습니다 . 나중에 이것이 왜 중요한지 설명하겠습니다.

다른 예

다음 정의를 고려하십시오.

f1 x = show x

f2 = \x -> show x

f3 :: (Show a) => a -> String
f3 = \x -> show x

f4 = show

f5 :: (Show a) => a -> String
f5 = show

이 모든 함수가 동일한 방식으로 작동하고 동일한 유형, 즉 show: 유형을 갖기를 기대합니다 Show a => a -> String.

그러나 위의 정의를 컴파일 할 때 다음과 같은 오류가 발생합니다.

test.hs:3:12:
    No instance for (Show a1) arising from a use of ‘show’
    The type variable ‘a1’ is ambiguous
    Relevant bindings include
      x :: a1 (bound at blah.hs:3:7)
      f2 :: a1 -> String (bound at blah.hs:3:1)
    Note: there are several potential instances:
      instance Show Double -- Defined in ‘GHC.Float’
      instance Show Float -- Defined in ‘GHC.Float’
      instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      ...plus 24 others
    In the expression: show x
    In the expression: \ x -> show x
    In an equation for ‘f2’: f2 = \ x -> show x

test.hs:8:6:
    No instance for (Show a0) arising from a use of ‘show’
    The type variable ‘a0’ is ambiguous
    Relevant bindings include f4 :: a0 -> String (bound at blah.hs:8:1)
    Note: there are several potential instances:
      instance Show Double -- Defined in ‘GHC.Float’
      instance Show Float -- Defined in ‘GHC.Float’
      instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      ...plus 24 others
    In the expression: show
    In an equation for ‘f4’: f4 = show

그래서 f2및 f4컴파일되지 않습니다. 또한 GHCi에서 이러한 함수를 정의하려고 할 때 오류가 발생하지 않지만 f2및 유형 f4은 () -> String!

단사 사상 제한이 만드는 것입니다 f2및 f4단형 유형을 필요로하며, 다른 행동 bewteen ghc와 ghci차이로 인해이다 디폴트 규칙 .

언제 발생합니까?

보고서에 정의 된대로 Haskell 에는 두 가지 유형의 바인딩이 있습니다. 함수 바인딩 및 패턴 바인딩. 함수 바인딩은 함수의 정의에 불과합니다.

f x = x + 1

구문은 다음과 같습니다.

<identifier> arg1 arg2 ... argn = expr

^{모듈로 가드 및 where선언. 그러나 그들은 실제로 중요하지 않습니다.}

여기서 최소한 하나의 인수 가 있어야합니다 .

패턴 바인딩은 다음 형식의 선언입니다.

<pattern> = expr

^{다시, 모듈로 가드.}

참고 변수 패턴입니다 바인딩, 그래서 :

plus = (+)

A는 패턴 바인딩. 패턴 plus(변수)을 표현식에 바인딩합니다 (+).

패턴 바인딩이 변수 이름으로 만 구성된 경우이를 단순 패턴 바인딩 이라고합니다 .

단 형성 제한은 단순 패턴 바인딩에 적용됩니다!

음, 공식적으로 우리는 다음과 같이 말해야합니다.

선언 그룹 은 상호 종속적 인 바인딩의 최소 집합입니다.

^{보고서 의 섹션 4.5.1 .}

그리고 ( 보고서 의 섹션 4.5.5 ) :

주어진 선언 그룹은 다음 과 같은 경우에만 제한되지 않습니다 .

1. 그룹의 모든 변수는 함수 바인딩 (예 :) f x = x또는 단순 패턴 바인딩 (예 plus = (+): 섹션 4.4.3.2)에 의해 바인딩됩니다 .

2. 단순 패턴 바인딩으로 바인딩 된 그룹의 모든 변수에 대해 명시 적 유형 서명이 제공됩니다. (예 :) plus :: Num a => a -> a -> a; plus = (+).

^{내가 추가 한 예.}

따라서 제한된 선언 그룹은 단순하지 않은 패턴 바인딩 (예 : (x:xs) = f something또는 (f, g) = ((+), (-)))이 있거나 유형 서명이없는 간단한 패턴 바인딩 (에서와 같이 plus = (+))이있는 그룹입니다.

단 형성 제한은 제한된 선언 그룹에 영향을줍니다 .

대부분의 시간 동안 당신은 상호 재귀 함수를 정의하지 않으며, 따라서 선언 그룹은이된다 바인딩.

그것은 무엇을합니까?

단 형성 제한은 보고서의 섹션 4.5.5에있는 두 가지 규칙에 의해 설명됩니다 .

첫 번째 규칙

다형성에 대한 일반적인 Hindley-Milner 제한은 환경에서 자유롭게 발생하지 않는 유형 변수 만 일반화 할 수 있다는 것입니다. 또한 제한된 선언 그룹의 제한된 유형 변수는 해당 그룹의 일반화 단계에서 일반화되지 않을 수 있습니다. (유형 변수가 어떤 유형 클래스에 속해야하는 경우 제한된다는 것을 상기하십시오. 섹션 4.5.2를 참조하십시오.)

강조 표시된 부분은 단 형성 제한이 도입하는 것입니다. 그것은 말합니다 경우 유형이 다형성 (즉, 그것이 어떤 종류의 변수를 포함) 및 해당 유형의 변수가 제한된다 (즉, 그것의 클래스 제약 조건이 : 예를 들어 유형 Num a => a -> a -> a이 포함되어 있기 때문에 다형성 a과이 있기 때문에 contrained a제약 조건을 가지고 Num그 위에 .) 그러면 일반화 할 수 없습니다.

간단히 말해서 일반화하지 않는 것은 함수 의 사용 이 plus그 유형을 변경할 수 있음을 의미합니다 .

정의가있는 경우 :

plus = (+)

x :: Integer
x = plus 1 2

y :: Double
y = plus 1.0 2

그러면 유형 오류가 발생합니다. 컴파일러가 선언에서 plus호출 되는 것을 볼 때 유형 변수 를 통합 하므로 유형 은 다음과 같습니다.IntegerxaIntegerplus

Integer -> Integer -> Integer

그것의 정의를 확인 입력 할 때하지만, y그것은 그 볼 plus에 적용되는 Double인수와 유형이 일치하지 않습니다.

plus오류없이 계속 사용할 수 있습니다 .

plus = (+)
x = plus 1.0 2

이 경우의 유형 plus은 먼저로 추론 Num a => a -> a -> a되지만 제약 x이 1.0필요한 경우 의 정의에서 사용 Fractional하면로 변경됩니다 Fractional a => a -> a -> a.

이론적 해석

보고서는 다음과 같이 말합니다.

규칙 1은 두 가지 이유로 요구되며, 둘 다 상당히 미묘합니다.

• 규칙 1은 계산이 예기치 않게 반복되는 것을 방지합니다. 예를 들어 genericLength는 Data.List형식이 다음과 같이 지정된 표준 함수 (라이브러리 내 )입니다.

  genericLength :: Num a => [b] -> a
  

  이제 다음 표현식을 고려하십시오.

  let len = genericLength xs
  in (len, len)
  

  len한 번만 계산되어야하는 것처럼 보이지만 규칙 1이 없으면 두 번의 서로 다른 오버로딩 각각에서 한 번씩 두 번 계산 될 수 있습니다. 프로그래머가 실제로 계산이 반복되기를 원하면 명시 적 유형 서명이 추가 될 수 있습니다.

  let len :: Num a => a
      len = genericLength xs
  in (len, len)
  

이 점에서 위키 의 예는 더 명확하다고 생각합니다. 기능을 고려하십시오.

f xs = (len, len)
  where
    len = genericLength xs

경우 len의 유형 다형성이었다 f될 것이다 :

f :: Num a, Num b => [c] -> (a, b)

따라서 튜플의 두 요소는 (len, len)실제로 다른 값 이 될 수 있습니다 ! 그러나 이것은 두 개의 다른 값을 얻기 위해에서 수행 된 계산을 반복 genericLength 해야 함을 의미 합니다.

여기서의 근거는 다음과 같습니다. 코드에는 하나의 함수 호출이 포함되어 있지만이 규칙을 도입하지 않으면 직관적이지 않은 두 개의 숨겨진 함수 호출 이 생성 될 수 있습니다 .

단 형성 제한으로 유형 f은 다음과 같습니다.

f :: Num a => [b] -> (a, a)

이런 식으로 계산을 여러 번 수행 할 필요가 없습니다.

• 규칙 1은 모호성을 방지합니다. 예를 들어 선언 그룹을 고려하십시오.

  [(n, s)] = t를 읽습니다.

  reads형식이 시그니처에 의해 제공되는 표준 함수 임을 상기하십시오.

  읽기 :: (읽기 a) => 문자열-> [(a, 문자열)]

  Without Rule 1, n would be assigned the type ∀ a. Read a ⇒ a and s the type ∀ a. Read a ⇒ String. The latter is an invalid type, because it is inherently ambiguous. It is not possible to determine at what overloading to use s, nor can this be solved by adding a type signature for s. Hence, when non-simple pattern bindings are used (Section 4.4.3.2 ), the types inferred are always monomorphic in their constrained type variables, irrespective of whether a type signature is provided. In this case, both n and s are monomorphic in a.

Well, I believe this example is self-explanatory. There are situations when not applying the rule results in type ambiguity.

If you disable the extension as suggest above you will get a type error when trying to compile the above declaration. However this isn't really a problem: you already know that when using read you have to somehow tell the compiler which type it should try to parse...

Second rule

2. Any monomorphic type variables that remain when type inference for an entire module is complete, are considered ambiguous, and are resolved to particular types using the defaulting rules (Section 4.3.4 ).

This means that. If you have your usual definition:

plus = (+)

This will have a type Num a => a -> a -> a where a is a monomorphic type variable due to rule 1 described above. Once the whole module is inferred the compiler will simply choose a type that will replace that a according to the defaulting rules.

The final result is: plus :: Integer -> Integer -> Integer.

Note that this is done after the whole module is inferred.

This means that if you have the following declarations:

plus = (+)

x = plus 1.0 2.0

inside a module, before type defaulting the type of plus will be: Fractional a => a -> a -> a (see rule 1 for why this happens). At this point, following the defaulting rules, a will be replaced by Double and so we will have plus :: Double -> Double -> Double and x :: Double.

Defaulting

As stated before there exist some defaulting rules, described in Section 4.3.4 of the Report, that the inferencer can adopt and that will replace a polymorphic type with a monomorphic one. This happens whenever a type is ambiguous.

For example in the expression:

let x = read "<something>" in show x

here the expression is ambiguous because the types for show and read are:

show :: Show a => a -> String
read :: Read a => String -> a

So the x has type Read a => a. But this constraint is satisfied by a lot of types: Int, Double or () for example. Which one to choose? There's nothing that can tell us.

In this case we can resolve the ambiguity by telling the compiler which type we want, adding a type signature:

let x = read "<something>" :: Int in show x

Now the problem is: since Haskell uses the Num type class to handle numbers, there are a lot of cases where numerical expressions contain ambiguities.

Consider:

show 1

What should the result be?

As before 1 has type Num a => a and there are many type of numbers that could be used. Which one to choose?

Having a compiler error almost every time we use a number isn't a good thing, and hence the defaulting rules were introduced. The rules can be controlled using a default declaration. By specifying default (T1, T2, T3) we can change how the inferencer defaults the different types.

An ambiguous type variable v is defaultable if:

• v appears only in contraints of the kind C v were C is a class (i.e. if it appears as in: Monad (m v) then it is not defaultable).
• at least one of these classes is Num or a subclass of Num.
• all of these classes are defined in the Prelude or a standard library.

A defaultable type variable is replaced by the first type in the default list that is an instance of all the ambiguous variable’s classes.

The default default declaration is default (Integer, Double).

For example:

plus = (+)
minus = (-)

x = plus 1.0 1
y = minus 2 1

The types inferred would be:

plus :: Fractional a => a -> a -> a
minus :: Num a => a -> a -> a

which, by defaulting rules, become:

plus :: Double -> Double -> Double
minus :: Integer -> Integer -> Integer

Note that this explains why in the example in the question only the sort definition raises an error. The type Ord a => [a] -> [a] cannot be defaulted because Ord isn't a numeric class.

Extended defaulting

Note that GHCi comes with extended defaulting rules (or here for GHC8), which can be enabled in files as well using the ExtendedDefaultRules extensions.

The defaultable type variables need not only appear in contraints where all the classes are standard and there must be at least one class that is among Eq, Ord, Show or Num and its subclasses.

Moreover the default default declaration is default ((), Integer, Double).

This may produce odd results. Taking the example from the question:

Prelude> :set -XMonomorphismRestriction
Prelude> import Data.List(sortBy)
Prelude Data.List> let sort = sortBy compare
Prelude Data.List> :t sort
sort :: [()] -> [()]

in ghci we don't get a type error but the Ord a constraints results in a default of () which is pretty much useless.

Useful links

There are a lot of resources and discussions about the monomorphism restriction.

Here are some links that I find useful and that may help you understand or deep further into the topic:

• Haskell's wiki page: Monomorphism Restriction
• The report
• An accessible and nice blog post
• Sections 6.2 and 6.3 of A History Of Haskell: Being Lazy With Class deals with the monomorphism restriction and type defaulting

참고URL : https://stackoverflow.com/questions/32496864/what-is-the-monomorphism-restriction