값, 타입, 그리고 리스트

값, 타입, 그리고 리스트

하스켈은 순수 함수형 언어라서, 모든 계산이 곧 표현식의 평가로 이루어져요. 그리고 그 표현식은 저마다 타입을 갖고, 정적 타입 시스템이 값과 타입의 관계를 지켜주죠. 여기에서는 값과 타입이 어떻게 짝을 이루는지, 다형성 타입이 뭔지, 그리고 함수형 언어에서 가장 흔한 자료구조인 리스트가 실제로 어떤 모양인지 함께 살펴볼게요.

출처: https://www.haskell.org/tutorial/goodies.html

본문

표현식과 타입

하스켈에서 값은 표현식(expression)이라는 구문적 용어를 평가해서 얻어요. 예를 들어 정수 5나 문자 'a' 같은 원자적 값, 그리고 함수 \x -> x+1 같은 것까지 모두 표현식이에요. 모든 값에는 타입이 붙고, 타입을 값의 집합쯤으로 이해하면 돼요.

몇 가지 타입 표현식만 보면 금방 감이 잡혀요. Integer는 무한 정밀도 정수 타입, Char는 문자 타입, Integer->Integer는 정수를 정수로 보내는 함수 타입이에요. 구조적인 타입으로는 정수들의 동질 리스트인 [Integer], 문자와 정수의 쌍인 (Char,Integer) 같은 것들이 있어요.

값과 타입의 짝을 :: 로 적어요. 이는 "~는 ~ 타입을 갖는다"로 읽으면 돼요.

5            :: Integer
'a'          :: Char
inc          :: Integer -> Integer
[1,2,3]      :: [Integer]
('b',4)      :: (Char,Integer)

함수는 보통 일련의 방정식으로 정의하고, 타입 시그니처 선언으로 명시적인 타입을 적을 수 있어요. 예를 들어 1을 더하는 함수는 이렇게 정의해요.

inc n   = n+1

정적 타입 시스템

하스켈은 정적 타입 시스템을 갖고 있어서, 컴파일 시점에 타입 안전성(type safety)을 보장해요. 두 문자를 더하는 'a'+'b' 같은 표현식은 타입이 맞지 않아 바로 거부돼요. 물론 타입 시스템이 모든 오류를 잡아주는 건 아니에요. 1/0 같은 건 타입이 있지만 실행 시점에 오류가 나거든요.

그래도 정적 타입의 장점은 분명해요. 대부분의 타입 오류를 컴파일 타임에 발견하고, 타입 시그니처가 훌륭한 문서 역할을 하며, 컴파일러가 더 효율적인 코드를 만들 수도 있어요. 흥미롭게도 하스켈의 타입 시스템은 충분히 강력해서 타입 시그니처를 아예 안 써도 추론(inference)으로 올바른 타입을 찾아줘요. 그래도 inc에 붙인 것 같은 시그니처를 잘 배치해 두는 건 좋은 습관이에요 — 문서화 효과도 있고 오류를 일찍 드러내 주니까요.

다형성 타입

하스켈에는 모든 타입에 걸쳐 보편 정량화된 다형성 타입이 있어요. 예를 들어 [a]는 "어떤 타입 a에 대해서도 그 타입의 리스트"라는 한 가족(family)의 타입을 뜻해요. [1,2,3], ['a','b','c'], 심지어 리스트의 리스트까지 모두 이 가족에 속해요. 다만 [2,'b']처럼 타입이 안 맞는 원소를 섞은 건 유효하지 않아요.

a 같은 식별자는 타입 변수라고 하고, 구체 타입인 Int와 구분하려고 소문자로 적어요.

리스트

함수형 언어에서 리스트는 가장 흔한 자료구조예요. [1,2,3]은 사실 1:(2:(3:[]))의 줄임 표현이에요. []는 빈 리스트, :는 첫 인자를 두 번째 인자(리스트)의 앞에 붙이는 중위 연산자예요. :와 []는 각각 Lisp의 cons와 nil에 해당해요. :는 오른쪽 결합이라 1:2:3:[]로도 쓸 수 있어요.

