계정: 로그인
AA 📝
4. Case 표현식과 패턴 매칭

A Gentle Introduction to Haskell, Version 98
이전 다음 위로


앞에서 우리는 몇가지 함수—예를 들어 lengthfringe 등—정의를 통해 패턴 매칭의 예를 보았습니다. 이 절에서는 패턴 매칭의 과정을 훨씬 자세하게 다뤄보겠습니다. (§3.17) (Haskell에서의 패턴 매칭은 Prolog 같은 논리형 프로그래밍 언어에서 말하는 패턴 매칭과는 다릅니다: Haskell에서는 ‘1-way’ 매칭인데 비해, Prolog에서는 unification을 통한 ‘2-way’ 매칭을 허용하며 평가 기전에 암묵적인 backtracking이 들어있습니다.)

패턴은 ‘first-class’가 아닙니다: 일정한 종류의 패턴만이 존재합니다. 우리는 이미 몇가지 자료 생성자 패턴의 예를 보았습니다: 앞서 정의했던 lengthfringe 모두 이런 패턴을 사용했으며, length는 내장 자료형(리스트)에 대한 생성자였고 fringe는 사용자 정의 타입(Tree)에 대한 것이었습니다. 사실, 사용자 정의이든 아니든 상관 없이 어떤 타입의 생성자를 사용해서도 매칭을 할 수 있습니다. 여기에는 튜플, 문자열, 수치, 문자 등등이 포함됩니다. 예를 들어, ‘상수’의 튜플에 매치시키는 함수 contrived는 다음과 같습니다:

   1 contrived :: ([a], Char, (Int, Float), String, Bool) -> Bool
   2 contrived    ([],  'b',  (1,   2.0),   "hi",   True)  = False

이 예로부터 패턴의 중첩이 (임의의 깊이까지) 허용된다는 사실도 알 수 있습니다.

기술적인 측면에서 말하자면, (Haskell Report에서 변수라고 부르는) 정규 매개변수(formal parameters)도 패턴입니다. — 단지 이들은 켤코 매칭에 실패하지 않을 뿐입니다. 성공적인 매칭의 ‘부작용’으로서, 정규 매개변수는 그것이 매치되려는 값에 bound됩니다. 이런 이유로, 하나의 등식에 들어있는 패턴들은 동일한 정규 매개변수를 두 번 이상 가질 수 없습니다. (linearity라 불리는 특성입니다. §3.17, §3.3, §4.4.3).

정규 매개변수처럼 결코 매칭에 실패하지 않는 패턴들은 irrefutable하다고 말합니다. 매칭에 실패할 수도 있는 패턴들은 refutable하다고 하죠. contrived의 예에서 사용한 패턴들은 refutable합니다. Irrefutable 패턴으로 세 가지가 더 있는데, 이 중 두 가지는 지금 소개하겠습니다. (나머지 하나는 4.4절까지 일단 보류합니다.)

As-patterns

때로는 패턴에 이름을 붙여 등식의 우변에서 사용하면 편할 경우가 있습니다. 예를 들어, 리스트의 첫번째 원소를 하나 복제해서 추가하는 함수는 다음과 같이 작성할 수 있습니다:

   1 f (x:xs)    =  x:x:xs

(‘:’는 우측 우선 결합을 한다는 사실을 상기하십시오.) 이 등식에서 x:xs가 좌변에 패턴으로서, 우변에 표현식으로서 모두 등장한다는 점에 주목하시기 바랍니다. 가독성을 높이기 위해 다음과 같이 as-패턴을 사용하여 x:xs를 한 번만 쓰고싶어질지도 모릅니다 (이렇게 하면 원론적으로 잘 구현된 구현물의 경우 x:xs의 매치되는 값을 재사용하는 대신 x:xs를 완전히 재구성할 것이라는 또다른 장점도 있습니다):

   1 f s@(x:xs)    =  x:s

기술적 측면에서 말하자면, as-패턴은 (비록 그 서브패턴—이 경우 x:xs—은 물론 실패할지도 모르지만) 항상 성공적으로 매치됩니다.

Wild-cards

또다른 흔한 상황으로서, 전혀 관심을 가질 필요 없는 값에 매칭시키는 경우가 있습니다. 예를 들어, 2.1절에서 정의한 함수 headtail다음과 같이 다시 쓸 수 있습니다:

   1 head (x:_)     =  x
   2 tail (_:xs)    =  xs

