하스켈 max의 항등원

neutral.md

아래 글은 책 Practical Haskell 을 읽은 내용을 정리한 것이다.

foldr

먼저 foldr을 사용한 예를 보자.

GHCi> foldr (+) 0 [1,2,3]
6

foldr의 첫번째 인자로는 '인자의 개수가 두개인 어떤 함수'를 넣는다. 여기에서는 함수 +를 사용했다.

두번째 인자로는 초기값을 넣는다.

세번째 인자로는 fold를 수행할 리스트를 넣는다.

함수 foldr의 타입은 아래와 같다.

foldr :: (a -> b -> b) -> b -> [a] -> b

• (a -> b -> b) : 인자가 두개인 함수
• b : 초기값
• [a] : fold를 수행할 대상 리스트
• b : 최종 결과값

실제 소스코드와는 다를 수 있지만 대충 구현한다면 아래와 같다.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f initial []     = initial
foldr f initial (x:xs) = f x (foldr f initial xs)

항등원

더하기나 빼기 같이 인자가 두개인 함수를 다룰 때 숫자 0은 결과에 영향을 미치지 않는다. 1에 0을 더해도 1이고 1에 0을 더해도 그대로 1이다. 이러한 값을 항등원 identity element 라고 한다.

함수 foldr의 두번째 인자인 초기값에는 보통 항등원을 넣는다. 위 코드에서는 함수 +의 항등원인 0을 초기값으로 넣었다.

max

함수 max는 두 수 중에 큰 것을 알려준다.

max :: Ord a => a -> a -> a

GHCi> max 1 2
2

그런데 함수 max의 항등원은 무엇일까? 어떤 값과 크기 비교를 했을 때 결과에 영향을 미치지 않는 값이란 무엇일까? 바로 음의 무한대 negative infinity 라고 한다.

This means you have to find a value z such that max(z,x) = max(x,z) = x any value x. You can check that the value that satisfies that property is negative infinity.

음의 무한대라는게 도대체 뭘까? 디스코드 하스켈 학교의 임기정님께서 아래와 같이 말해주셨다.

어떤 숫자보다도 작은 객체라고 생각하시면 됩니다

아래와 같이 max로 foldr를 할 때 초기값에는 과연 어떤 값을 넣어야 할까?

GHCi> foldr max ? [1,2,3]

하스켈에 음의 무한대를 나타내는 값이 있나? 없으면 만들면 된다. 하스켈 만세! 아래와 같이 InfNumber 라는 타입을 만들자.

data InfNumber a = MinusInfinity
                 | Number a
                 | PlusInfinity
                 deriving Show

이렇게 만든 타입을 활용한 infMax라는 함수를 만들자.

infMax :: Ord a => InfNumber a -> InfNumber a -> InfNumber a
infMax MinusInfinity x       = x
infMax x MinusInfinity       = x
infMax PlusInfinity _        = PlusInfinity
infMax _ PlusInfinity        = PlusInfinity
infMax (Number a) (Number b) = Number (max a b)

이제 음의 무한대를 이용한 fold를 할 수 있다!

GHCi> foldr infMax MinusInfinity (map Number [1,2,3])
Number 3

대문 링크