컴파일 에러 읽기 - no smaller than the instance head

이 포스트는 정확히 이해한 내용이 아니라 추측만 가득합니다. 의심하면서 읽어주세요

타입 하나를 위한게 아닌, 클래스를 위한 인스턴스

특정 타입을 위한 인스턴스가 아니라, 특정 종류(클래스)의 타입을 위한 인스턴스를 만드는게 가능할까요? 예를 들면 Num a 클래스의 모든 인스턴스들을 위한 타입, 즉 클래스를 위한 인스턴스를 만들려고 합니다.

ClassA 클래스를 정의하고, 모든 Num a 인스턴스들을 위한 인스턴스를 정의해 봤습니다.

class ClassA a where
    method1 :: a -> a
    method1 a1 = a1

instance Num a => ClassA a where
    method1 x = x 

func :: (Num a, ClassA a, Show a) => a 
func = method1 1 

main :: IO ()
main = do
    print $ func 

컴파일 하면 다음과 같은 에러가 납니다.

    • The constraint ‘Num a’
        is no smaller than the instance head ‘ClassA a’
      (Use UndecidableInstances to permit this)
    • In the instance declaration for ‘ClassA a’
5 | instance Num a => ClassA a where

“Num a 제약이 인스턴스 head 보다 작지 않다” 뭐가 작다는 얘기일까요? 뭐가, 작다고 얘기해주면 좋을 텐데, 그저 no smaller라고 나오니 당황스럽습니다.

타입 추론에서 뭔가 작다고 얘기할 때는 값을 생성하기 위한 생성자 수와 관계가 있습니다. 생성자가 많이 감싸고 있으면 크고, 생성자가 적게 감싸고 있으면 작다고 표현합니다. 예를 들면, [Just 1]은 Just와 [] 생성자가 필요합니다. Just 1은 Just 하나만 있으면 됩니다.

2022.3.8 추가 - 생성자의 수, 즉 kind의 size로 한정하기 보다는 GHC가 타입 추론을 좁혀갈 수 있는 정보의 양을 크다/작다로 얘기한다고 알려주셨습니다. Ailrun 님 감사합니다.

예를 들어 보면,

class Monad m => MonadReader r m | m -> r where

instance Monad m => MonadReader r (ReaderT r m) where

인스턴스 헤드는 m을 감싼 ReaderT를 MonadReader로 감싸고 있습니다. 제약constraint에는 Monad m 한 번만 감싸고 있습니다. 이럴 때 제약이 헤드보다 “작다”라고 표현한다고 합니다. 더 많은 생성자로 감싼 걸 왜 크기로 표현했는지는 자료를 찾지 못했습니다.

ClassA는 a를 한 번 감싸고 있고, 제약에 있는 Num도 a를 한 번 감싸고 있습니다. 이러면 안된다는 에러입니다. 왜 안될까요? 문제를 단순화 시켜 아래 코드부터 보겠습니다.

모든forall 타입을 위한 인스턴스

instance ClassA a 

somefunc :: (ClassA a) => a
somefunc = method1

이 함수의 타입으로 추론될 수 있는 타입은 뭘까요? ClassA로 제약을 걸어 두었지만, 인스턴스 선언에 instance ClassA a로 모든a의 인스턴스가 존재하니 a는 어떤 타입이 들어와도 되는 상태입니다. 예를 들어 나중에 a에 Int가 들어오면 ClassA Int 인스턴스를 찾는데, 이 건 Instance ClassA a와 매치될겁니다.

test.hs:8:9: warning: [-Wsimplifiable-class-constraints]
    • The constraint ‘ClassA a’ matches an instance declaration
      instance ClassA a -- Defined at test.hs:5:10
      This makes type inference for inner bindings fragile;
        either use MonoLocalBinds, or simplify it using the instance
    • In the type signature: func :: (ClassA a) => a
8 | func :: (ClassA a) => a 

내부 바인딩을 위한 타입 추론이 깨질fragile 위험이 있다고 합니다. 헤드와 제약이 완전히 같을 때 나오는 에러인 것 같습니다. 보통은 제약에 Monad m => 이라 하면, 나중에 m으로 들어오는 타입에 따라 인스턴스를 고릅니다. m에 IO가 들어오면 instance Monad IO를 선택합니다. 만일 인스턴스가 instance Monad m이 있다면, m에 뭐가 들어오든 이 인스턴스를 선택하게 됩니다. 혹시 다른 인스턴스들이 있다면 모두 무효화 시키기 때문에 위험하단 얘기일까요?

※ 내부 바인딩, 외부 바인딩이 뭘까요? 람다 대수에서 (\x -> ((\y -> y + 1) 1) + 2) 2 이런 abstraction에서 \y를 내부 바인딩이라 부르는 것 같습니다. 여기선 ClassA를 매칭하는 걸 외부 바인딩, a를 매칭하는 걸 내부 바인딩쯤으로 여기는 게 아닐까요? 그래서 내부 a를 위한 여러 인스턴스로 instance Monad IO, instance Monad Maybe… 등이 있더라도 모두 무시 되고, 모드 instance Monad m에 매치되므로 내부 바인딩이 깨질 위험이 있다고 한게 아닐까요? 일단 모든forall 타입에 대한 인스턴스를 이렇게 처리한다고 알고 다음으로 넘어 가겠습니다.