여기서 우리는 입력 중 일부분의 값이 무엇이든 전혀 상관하지 않겠다는 점을 ‘피력’한 것입니다. 각각의 와일드 카드는 서로 무관하게 아무것에나 매칭됩니다만, 정규 매개변수와는 달리 이들을 어느것에도 bound되지 않습니다: 이런 이유로 이들은 하나의 등식 안에 여러번 등장할 수 있습니다.

4.1 패턴 매칭의 의미론

지금까지 우리는 어떻게 각각의 패턴들이 매치되며, 어째서 일부는 refutable하고 일부는 irrefutable한가 등등의 문제들을 논의했습니다. 그럼 무엇이 전체 과정을 움직일까요? 매칭은 어떤 순서로 시도될까요? 아무것도 매칭에 성공하지 못한다면? 이번 절은 이런 문제들을 다뤄보겠습니다.

패턴 매칭은 성공할 수도 있고 실패할 수도 있으며 혹은 분지(diverge)될 수도 있습니다. 매칭에 성공하면 패턴 속의 정규 매개변수들이 bind됩니다. 패턴이 필요로하는 값이 오류(⊥)를 포함하고 있을 때 분지가 일어납니다. 매칭 과정 자체는 ‘탑-다운이자 좌에서 우로’ 일어납니다. 하나의 등식 중 어디에서라도 패턴 매칭에 실패하면 전체 등식이 실패하는 것이며, 다음번 등식을 시도하게 됩니다. 만일 모든 등식들이 실패하면, 함수 적용의 값은 ⊥이 되고 런타임 오류를 내게됩니다.

예를 들어, 만일 [1,2][0,bot]에 매치되면 10에 매치되지 않으므로 매칭에 실패하게됩니다. (이전에 정의했던 bot은 ⊥에 bound된 변수라는 사실을 상기하시기 바랍니다.) 그러나, 만일 [1,2][bot,0]에 매치되면 1bot에 매칭한 결과는 분지됩니다. (즉, ⊥)

이런 규칙들의 또다른 twist는, 최상위수준(top-level) 패턴도 수치의 부호의 추상화 버전을 만드는 아래 함수 정의처럼 불리언 guard를 가질 수 있다는 점입니다:

   1 sign x  | x >  0    =   1
   2         | x == 0    =   0
   3         | x <  0    =  -1

같은 패턴에 대해서 여러번 guard를 줄 수 있습니다: 패턴에서처럼 이들은 탑다운으로 평가되고, 처음으로 True로 평가된 것이 성공적으로 매칭됩니다.

4.2 예제

매턴 매칭 규칙은 함수의 의미에 중대한 영향을 미칩니다. 예를 들어, 아래와 같은 take의 정의를 살펴봅시다:

   1 take  0  _         =  []
   2 take  _  []        =  []
   3 take  n  (x:xs)    =  x : take (n-1) xs

아래는 약간 다른 버전입니다. (처음 두 개의 등식이 뒤바뀌어 있습니다):

   1 take1  _  []        =  []
   2 take1  0  _         =  []
   3 take1  n  (x:xs)    =  x : take1 (n-1) xs

이제 아래 사항들에 주목하시기 바랍니다:

take는 두번째 인수에 대해서 ‘more defined’되어있고, 반면에 take1은 첫번째 인수에 대해서 좀 더 잘 정의되어 있습니다. 이런 경우 어떤 정의가 더 낫다고 말하기는 어렵습니다. 다만 경우에 따라서는 함수 적용의 결과에 차이가 날 수 있다는 점만 기억하시기 바랍니다. (Standard Prelude에는 take와 같은 정의가 들어있습니다.)

4.3 경우 표현식 (Case Expressions)

패턴 매칭은 값의 구조적 특성에 기반을 둔 ‘신속 제어’ 방법을 제공합니다. 많은 경우, 필요할 때마다 매번 함수를 정의하고 싶진 않을겁니다. 그러나 지금까지 우리는 함수 정의 내에서 어떻게 패턴 매칭을 하는지에 대해서만 살펴봤습니다. Haskell의 경우 표현식(case expression)은 이 문제의 해법을 제공합니다. 사실, Haskell Report는 함수 정의에 있어서의 패턴 매칭의 의미를, (대개 좀 더 원론적이라고 간주하는) 경우 표현식 용어로 명세하고 있습니다. 특히, 다음과 같은 형태의 함수 정의는:

각각의 pij가 패턴일 경우 의미론상 다음과 동일하며:

여기서 xi는 새로운 identifier입니다. (Guard를 포함하는 좀 더 일반적인 해설은 §4.4.3참조하시기 바랍니다.) 예를 들어, 앞서 보인 take의 정의는 아래와 동일한 것입니다:

   1 take m ys    =  case (m,ys) of
   2                      (0,_)       ->  []
   3                      (_,[])      ->  []
   4                      (n,x:xs)    ->  x : take (n-1) xs

앞서 말하지 않았던 요점으로서, 타입의 정확성을 위해서, 함수 정의를 구성하는 경우표현식들이나 등식들의 우변은 모두 같은 타입이어야 합니다. 좀 더 엄밀히 말해서, 이들은 모두 공통의 최우선 타입(principal type)을 공유해야 합니다.

경우 표현식의 패턴 매칭 규칙은 앞서 살펴본 함수 정의에서와 같으므로, 경우표현식이 제공하는 편의성 외에는 여기에서 새로 배울 내용이 없습니다. 사실은, 너무나 흔히 사용되기 때문에 특수 구문을 갖고 있는 용법이 하나 있는데, 조건 표현식(conditional expression)입니다. Haskell에서 조건 표현식은 아래와 같이 친숙한 형태이며:

이것은 아래 표현의 단축형입니다:

위와 같은 확장으로부터 명백한 것은, e1Bool 타입을 가져야하고, e2e3는 (그것이 무엇이든 간에) 서로 같은 타입이어야한다는 사실입니다. 다시 말해서, if-then-else를 함수로 보자면 Boolaaa 타입을 갖습니다.

4.4 Lazy Patterns

Haskell이 허용하는 패턴이 한 가지 더 있습니다. Lazy pattern이라고 부르는 것이며 ~pat 형태를 취합니다. Lazy pattern은 irrefutable합니다: 값 v를 ~pat에 매칭시키는 것은 pat에 상관 없이 항상 성공합니다. 절차적으로 말해서, 만일 pat에 들어있는 identifier가 나중에 우변에서 ‘사용’되면, pat은 v가 pat에 성공적으로 대응되었다고 가정할 때 나타날 값 부분에 바인드되고, 그렇지 않으면 ⊥에 바인드됩니다.

Lazy pattern은 무한 자료 구조가 재귀적으로 정의되는 문맥에서 유용합니다. 예를 들어, 무한 리스트는 모의 실험 프로그램을 작성하는데에 매우 훌륭한 도구이며, 이런 경우 무한 리스트를 대개 stream이라고 부릅니다. 서버 프로세스 server와 클라이언트 프로세스 client 간의 상호작용을 모의 실험하는 경우를 고려해봅시다. 여기에서 client는 순차적인 요청server에 보내고 server는 각각의 요청에 대해서 어떤 반응으로 응답합니다. 이 모의 실험은 그림 2에 도식적으로 나타나 있습니다. (client는 인수로서 초기화 메세지도 받아들인다는 점에 주목하시기 바랍니다.)

그림 2: 클라이언트/서버 예제

메세지 열을 모의하기 위해 스트림을 사용하면 위 모식도에 상응하는 Haskell 코드는 다음과 같습니다:

   1 reqs     =  client init resps
   2 resps    =  server reqs

이런 재귀적인 등식은 모식도를 그대로 직역하여 만든 표현입니다.

서버와 클라이언트의 구조가 아래와 같다고 가정하도록 합시다:

   1 client init (resp:resps)    =  init : client (next resp) resps
   2 server      (req:reqs)      =  process req : server reqs

여기서 next는 서버로부터 응답 하나를 받아서 다음번 요청을 알아내는 함수고 process는 클라이언트로부터의 요청을 처리해서 적절한 반응을 내보내는 함수라고 가정합니다.