리스트를 다루는 함수를 직접 만들어 볼까요. 리스트의 원소 개수를 세는 length를 정의해 봐요.

length                    :: [a] -> Integer
length []                 =  0
length (x:xs)             =  1 + length xs

이 정의는 거의 설명 없이도 읽혀요. "빈 리스트의 길이는 0이고, 첫 원소가 x이고 나머지가 xs인 리스트의 길이는 1 더하기 xs의 길이다." 여기서 등장하는 게 바로 패턴 매칭이에요. 방정식의 왼쪽 변에 []나 x:xs 같은 패턴이 오고, 함수 호출에서 이 패턴이 실제 인자와 매치돼요. []는 빈 리스트에만, x:xs는 최소 한 원소 이상인 모든 리스트에 매치되면서 x에는 첫 원소, xs에는 나머지 리스트가 묶여요.

length는 다형성 함수이기도 해요. 어떤 타입의 리스트에도 적용할 수 있어요.

length [1,2,3]           => 3
length ['a','b','c']     => 3
length [[1],[2],[3]]     => 3

유용한 리스트 함수 두 개만 더 볼게요. head는 첫 원소를, tail은 첫 원소를 뺀 나머지를 돌려줘요.

head                     :: [a] -> a
head (x:xs)              =  x
tail                     :: [a] -> [a]
tail (x:xs)              =  xs

length와 달리 이 둘은 모든 인자에 대해 정의되진 않아요. 빈 리스트에 적용하면 런타임 오류가 나요.

주 타입과 타입 추론

[a]는 [Char]보다 더 일반적인 타입이에요. 이렇게 일반성의 순서가 있고, 하스켈 타입 시스템은 두 가지 중요한 성질을 가져요. 첫째, 모든 well-typed 표현식은 유일한 **주 타입(principal type)**을 갖고, 둘째, 그 주 타입은 자동으로 추론돼요. 예를 들어 head의 주 타입은 [a]->a예요. [b]->a나 a->a는 지나치게 일반적이고, [Integer]->Integer는 지나치게 구체적이죠. 유일한 주 타입이 존재한다는 건 Hindley-Milner 타입 시스템의 특징이에요. 하스켈, ML, Miranda 등이 모두 이 시스템을 바탕으로 해요.

사용자 정의 타입

data 선언으로 자신만의 타입을 정의할 수 있어요. 진리값 타입 Bool은 가장 간단한 예시예요.

data Bool = False | True

Bool은 값으로 True와 False 두 개만 가져요. 이런 data 선언에서 타입 쪽 이름 Bool은 (nullary) 타입 생성자, True/False는 (nullary) 데이터 생성자라고 불러요. 데이터 생성자가 유한 개인 이런 타입을 열거 타입(enumerated type)이라고 해요.

이번엔 타입 생성자가 하나뿐인 예를 볼게요.

data Point a = Pt a a

생성자가 하나뿐이라 Point 같은 타입은 튜플 타입이라 부르고, 사실상 다른 타입들의 데카르트 곱이에요. 반대로 Bool이나 Color처럼 생성자가 여럿인 타입은 (서로소) 합(sum) 타입이라고 불러요. 그리고 Point는 중요한 의미로 다형성 타입이에요 — 어떤 좌표 타입 t에 대해서도 그 좌표를 쓰는 점의 타입을 정의하니까요. 데이터 생성자 Pt의 타입은 a -> a -> Point a라서 다음과 같은 typing이 모두 유효해요.

Pt 2.0 3.0          :: Point Float
Pt 'a' 'b'          :: Point Char
Pt True False       :: Point Bool

재귀 타입

타입은 재귀적일 수도 있어요. 이진 트리 타입을 정의해 볼게요.

data Tree a = Leaf a | Branch (Tree a) (Tree a)

Leaf는 타입 a의 값을 담는 잎 노드, Branch는 재귀적으로 두 하위 트리를 담는 내부 노드예요. Tree는 타입 생성자, Branch와 Leaf는 데이터 생성자라는 걸 기억해 두면 선언이 잘 읽혀요. 이 타입을 쓰는 함수도 정의해 봐요. 잎들의 원소를 왼쪽에서 오른쪽으로 나열하는 fringe를 보면,