무한 타입 체크

instance (Num a) => ClassA a ------ (1)

이를 피하기 위해, 모든 타입이 아닌 Num a 클래스의 인스턴스로 범위를 좁혀 보겠습니다. 모든 forall a. Num a 는 Num a의 모든 인스턴스를 말합니다. [Int, Intger, Word, Float, Double …]를 위한 ClassA 인스턴스란 말입니다. 나중에 “Num a 컨텍스트속에서 method1을 만나면 이 인스턴스에 있는 method1을 불러라* 입니다. 하지만, UndecidableInstances 확장 없이는 이렇게 정의할 수 없다고 합니다. 왜 컨텍스트와 헤드의 크기가 같으면 안될까요? Paterson Condition 때문에 그렇다는데, 패터슨 조건이 뭔지 나오는 자료는 많은데, 왜 그게 필요한지 알려주는”간단한” 자료를 못 찾았습니다.
Instance termination rules

stackoverflow에서 검색하면 무한 타입 체킹을 피하기 위한 조치라고 나옵니다. 왜 무한 타입 체킹이 일어날 수 있다는 걸까요? 이 조건이 있으면 반드시 무한 루프가 발생한다는 얘기가 아니라, 그럴 수도 있다는 얘기니 일어날 수 있는 상황을 끼워 맞춰 보겠습니다.

instance (ClassA a) => Num a ------ (2)

만일 (1)번 정의가 있는 상태에서 추가로 (2)번 인스턴스 정의가 추가 된다면 (일부러라기보다 라이브러리를 쓰는 사용자가 추가한다거나…)

func :: (ClassA a) => a

나중에 func의 a로 Int가 들어오는 상황이 생기면,

1. instance (Num a) => ClassA a(1)와 매칭되고,
   
2. a가 Num 인스턴스가 있는지 찾을테니,
   
3. instance (ClassA a) => Num a(2)와 매칭됩니다.
   
4. 그럼 다시 (1)과 매칭되고, 다시 (2)와 매칭되고….

이렇게 무한 체킹에 빠질 헛점이 존재합니다. 그럼 제약보다는 헤드에서 조건이 크도록 만들어 보겠습니다.

instance (Num a) => ClassA (Maybe a)
instance (Ord a) => ClassA (Monad m)
instance (ClassA a) => Num (Maybe a)
instance (ClassA a) => Ord (Monad m)
...
-- instance (Num a) => ClassA a 인스턴스나,
-- instance (ClassA a) => Maybe a 란 인스턴스를 만들 수 없습니다.

– 헤드가 반드시 더 생성자로 감싸져 있어야 하니, 타입과 헤드 서로 자리를 바꿔 무한 체킹 조건을 만들 수가 없습니다.

이래서, 제약보다 헤드가 항상 크게 만들어 무한 타입 체킹이 생길 일을 미연에 방지한다는 뜻 아닐까요? 역시나 무한 체킹 절차가 돌아가는 작업 자체를 설명한 자료는 못찾았습니다.

패터슨 조건 Paterson Conditions :

컨텍스트의 각 클래스 제약 ( C t1 ... tn )은
타입 변수는 헤드에서 보다 제약에서 더 등장해서는 안된다.
제약은 헤드보다 더 적은 생성자와 변수를 가지고 있어야 한다.
제약에 타입 함수가 있으면 안된다.

인스턴스 매칭을 시도할 때 두 개 이상의 인스턴스와 매칭될 확률이 있는건 상관없다고 합니다. 중복 매칭이 되면 그 때서야 에러를 뱉습니다. 위와 같은 작업이 필요하고, 사용자가 주의를 기울인다면 UndecidableInstances 확장을 켜고 인스턴스를 만들 수 있습니다.

언제 이런게 필요할까 싶은데, 가장 간단한 예로 같은 동작을 하는 다른 이름의 클래스를 만들 때 쓰인다고 합니다.

https://stackoverflow.com/questions/3213490/how-do-i-write-if-typeclass-a-then-a-is-also-an-instance-of-b-by-this-definit

인스턴스를 찾는 작업Instance Resolution

“헤드 매칭 이후에 제약이 쓰인다.”

코드에서 만난 constraint -> 헤드와 패턴 매칭 -> 컨텍스트와 패턴 매칭

instance (Num a) => ClassA a where ...
func :: (ClassA a) => a

ClassA a => a를 만나 제약 ClassA a와 매칭되는 인스턴스를 찾습니다. 헤드만 매칭하니 Num a => ClassA a를 찾았습니다. 이렇게 찾은 a가 Num a클래스를 따라야 한다고 하니, Num a와 매칭 되는 인스턴스를 찾습니다.

만약 Int가 들어왔다 치면, ClassA Int를 찾을테고, 이건 (Num a) => ClassA a 와 매칭되고, Int는 Num의 인스턴스여야 하는 조건을 만족하니, OK입니다.