애석하게도 이 프로그램에는 심각한 문제점이 있습니다: 이 프로그램은 어떠한 결과도 만들어낼 수 없습니다! 문제는 client가, reqsresps의 재귀 속에서 사용된 것처럼, 첫번째 요청을 받기도 전에 반응 리스트에 매칭시키려고 시도한다는 것입니다! 다시 말해서, 패턴 매칭이 ‘너무 일찍’ 일어납니다. 이 문제를 수정하는 방법 중 하나는 client를 다음과 같이 다시 정의하는 것입니다:

   1 client init resps    =  init : client (next (head resps)) (tail resps)

이제 비록 동작을 하긴 하지만, 이런 해법은 이전에 보왔던 정의보다 가독성이 떨어집니다. 좀 더 나은 해법은 lazy pattern을 이용하는 것입니다:

   1 client init ~(resp:resps)    =  init : client (next resp) resps

Lazy pattern은 irrefutable하기 때문에 초기 요청이 ‘제공(submit)’되면서 즉시 매칭이 성공하고, 이렇게 첫번째 반응이 만들어집니다: 이제 엔진이 ‘장전’된 것이며, 나머지에 대해서 재귀가 일어납니다.

이 프로그램의 실제 동작 예로서 다음을 정의합니다:

   1 init           =  0
   2 next resp      =  resp
   3 process req    =  req+1

그러면 다음과 같음을 알 수 있습니다:

Lazy pattern을 사용하는 또다른 예로서, 전에 보았던 피보나치 수열의 정의를 살펴봅니다:

   1 fib    =  1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]

이걸 as-패턴을 사용해서 다시 작성할 수도 있습니다:

   1 fib@(1:tfib)    =  1 : 1 : [ a+b | (a,b) <- zip fib tfib ]

fib의 이번 버전은 우변에서 tail을 사용하지 않는다는 (사소한) 장점이 있으며, 이는 좌변에서 이미 tfib라는 ‘destructured’ 형태가 존재해서 이걸 사용할 수 있기 때문입니다.

이런 종류의 등식은 좌변 전체가 패턴인 최상위(top-level) 등식이기 때문에 패턴 바인딩이라고 부릅니다. 즉, fibtfib 모두 선언문의 스코프 내에서 바운드됩니다.

여기서 앞서와 같은 추론을 해 보면 이 프로그램도 아무런 결과를 내놓지 않을것이라고 생각하게 될지 모릅니다. 하지만 이상하게도 이 프로그램은 결과를 내며 그 이유는 간단합니다: Haskell에서 패턴 바인딩은 암묵적으로 그 앞에 ~를 가지고 있다고 가정하며, 패턴 바인딩의 가장 흔한 동작을 반영하면서 동시에 이 튜토리얼의 범위를 벗어나는 어떤 변칙적인 상황을 피하게 해줍니다. Haskell에서는 이렇게 lazy pattern이 암묵적으로나마 중요한 역할을 하고 있음을 알 수 있습니다.

4.5 Lexical Scoping and Nested Forms

종종, 다른 어떤 곳에서도 볼 수 없는 로컬 바인딩을 만들 목적으로 표현식 내에 중첩된 scope를—즉, 일종의 ‘블럭 구조’ 형태를—만들 필요가 있습니다. Haskell에서는 두 가지 방법이 있습니다:

Let Expressions.

Haskell의 let 표현식은 중첩된 바인딩 집합이 필요할 때 항상 유용합니다. 간단한 예로 아래 코드를 생각해봅시다:

   1 let y   = a*b
   2     f x = (x+y)/y
   3 in f c + f d

let 표현식이 만든 바인딩 집합은 상호 재귀적이며, 패턴 바인딩은 lazy pattern으로 (즉, 암묵적인 ~를 가지고있는 것으로) 취급됩니다. 여기서 허용되는 선언의 종류는 타입 지정문, 함수 바인딩, 그리고 패턴 바인딩 뿐입니다.

Where Clauses.

때때로 바인딩의 스코프를 몇 개의 guard된 등식들에 모두 걸치도록하면 편할 때가 있으며, 이를 위해서는 where 절이 필요합니다:

   1 f x y  | y > z     =  ...
   2        | y == z    =  ...
   3        | y < z     =  ...
   4      where z = x*x

