forall - 아무거나 (하나)와 모든 것의 차이

Posted on May 4, 2021

오늘 점심 뭘 먹을까?
난 이 것도, 저 것도 모든걸 먹을 수 있는 입맛이야. For All
아무거나 (하나) 먹자

에러 관련 포스트들에서 몇 번 강조했는데 forall은 말 그대로 모든 타입입니다. 어떤 타입으로든 카멜레온처럼 변할 수 있다가 아니라, 어떤 타입도 처리할 수 있어야 한다는 뜻입니다. ( 참고 - 컴파일 에러 읽기 - rigid type variable ) 그런데, 이 걸 명시적으로 써야 하는 경우가 있습니다. 바로 Rank 개념이 필요한 경우입니다.

생각 스트레칭

2022.12.31 추가

foo :: forall a. a -> Bool
foo _ = True
-- 괄호를 써서 유효 범위를 명시적으로 표시하면 foo는 다음과 같습니다.
-- foo :: forall a. (a -> Bool)

bar :: (forall a. a) -> Bool
bar _ = False

forall이 걸리는 범위에 대한 이야기입니다.
“foo는 a -> Bool 구현이 모든 타입에 문제 없이 동작한다”고
“bar는 a 구현이 모든 타입에 문제 없이 동작한다”입니다.

ghci> foo 1
True
ghci> foo "a"
True

foo는 어떤 타입이 들어와도 문제 없이 동작합니다.

ghci> bar 1

<interactive>:41:5: error:
    • No instance for (Num a) arising from the literal ‘1’
      ...
ghci> bar "a"

<interactive>:42:5: error:
    • Couldn't match expected type ‘a’ with actual type ‘String’
      ...
ghci> bar undefined
False

bar는 a -> Int가 아니라, a가 모든 타입에 문제 없이 동작해야 하니, a가 모든 타입에 문제 없는, 즉 모든 타입에 속하는 bottom만 가능한 구현입니다. bottom을 돌려주는 undefined 함수만 받을 수 있습니다.

RankNTypes

RankNTypes 설명은 남현욱님의 설명이 좋습니다. 여기 글은 RankNType 글을 본 후 생각해 볼만한 내용입니다.

위 사이트에서 예를 든 소스를 가져와 약간 변형해 보겠습니다.

2022.12.31 추가
forall 범위
forall a. a -> a -> a 는 모든 a가 영향을 받고,
forall a. a -> forall a. a -> a는 앞에 하나와 뒤에 두 개가 따로 영향을 받습니다.

혼동을 줄이려면
forall a. a -> forall b. b -> b 이렇게 쓰면 됩니다.