fringe                    :: Tree a -> [a]
fringe (Leaf x)           =  [x]
fringe (Branch left right) =  fringe left ++ fringe right

fringe는 Tree a -> [a] 타입의 다형성 함수예요. ++는 두 리스트를 이어붙이는 중위 연산자고요.

타입 동의어

자주 쓰는 타입에 이름을 붙여 주는 **타입 동의어(type synonym)**도 있어요. type 선언으로 만들어요.

type String      = [Char]
type Person      = (Name,Address)
type Name        = String
data Address     = None | Addr String

타입 동의어는 새 타입을 만드는 게 아니라 기존 타입에 새 이름을 붙여 주는 거예요. 다형성 타입에도 이름을 붙일 수 있어요.

type AssocList a b = [(a,b)]

내장 타입도 특별하지 않아요

리스트, 튜플, 정수, 문자 같은 "내장" 타입은 특별한 문법이 있긴 해도, 사용자 정의 타입보다 본질적으로 특별하진 않아요. 가령 Char는 사실 거대한 열거 타입으로 볼 수 있어요.

data Char = 'a' | 'b' | 'c' | ...   -- This is not valid
          | 'A' | 'B' | 'C' | ...   -- Haskell code!
          | '1' | '2' | '3' | ...

이건 유효한 문법은 아니지만, 특별 문법 너머를 보는 데 도움이 돼요. 리스트도 마찬가지로 재귀 구조로 이해할 수 있어요.

data [a] = [] | a : [a]    -- more pseudo-code

[]가 빈 리스트, :가 중위 리스트 생성자라는 게 이제 분명해져요. [1,2,3]은 결국 1:2:3:[]과 동등하고요.

튜플과 리스트를 잘 구분해야 해요. 리스트는 동질(homogeneous) 원소를 임의 길이로, 그리고 재귀적으로 담는 반면, 튜플은 이질(heterogeneous) 원소를 고정 길이로 담아요. 표기 규칙도 정리하면, 튜플 (e1,e2,...,en)의 타입은 (t1,t2,...,tn)이고, 리스트 [e1,e2,...,en]은 모든 원소가 같은 타입 t여야 하며 타입은 [t]가 돼요.

리스트 컴프리헨션과 산수 시퀀스

리스트를 간편하게 만드는 문법이 더 있는데, 그중 하나가 리스트 컴프리헨션이에요.

[ f x | x <- xs ]

이건 "xs에서 뽑은 각 x에 대해 f x를 모은 리스트"로 읽으면 돼요. 집합 표기와 닮았는데 우연이 아니에요. 생성자(generator)는 여러 개 둘 수 있어요.

[ (x,y) | x <- xs, y <- ys ]

이건 두 리스트의 데카르트 곱을 만들어요. 조건을 거는 guard라는 부울 표현식도 쓸 수 있어요. 이 기능으로 모든 사람이 좋아하는 정렬 알고리즘을 간결하게 쓸 수 있어요.

quicksort []          =  []
quicksort (x:xs)      =  quicksort [y | y <- xs, y<x ]
                        ++ [x]
                        ++ quicksort [y | y <- xs, y>=x]

**산수 시퀀스(arithmetic sequence)**라는 특별 문법도 있어요. 예시가 가장 설명이 잘 돼요.

[1..10]    => [1,2,3,4,5,6,7,8,9,10]
[1,3..10]  => [1,3,5,7,9]
[1,3..]    => [1,3,5,7,9, ... (infinite sequence)

문자열

문자열 리터럴 "hello"는 사실 문자 리스트 ['h','e','l','l','o']의 줄임 표현이에요. 타입도 String인데, 이는 앞서 본 타입 동의어 type String = [Char] 덕분이에요. 덕분에 다형성 리스트 함수를 문자열에도 그대로 쓸 수 있어요.

"hello" ++ " world" => "hello world"

더 알아보기