자신이 감싸고있는 표현식에만 스코프를 펼치는 let 표현식으로는 위와 같이 할 수 없다는 점에 주목하십시오. where 절은 등식들의 집합의 최상위 위치나 경우표현식(case expression)에만 허용됩니다. let 표현식에 존재하는 바인딩들의 성질과 제한점들이 where 절의 바인딩들에도 똑같이 적용됩니다.

이런 두 가지 형태의 중첩 스코프는 매우 비슷해 보이지만, let 표현식은 표현식인 반면 where 절은 그렇지 않다는 사실을 기억하시기 바랍니다. — where 절은 함수 선언 구문과 경우 표현식 구문의 일부입니다.

4.6 Layout

어떻게 Haskell 프로그램이 등식이나 선언 등의 끝을 나타내는 데에 세미콜론이나 어떤 다른 종류의 종결자를 사용하지 않을 수 있는지 궁금하실겁니다. 방금 전 절에서 살펴본 let 표현식을 예로 들어보겠습니다:

   1 let y   = a*b
   2     f x = (x+y)/y
   3 in f c + f d

이걸 아래와 같이 파싱하면 안된다는걸 파서는 어떻게 알고 있을까요?

   1 let y = a*b f
   2     x = (x+y)/y
   3 in f c + f d

답은 Haskell이 layout이라고 불리는 2차원적인 구문을 사용하기 때문이며, 이 layout은 ‘열을 맞춰 나열된’ 선언에 의존하고 있습니다. 위 예에서 yf가 같은 열에 쓰여있다는 점에 주목하시기 바랍니다. Layout의 규칙에 대해서는 Haskell Report(§2.7, §9.3)가 자세하게 설명하고 있지만, 일반적으로 레이아웃의 용법은 조금 직관적입니다. 그저 두 가지만 기억하십시오:

첫째, 키워드 where, let, of 중 어느 한가지의 뒤에 연이어 나오는 문자는 현재 작성하고 있는 where 절이나 let 혹은 case 표현식에 등장하는 선언문들의 시작 열을 결정합니다. (이 규칙은 5장에서 소개할 클래스와 인스턴스 선언에 사용되는 where에도 마찬가지로 적용됩니다.) 이렇게 우리는 키워드와 같은 행이나 다음 행에서 선언을 시작할 수 있습니다. (나중에 논의할 do 키워드도 레이아웃을 사용합니다.)

둘째, 시작 열은 그것을 바로 곁에서 감싸고 있는 절과 관련된 시작열보다 명백하게 우측에 있어야 한다는 점만 주의하시면 됩니다. (그렇지 않으면 모호해지죠.) 선언의 ‘종료’는 그것의 binding form과 관련된 시작 열보다 좌측이나 같은 위치에 뭔가가 나타날 때 이루어집니다. (Haskell은 탭을 공백 8개로 간주하는 관례를 따릅니다: 따라서 이 관례를 따르지 않는 편집기를 사용할 때에는 매우 주의를 기울여야합니다.)

Layout은 실제로는 명시적인 그룹화 기전의 축약형이며, 이런 명시적 그룹화 기전은 경우에 따라 유용하기 때문에 알아둘만한 가치가 있습니다. 위에서 든 let 예제는 아래와 동일합니다:

   1 let { y   = a*b
   2     ; f x = (x+y)/y
   3     }
   4 in f c + f d

명시적인 중괄호와 세미콜론에 주목하십시오. 이런 명시적 표기가 유용한 한 가지 경우는 한 행에 여러개의 선언이 요구될 때입니다. 예를 들어 아래와 같은 표현은 유효합니다:

   1 let y   = a*b;  z = a/b
   2     f x = (x+y)/z
   3 in f c + f d

레이아웃을 명시적인 경계기호(delimiter)로 확장하는 또다른 예는 §2.7을 보시기 바랍니다.

레이아웃을 사용하면 선언 리스트와 관련된 문법적 혼란을 획기적으로 줄일 수 있으며, 따라서 가독성이 높아집니다. 배우기 쉬우며, 사용을 적극 권장합니다.


이전 다음 위로
A Gentle Introduction to Haskell, Version 98

Copyright © 1999 Paul Hudak, John Peterson and Joseph Fasel

Permission is hereby granted, free of charge, to any person obtaining a copy of “A Gentle Introduction to Haskell” (the Text), to deal in the Text without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Text, and to permit persons to whom the Text is furnished to do so, subject to the following condition: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Text.