{-# LANGUAGE RankNTypes #-}

-- foo :: (forall a. [a] -> Int) -> [b] -> [c] -> Bool
foo :: (forall a. [a] -> Int) -> forall a. [a] -> forall a. [a] -> Bool
foo f x y = f x == f y

main = do
    print $ foo length [1,2,3,4] ['a','b','c']

foo 함수가 실행될 때, 각 a들은 모두 다른 타입이 될 수 있습니다. forall을 특정 범위에 한정되게 붙이면 a 글자를 b나 c등으로 바꿔도 상관 없습니다. 람다 대수의 alpha equivalance와 같은 의미입니다. 그런데 아래와 같이 영향을 미치는 범위를 명확히 표시하기 위해 괄호로 감싸주면

foo :: (forall a. [a] -> Int) -> (forall a. [a]) -> (forall a. [a]) -> Bool

에러가 납니다.

    • No instance for (Num a) arising from the literal ‘1’ ------------------(1)
      Possible fix:
        add (Num a) to the context of
          a type expected by the context:
            forall a. [a]
    • In the expression: 1
7 |     print $ foo length [1,2,3,4] ['a','b','c']
  |                         ^

    • Couldn't match expected type ‘a’ with actual type ‘Char’ --------------------(2)
      ‘a’ is a rigid type variable bound by
        a type expected by the context:
          forall a. [a]
    • In the expression: 'a'
7 |     print $ foo length [1,2,3,4] ['a','b','c']
  |                                   ^^^

왜 그럴까요? 일단, 하나는 No instance, 하나는 Couldn't match 입니다.

No instance인 이유는, 리터럴 1이 Int나 Integer 같이 딱 하나의 타입으로 추론되지 않고 Num 클래스의 인스턴스란 것 까지만 추론되었기 때문입니다.
Couldn't match는 딱 하나의 타입 Char로 추론됐는데 서명에는 모든 타입으로 지정rigid되어 있어, 서로 일치하지 않는다는 에러입니다. 참고 - rigid type variable

여기서부턴 추측입니다. 괄호로 감싸져 있을 땐, 현재 함수 서명에서 영향이 있는 게 아니라, 나중에 들어오는 값이 진짜 forall a. [a] 가 들어와야 합니다. 모든 타입 중에 어느 한 타입이 아니라, 진짜로 모든 타입을 받을 수 있는 무언가가 들어와야 합니다.

No instance ...: 클래스는 추론됐는데, 해당 타입을 키로 하는 인스턴스는 없다.

서명의 다른 부분은 볼 필요 없습니다. (forall a.[a])만 보면 됩니다. 생각 스트레칭에서 봤듯이 모든 타입을 받아 리스트[]로 만들 수 있는 구현만 가능합니다.
서명과 구현의 모순 여부 체크를 지나, 나중에 코드 조립 중 들어온 타입을 보니 1이 들어왔습니다.
1이란 리터럴로 추론한 타입은 Num 클래스의 인스턴스입니다.
모든 타입 a가 Num의 인스턴스여야 한다는 말입니다. a는 모든 타입인데, Num 인스턴스 중 모든 타입용 인스턴스는 당연히 없습니다.

Couldn't match ...: 특정 타입까지 추론됐는데, 다른 조건에서 추론된 타입과 일치하지 않는다.

서명의 다른 부분은 볼 필요 없습니다. (forall a.[a])만 보면 됩니다. 이 것도 역시 모든 타입을 받아 리스트[]로 만들 수 있는 구현만 가능합니다.
서명과 구현의 모순 여부 체크를 지나 , 나중에 코드 조립 중 들어온 타입을 보니 'a'가 들어왔습니다.
'a'를 보고 추론할 수 있는 타입은 Char 하나입니다. 구체 타입 Char로 추론되었습니다.
지금 정해지지 않은 타입, 모든 a는 모든 타입이지 하나의 구체 타입이 아닙니다. 모든 타입과 Char는 매치되지 않습니다.

2022.2.25 추가

함수 서명에 아무런 제약 없이 a만 써주면, GHC는 a를 무엇으로 결정할지 모릅니다. 반드시, 타입 정보를 줘야 합니다. 함수 안에서 폴리모픽 a를 다룰 때, 특정 클래스의 인스턴스만 다룰지, 아니면 어떤 타입이든 들어와도 처리할 수 있는지 함수 서명에서 알려줘야, 코드 조립할 때, 함수 내용을 보지않고 서명으로만 체크할 수 있게 됩니다. 그래서, 컴파일할 때는 함수 몸체(구현)에 있는 타입의 쓰임과 함수 서명이 일치하는지 체크하고, 나중에 다른 코드와 만날 때는 서명만 가지고 일치하는 타입이 들어오는지 체크하리라 예상합니다.
※ 2022.10.17 추가 - 이게 non-dependent type checking이 동작하는 방식이라 합니다. @Ailrun님 감사합니다.
forall a. a로 함수가 아닌 단독 a만을 위한 foall a.붙여 주면, a가 아무 타입이 될 수 있다는 말이 아니라, 아무 타입을 받아도 문제가 없는 구현, 즉 모든 타입에 대응하는 구현이라는 타입 정보를 준 것으로 받아들입니다. 아무 타입이나 들어와도 문제 없으려면, 구현은 모든 타입 대응할 수 있어야 합니다. forall a.a -> Bool은 a의 구현이 아니라, a -> Bool의 구현이 모든 타입에 대응할 수 있다는 말입니다. a를 아예 보지 않는 구현을 만들면 되겠지요. 보통 폴리모픽하게 쓸 때 forall a.를 명시적으로 써주지 않지만, GHC가 안보이게 붙인다고 보면 됩니다.

2022.9.17 추가

{-# LANGUAGE RankNTypes #-}

func1 :: forall a.a -> Int
func1 _ = 1

func2 :: (forall a.a) -> Int
func2 _ = 2

func3 :: (forall a . (Num a) => a) -> Int
func3 _ = 3

*Main> func1 1
1
*Main> func2 1
<interactive>:91:7: error:
    • No instance for (Num a) arising from the literal ‘1’...
*Main> func2 undefined
2
*Main> func3 1
3

세상에 타입은 Bool, Int만 있다고 가정하면

forall a. a -> Int ----(가)
-- forall a.(a -> Int)와 같습니다.

의 구현은 Bool -> Int로 봐도, Int -> Int로 봐도 문제가 없는, 즉 둘 모두에 대응할 수 있는 구현이어야 합니다. 구현은 Bool에 의존하지도, Int에 의존하지도 않기 때문에 1을 넣어 줄 수 있습니다.

(forall a. a) -> Int ----(나)

괄호안만 떼어내서 보면

forall a. a

의 구현은 Bool로 봐도, Int로 봐도 문제가 없는 구현이어야 합니다. 그래서 undefined만 가능합니다. 그래서 func2에 인자로 줄 수 있는 값은 undefined뿐이 없습니다.

(forall a. a)는 아무 타입 중 하나가 아니라 모든 타입입니다. 나중에 모든 타입이 될 수 있는 값인 undefined만 들어 올 수 있습니다. forall a . (Num a) => 는 Num클래스의 인스턴스가 아니라, 지정한대로 Num a클래스까지만 추론할 수 있는 값이 들어와야 합니다. 리터럴 1은 Int나 Integer 같은 구체 타입이 아니라 (Num a => a) 타입의 값입니다. 정확히 이 값만 OK로 받아들입니다.

다양한 단계의 타입 정의가 가질 수 있는 값
Int 타입 : { undefined, 0, 1, 2,…}
() 타입: { undefined, () }
Maybe Int 타입 : { undefined, Nothing, Just 0, Just 1, …}
forall a. a 타입 : { undefined }
forall a. (Num a) => a 타입 : { 리터럴 0, 리터럴 1, 리터럴 2, … }

※ 괄호를 쓰지 않았을 때 forall의 스코프 GHC 매뉴얼을 보면 func1은 함수 선언 전체가, 즉 a -> Int가 forall a의 유효 스코프라고 합니다.

제가 본 자료들에 서명, 조립 단계 이렇게 설명한 곳은 없습니다. forall a를 Bottom값으로 설명한 자료, 또는 타입을 매개 변수로 받는 함수 등으로 설명한 자료들을 찾았지만, 서명에 있는 괄호 (...)에 대해 명쾌하게 설명한 곳은 아직 찾지 못했습니다.

GHC가 폴리모픽 타입을 만나면 구체 타입으로 추론한다는 것에서 혼동이 올 수 있습니다. forall은 타입 추론을 해서 Bool을 주면 Bool에 맞는 동작을 하고, Int를 주면 Int에 맞는 동작을 하겠다는 게 아닙니다. Bool을 주든, Int를 주든 같은 동작으로 문제 없이 처리 하겠다는 겁니다.

2022.10.13 추가

좋은 설명이 보여 옮겨 놓습니다. 나중에 covarint와 contravariant 글로 옮길 예정입니다.
Unification of higher rank types on contravariant positions
위 링크의 chi란 분의 답변에서 발췌한 소스입니다.

k :: ((forall b. [b] -> [b]) -> Int) -> Int
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
               ... -> Int
k f = f (\xs -> xs++xs)

k1 :: (forall a. a -> a) -> Int
k1 x = x 10 + length (x "aaa")

k함수는 ... -> Int 타입의 함수를 받으면 Int값을 돌려 줍니다. 함수를 받았는데, Int를 돌려주려면, 이미 안에 ...에 해당하는 걸 가지고 있어야 합니다.

예를 들어, (Int -> Bool) -> Bool 타입의 함수는 Int -> Bool함수를 받아서, 안에서 Int를 넣어 Bool을 뽑아 낼 거라 예상할 수 있습니다.

마찬가지로 위는 (forall b. [b] -> [b]) -> Int 함수를 받아, 안에서 forall b. [b] -> [b] 함수를 넣어 줄 거라 예상할 수 있습니다. 이 때 넣어 주는 함수를 타입에 맞춰 만들어 본 예시가 (\xs -> xs ++ xs) 입니다. 이렇게 forall b 즉 모든 타입의 b가 들어와도 문제가 없는, (\xs -> xs ++ xs) 같은 함수를 가지고 있다는 뜻입니다.

실제로 k에 k1을 넣어 풀어 보면

k k1 =
k1 (\xs -> xs++xs) =
(\xs -> xs++xs) 10 + length ((\xs -> xs++xs) "aaa") =
(10++10) + length ("aaa"++"aaa")

문제가 생기는 ill 타입이 나옵니다.

2022.10.14 추가

func1 :: forall a. a -> Int
func1 _ = 1

ghci> func1 "a"
1
ghci> func1 1
1
ghci> func1 True
1
g

func2 :: (forall a. a -> Int) -> Int
func2 _ = 2

hci> func2 (\n -> 2)
2
ghci> func2 (\n -> n)
<interactive>:6:14: error:
    • Couldn't match expected type ‘Int’ with actual type ‘a’
      ‘a’ is a rigid type variable bound by

func1은 아무(어떤) 타입이 들어와도 Int를 내뱉을 수 있습니다. => 모든 타입에 대응해서 Int를 뱉을 수 있습니다. func2는 반드시 “아무(어떤) 타입이 들어와도 Int를 내뱉을 수 있는 함수”만 들어와야 합니다. \n -> 2는 어떤 타입이 들어와도 2를 내뱉을 수 있습니다. \n -> n는 True를 주면 True를 내뱉는 함수라 안됩니다.

func1은 forall a. a 자리에 "a", 1, True 등 아무 타입이나 들어오는데 func2는 forall a. a -> Int 자리에 반드시 forall a. a -> Int만 들어와야 합니다. Int -> Int같은 함수는 안됩니다.

아마도 많은 입문자들에게 혼란을 주는 부분이 여기지 않을까요?

func1은 모든 타입을 받을 수 있는 함수니 이런 저런 타입을 넣어 준 것이고, func2는 “모든 타입을 받을 수 있는 함수”만 받을 수 있습니다.

이렇게 타입으로만 설명하면 말장난처럼 들릴 수도 있습니다.

동작을 따라가며 예상하면 조금 나을 수 있습니다.
넣어 준 함수의 인자는 아직 정해지지 않았습니다. func2 안에서 어떤 인자를 넣어 줄지(혹은 아무 것도 안 넣어 줄지) 모릅니다. 예를 들어, 나중에 func2가 True를 넣어 줄 수도 있는데, 여기다 Int -> Int 함수를 넣어 놓으면 문제가 생길거라 예상할 수 있습니다.

다음 함수를 해석해 보면,

func :: forall a. (a -> Bool) -> Int
func f = if f 1 then 1 else 0

• No instance for (Num a) arising from the literal ‘1’
  Possible fix:
    add (Num a) to the context of
      the type signature for:
        func :: forall a. (a -> Bool) -> Int
• In the first argument of ‘f’, namely ‘1’
  In the expression: f 1
  In the expression: if f 1 then 1 else 0

모든 a를 다룰 수 있는 함수가 들어 왔으니 1을 넘겨줘도 되야 할 것 같은데, 그렇게 해석되지 않습니다.

func :: forall a. (a -> Bool) -> Int ------(가)
func f = if f 1 then 1 else 0
            ^^^ -- f가 1을 받고 있다!

세상에 Int타입과 Bool 타입만 있다 가정하면, func는 (Int -> Bool) -> Int도 (Bool -> Bool) -> Int도 가능한 구현이어야 합니다. 하지만, 구현에서 1을 넣어주고 있기 때문에 (Bool -> Bool)인 경우에는 문제가 됩니다.

func :: (forall a. a -> Bool) -> Int ------(나)
func f = if f 1 then 1 else 0

func는 (Int -> Bool)도 (Bool -> Bool)도 가능한 함수를 받아 Int를 돌려줍니다. Int도, Bool도 받을 수 있는 함수를 받았기 때문에, 여기에 1을 넣는 건 문제가 되지 않습니다.

이론적인 것보다 실제 동작으로 얘기하면, (가)는 외부에서 Bool -> Bool 타입으로 결정된 함수가 들어오면 문제가 생기고, (나)는 외부에서는 모든 것이 가능한 함수가 들어오고, 이 함수가 Int -> Bool일지, Bool -> Bool일지는 즉, 구체 타입은 내부에서 결정됩니다.

그래서 “내부에서 함수가 결정되도록 하려면 RankNType을 쓰면 된다”고 얘기합니다. @재원

※ 위에 날짜별로 추가된 글은, 하스켈 학교에서 여러분들과 대화하며 올렸던 글들을 그대로 가져온 것입니다.

2023.9.28 forall a.a => [a]라 하면, “a는 무엇인지 보지 않겠어”, 혹은 “구조 안에 들어 있는 건 뭔지 관심없고, 난 구조에 관한 내용만 가지고 있어” 라고 간단히 읽을 수 있습니다. a가 무언가로 특정되면 안된다는 걸 컴파일러에게 알려 주는 가이드입니다.

Github 계정이 없는 분은 메일로 보내주세요. lionhairdino at gmail.com