Haskell Tutorial

Haskell-Tutorial

 

함수형 프로그래밍을 위한 많은 책들이 있습니다. 비록 모두 좋은 책들이긴 하지만 저자들이 – 자신이 - 이전에 배웠던 모든 것을 - 한꺼번에 - 학생들에게 가르치려고 노력합니다.

따라서 독자들은 공부해야 할 양이 만만치 않을뿐더러 이론적인 내용들을 적용할 만한 구체적이고 실용적인 예제가 부족하기 때문에 처음 배우기 시작할 무렵에 어려움을 느끼게 됩니다. 대개 독자들은 프로그래밍의 추상적인 개념을 사용하는 것에 대해 호기심을 갖고 있지만 어떻게 시작해야 할지 모릅니다.

따라서 우리는 초보자를 위해 함수형 언어의 핵심적인 내용을 여기에서 설명하고자 합니다. 그래서 독자들은 실제적인 문제들을 코딩 하게 되고, 차후에 익힐 과목을 위한 이론적 배경에 대한 지적 욕구를 불러 일으킬 수 있습니다.

이 문서는 독자들이 기본적인 수학 지식에 익숙하다고 가정했습니다.

그러나 우리는 몇몇 독자들이 중요하게 여길 수 있는 두 가지 사항을 무시하고 있습니다.

 

-           우리는 효율성(efficiency)에 대해 고려하지 않았습니다. 우리는 함수를 구현하고 모델을 생성하고자 합니다. 따라서 우리는 빠르고 강력한 소프트웨어 보다는 이해하기 쉬운 모델에 중점을 둡니다.

-           우리는 사용자 인터페이스를 구현하지 않습니다. 사용자나 다른 프로그램 혹은 파일과의 상호 작용에 대해서도 고려하지 않습니다. 단지 모델링을 위해 언어를 사용하며 커맨드 라인에서 테스트를 수행합니다.

 

1. 전제 조건(Prerequisites)

모든 예제는 즉각 테스트할 수 있기 때문에 이 문서를 읽는 동안 컴퓨터를 앞에 두고 있는 것이 좋습니다. 따라서 Hugs와 적절한 문서 편집기(예를 들어 UltraEdit)를 설치해 두는 것이 좋습니다.

 

1.1 Hugs 설치 방법(How to install Hugs?)

어떤 프로그래밍 언어든지 소스를 직접 실행해 볼 수 없이 읽기만 해야 한다면 무척 지루한 일일 것입니다. Haskell에는 Hugs(Haskell User’s Gofer System)라고 부르는 프로그램이 있습니다. 인터넷(www.Haskell.org)에서 최신 버전을 구할 수 있다.

	DOS-version	Windows-version
Command line	dir \HUGS.EXE %F	dir \WINHUGS.EXE %F
Working directory	%P	%P
Windows program?	Not checked	Checked

Table 1: UltraEdit에서 사용 도구에 Hugs를 추가하기 위한 파라미터

 

이 문서가 만들어지던 시점(2003년 2월)에서 가장 최근에 나온 버전은 2002년 11월 버전입니다. (역자 주: 현재 2006년 버전이 나와 있습니다.) 마이크로 소프트의 윈도우, 유닉스, 리눅스, 맥 OS X 그리고 맥 OS 9를 위한 버전들이 나와 있습니다. 우리는 사용자 인터페이스에 대해 이야기할 때 항상 윈도우 버전을 가지고 이야기할 것입니다. 다른 운영체제를 위한 문서는 그에 해당하는 문서를 읽기 바랍니다. 윈도우 파일은 윈도우 설치 패키지(msi)로 되어 있습니다. (역자 주: 2006년 버전은 실행 파일 형태로 되어 있습니다.) 이 파일을 더블 클릭하면 바로 설치가 됩니다. 추가적인 정보를 얻거나 문제를 해결하려면 도움말 파일을 읽기 바랍니다.

 

-           최신 Hugs 버전을 여러분의 하드 디스크에 다운 받습니다.(현재는 ‘hugs98-Nov2002.msi’입니다.)

-           인스톨 프로그램을 실행합니다.

-           문서 편집기가 미리 설치되어 있는지 확인합니다. 만약 좋은 문서 편집기를 가지고 있지 않다면 바로 설치합니다.

-           만약 UltraEdit를 사용하려면 Hugs에 편집기 옵션을 다음과 같이 설정합니다. (Options/Set...) UEdit32 %s %d/1. 만약 다른 문서 편집기를 사용하려면 “UEdit32” 부분을 해당 편집기 이름으로 바꾸고 편집기에서 파일을 열거나 특정 라인으로 이동하기 위해 파라미터를 다른 값으로 바꾸면 됩니다.)

 

테이블 1에서 Hugs를 UltraEdit에 도구로 추가하기 위한 명령어들을 설명해 놓았습니다. 커맨드 라인에 있는 dir를 Hugs가 설치된 디렉토리로 바꿔야 합니다.

 

1.2 이 문서에서 우리가 배우고자 하는 것(What are we going to learn in the tutorial?)

무엇이든 유용한 것을 배우는 것은 어렵습니다. 물론 이 문서를 통해 함수형 프로그래밍을 익히는 것도 쉬운 일이 아닙니다. (만약 여러분이 어떤 다른 정형화 기법(formal method)에 관심 있다면 일차 논리(first order logic)에 대한 책을 하나 구해서 한 두 챕터 정도 읽어보기 바랍니다.)

여러분은 Hugs를 이용한 쉬운 예제를 통해 – 함수형 프로그래밍에 – 익숙해 질 것입니다. (이에 대한 의견이나 추천이 있으면 언제든지 주기 바랍니다.) 우리는 함수나 자료 형에 대한 정의 같은 쉬운 것부터 시작할 것입니다. 그리고 이 후에 객체 지향 프로그래밍이나 모듈화와 같은 보다 복잡한 방법들에 대해 알아볼 것입니다.

 

2. 기본 형, 우리가Haskell로 할 수 있는 것이 무엇인가?(Basic Types, or “How to bring Haskell to work for me at all?”)

Hugs에서 다음과 같은 함수를 수행하십시오. - 파일에 소스를 저장하고 Hugs에서 불러와 테스트해보기 바랍니다.

 

2. 1 “Hello, world” 를 커맨드 라인에서 출력하기

이것은 대단하지는 않지만 모든 언어에서 할 수 있는 것입니다. Haskell은putStr이라는 연산자(함수)를 가지고 있어서 화면에 문자열을 쓸 수 있습니다. Hugs를 실행하고 커맨드 라인에 아래와 같은 문장을 입력합니다.(인용 부호도 같이 입력합니다.) (저자 주: “Hello”는 문자열을 뜻합니다. 파스칼처럼 Haskell도 문자열의 시작과 끝을 나타내기 위해 이중 인용 부호를 사용합니다. 단독 문자는 일반 인용 부호를 사용합니다. 문자열은 “abc”, 문자는 ‘a’, ‘b’, ‘c’)

 

          putStr “Hello”

 

이에 대한 결과는 아래와 같습니다.

 

          Hello

          (2 reductions, 7 cells)

          ?

 

첫 줄은 결과값을 두 번째 줄은 수행한 명령에 대한 정보를 나타냅니다. 인터프리터는 함수를 각 부분이 직접적으로 구현될 수 있는 간단한 형태가 될 때까지 보다 쉬운 함수로 변환(replacements)합니다.(Basic과 같은 다른 인터프리터 언어와 비슷하다.) 이런 각 변환(replacements)을 ‘환산(reductions)’이라 부릅니다. ‘cell’은 환산이나 결과 출력을 위해 사용된 메모리 사용량을 말합니다.

편집기를 열고(커맨드 라인에서 ‘:e’ 를 입력합니다.) 편집기 창에 아래와 같은 명령어를 입력합니다. (편집기에서 ‘새 파일’ 이나 ‘다른 이름으로 저장’을 이용한다.) 우리는 그것을 함수처럼 작성할 것입니다. 함수 이름(여기서는 f라고 했습니다.)을 정하고 ‘=’문자로 함수의 정의와 이름을 구분합니다. 확장자를 ‘.hs’로 하여 파일을 저장합니다.

 

          f = putStr “Hello”

 

Hugs에서 이 파일을 불러와 실행합니다. Hugs에서 함수를 실행하는 것은 쉬운 일입니다. 단지 함수의 이름(여기서는 f)과 인자(여기서는 없음.)를 입력하면 됩니다. 결과는 아래와 같습니다.

 

          ? f

          Hello

          (3 reductions, 15 cells) (역자 주: 이 값은 Hugs 버전에 따라 다를 수 있습니다.)

 

위 결과에서 다른 점은 환산(reduction)이 3(이전에는 2)이고 cell이 15(이전에는 7)이라는 사실입니다. 환산 값이1만큼 증가한 것은 인터프리터가 f를 putStr “Hello”로 변환해야 하기 때문입니다. 또한 이런 추가적인 환산은 약간의 메모리를 더 사용합니다.

 

2.2 Haskell에서 함수 작성하기

함수형 언어에서는 모든 것이(심지어 프로그램 자체도) 함수입니다. 그래서 프로그램을 작성하는 것은 실제적으로 함수를 작성하는 것과 같습니다. 여러분은 하나의 파일에 여러 개의 함수를 작성할 수 있는 것처럼 하나의 파일에 여러 개의 프로그램을 작성할 수 있습니다. 각각의 함수는 결과를 계산하기 위해 다른 함수를 사용(호출)할 수 있습니다. 다른 프로그래밍 언어처럼 Haskell도 미리 정의된 많은 함수를 가지고 있습니다. 이러한 함수들을 정의한 파일은 ‘hugs98\lib’에서 찾을 수 있습니다.

함수를 작성하는 것은 크게 두 가지 부분으로 구성됩니다. 하나는 함수의 인자와 결과 값의 타입을 정의하는 것입니다. 함수는 인자가 없을 수 있습니다. 이런 것을 상수 함수라 부릅니다. π 값을 반환하는 함수 pi는 인자를 필요로 하지 않는 함수의 대표적인 예입니다. – 상수 함수를 제외한 – 다른 함수들은 하나 이상의 인자를 가질 수 있습니다. 그러나 모든 함수는 - 인자 값은 여러 개가 될 수 있지만 - 결과값은 하나만 갖습니다. (역자 주: 엄밀히 말하면 이 말의 뜻은 하나의 ‘타입값’을 갖는 다는 뜻입니다. 뒤에 설명할 리스트와 같은 타입은 여러 개의 단일 값들이 구성된 하나의 타입이며 함수는 이런 리스트를 결과값을 가질 수 있습니다.)

 

          increment :: Int -> Int

 

우리가 정의한 새로운 함수의 이름은 increment 입니다. ‘::’는 함수의 이름과 타입 정의 부분을 분리하는 역학을 합니다. 만약 하나 이상의 타입이 있다면 -> 에 의해 분리될 수 있습니다. 리스트의 마지막 타입은 결과 값의 타입이 됩니다. (역자 주: 만약 파스칼로 위 함수를 작성한다면 다음과 같습니다. function increment (i: Integer) : Integer) (역자 주: 만약 C로 위 함수를 작성한다면 다음과 같습니다. int increment(int))

함수 작성의 두 번째 부분은 실제적인 구현 부분입니다. 아래가 그 예입니다.

 

          increment x = x+1

 

increment는 Int(정수)형 인자 하나를 받고 역시 Int 형 결과를 반환하는 함수입니다. 이 함수를 테스트하기 위해 Hugs 프롬프트 상에서 “increment 2”(인용 부호는 입력하지 않습니다.) 를 입력하면 아래와 같이 나옵니다.

 

          3 :: Int

 

만약 Hugs에서 타입 없이 3만 출력된다면 “Options/Set...” 메뉴에서 “show type after evaluation”을 확인해 보기 바랍니다. 이 값이 체크되어 있지 않으면 인터프리터는 구체적인 타입 없이 결과 값만을 출력합니다.

다른 예를 보도록 하겠습니다. 다른 프로그래밍 언어처럼 Haskell은 Boolean 값을 위한 자료 형을 미리 정의해 놓았습니다. Boolean을 위해 중요하게 사용되는 연산자로 논리 연산자 and가 있습니다. 비록 Haskell에서 이미 이 함수가 구현되어 있지만 우리는 이것을 다시 아래와 같이 구현해 보겠습니다.

 

          and1 :: Bool -> Bool -> Bool

          and1 a b = if a == b then a

                                       else False

 

여기서 우리는 (if-then-else) 분기를 사용하여 결과 값에 따라 다른 계산을 수행하도록 하였습니다. 만약 매개 변수가 같다면(둘 다 참 혹은 거짓인 경우) 이 함수는 매개 변수 중 하나를 반환하며 두 매개 변수가 다르다면 False를 반환합니다.

패턴 매칭(pattern matching)을 이용하면 다른 방식으로 구현할 수 있습니다. 논리 연산자(함수) ‘and’는 특별한 경우에 ‘참’을 반환하며 나머지 경우에는 거짓을 반환합니다. 우리는 매개 변수가 어떤 값일 때 그런 특별한 경우가 되는지 알고 있습니다. 우리는 이 매개 변수를 별도의 줄에서 정의하고 그 결과를 추가할 수 있습니다. 그 외에 모든 다른 경우는 다음 줄에서 정의한다.

 

and2 :: Bool -> Bool -> Bool

and2 True True = True

and2 x    y    = False

 

위 예제에서 우리는 두 번째 함수 정의(위 소스의 세 번째 줄)의 결과 값을 계산하기 위해 매개 변수를 사용하지 않습니다. 다시 말하면 세 번째 중에서 and2 함수는 상수 값을 반환하기 때문에 매개 변수의 값을 알 필요가 없습니다. Haskell에서는 이러한 – 사용하지 않는 - 매개 변수에 이름을 붙이는 대신 ‘_’을 사용할 수 있습니다. 이렇게 하면 읽는 이에게 매개 변수의 개수를 알려주면서도 이 값들이 결과 값에 상관이 없다는 것을 알려주는 장점이 있습니다. 따라서 두 번째 함수 정의는 아래와 같이 표현할 수 있습니다.

 

          and2 _ _ = False

 

2.3 2차 방정식의 근 구하기(where와 if then else에 대한 공부)

함수를 구현하기 위해서는 먼저 문제를 정의해야 합니다. 즉, 우리는 해결책이 가진 특성을 정의해야 합니다.

먼저 여러분이 구현하는 함수가 실제적인 프로그램이라는 점을 기억하기 바랍니다. 프로그래밍을 하는 동안에는 초안, 메모, 책, 이전에 작성한 예제 등을 사용하십시오. 프로그래밍은 단순히 글자를 입력하는 작업(typing)이 아닙니다. 프로그래밍은 기예(art, 伎藝)입니다.

2차 방정식은 a2*x^2 + a1*x + a0 = 0과 같은 형태를 갖습니다. 2차 방정식은 두 개의 근(혹은 만약 두 근이 같다면 하나)을 갖는데 수학적인 해법은 아래와 같습니다.

 

          x1 = (-b – sqrt(b^2 – 4ac)) / 2a

          x2 = (-b + sqrt(b^2 – 4ac)) / 2a

 

근을 계산하는 함수는 세 개의 입력 값을 받으며 하나의 결과 값을 반환합니다. 만약Float 타입의 값을 사용하면, Haskell에서는 아래와 같이 정의할 수 있습니다.

 

          roots :: (Float, Float, Float) -> (Float, Float)

 

함수의 이름은 roots 입니다. ‘::’는 함수의 이름과 타입 정의 부분을 분리해 줍니다. ‘->’는 다른 타입 정의들을 구분해 줍니다. 타입 정의의 마지막 부분은 함수의 결과 값에 대한 정의이며 나머지는 매개 변수에 대한 정의입니다. 즉, 타입 정의 (Float, Float, Float)은 이 함수의 매개 변수에 대한 정의입니다. 이것은 Float 값의 3개 쌍(triple)을 나타냅니다. 함수의 결과는 (Float, Float)이며 Float 값의 쌍(pair)이 됩니다. (역자 주: Haskell에서는 여기 나온 것처럼 소괄호로 여러 개의 값을 묶은 형식의 타입 값을 지원합니다.)

아래는 함수 roots에 대한 구현 부분입니다.

 

          roots (a, b, c) = (x1, x2) where

                        x1 = e + sqrt d / (2*a)

                        x2 = e – sqrt d / (2*a)

                        d = b*b – 4*a*c

                        e = -b / (2*a)

 

이 함수의 결과는 (x1, x2) 쌍입니다. 두 값x1, x2는 (where 절 이후에 나오는) 부분 정의(local definition)에 의해 구현되며 이것은 결과의 각 부분을 계산합니다. 일반적으로 부분 정의(local definition)는 계산 결과가 여러 곳에서 사용돼야 하는 부분 식을 만들 때 유용합니다. 여기서는 부분 정의의 결과인 d와 e가 두 해법(x1, x2)를 위해 사용된다. 부분 정의식을 전체 정의 부분에 직접 적용할 수도 있지만 부분 정의로 분리하여 사용하면 해법의 대칭 부분이 명확해지기 때문에 코드의 가독성이 향상됩니다.

사용한 수식은 2차 방정식의 근을 구하기 위한 유명한 공식이다. 이 함수는 동작은 하지만 제곱근이 음수가 되는 경우를 고려하지 않았습니다. 우리는 아래처럼 정의한 두 개의 다항식 p1과 p2를 가지고 테스트할 수 있습니다.

 

p1, p2 :: (Float, Float, Float)

p1 = (1.0, 2.0, 1.0)

p2 = (1.0, 1.0, 1.0)

 

p1에 대한 결과는 아래와 같다.

 

? roots p1

(-1.0, -1.0) :: (Float, Float)

(94 reductions, 159 cells)

 

그러나 p2는 아래와 같이 결과가 나온다. (역자 주: 에러 메시지는 인터프리터의 버전마다 조금씩 다릅니다. 역자의 경우 Program error: argument out of range 라는 에러 메시지가 발생했습니다.)

? roots p2

(

Program error: {primSqrtFloat (-3.0)}

(61 reductions, 183 cells)

 

Program error: 표시는 실행 시점에서 에러가 발생했음을 뜻합니다. 위 메시지에서 괄호가 표시된 이유는 Haskell이 에러가 발생하기 전에 결과를 출력하려 했기 때문이며 괄호는 결과 쌍을 위한 문장의 시작 부분입니다. 어쨌든 에러 표시 이후에 나오는 문장은 에러의 원인을 설명하는 문장입니다. 여기서는 매개 변수 -3.0이 음수이고 따라서 실수 제곱근을 가지고 있지 않기 때문에 primSqrtFloat 함수가 이 값을 처리할 수 없다는 것을 의미합니다. 함수 primSqrtFloat는 Float 타입을 위해 하드 코딩 된 sqrt 함수의 정의 부분입니다.

우리는 실수 제곱근이 존재하지 않는 예외를 처리하기 위해 코드를 수정해야 합니다.

 

          roots (a,b,c) = if (d < 0 then error “sorry” else (x1, x2)

                        where    x1 = e + sqrt d / (2*a)

                                     x2 = e – sqrt d / (2*a)

                                     d = b*b – 4*a*c

                                     e = -b / (2*a)

 

이 함수는 이제 부분 정의(local definition) d의 값을 확인해보고 이 값이 음수이면 사용자가 정의한 오류 메시지를 출력합니다. 만약 d값이 양수이면 전에 정의한 대로 결과를 계산합니다.

이 해법에 대해 몇 가지 설명할 것이 있습니다.

 

-           if-then-else 구문은 만약 조건식을 만족하면 첫 번째 부분(then 이후 부분)을 수행하고 그렇지 않으면 두 번째 부분(else 이후 부분)을 수행합니다.

-           where 는 이전 줄과 연결된 부분이라는 것을 의미합니다. 그것은 들여쓰기를 해야 하며 다음에 나오는 네 줄 역시 모두 같은 단계(level)이므로 동일한 들여쓰기를 해야 합니다. (역자 주: Haskell은 python처럼 들여쓰기로 코드 블록을 구분합니다.)

-           d < 0.0인 경우에 x1 에 있는 sqrt d를 계산하려면 어떻게 해야 할까요? 함수형 언어는 단지 결과가 필요할 때만 해당 표현식을 계산하기 때문에 만약 d가 0보다 작으면 절대로 그 수식을 계산하지 않습니다.

n         만약 프로그램이 d값을 필요로 한다면 d를 계산한다. 만약 d값이 0.0보다 작으면 프로그램은 에러 메시지를 출력하고 종료합니다.

n         만약 d가0.0보다 작지 않으면(즉, 크거나 같으면) x1을 계산하고 이 때 계산에 필요한 e를 계산하며 그 다음에 x2를 계산하고 실행을 종료합니다.

 

올바른 동작을 위해서는 함수를 테스트해야만 합니다. 만약 인터프리터가 에러 메시지를 출력하지 않으면 함수는 모든 문법 규칙을 준수한 것이다.(예를 들어 모든 여는 괄호와 닫는 괄호가 일치하는 것) 만약 파일을 불러오거나 혹은 함수를 실행하는 도중 type이라는 단어를 포함한 에러 메시지가 발생한다면 함수의 타입 구조가 잘못되었다는 것을 의미합니다. (예를 들어 함수의 타입 명세가 일치하지 않음) 마지막으로 구문상으로(syntactically) 올바른 함수라고 해서 의미상으로(semantically) 올바른 것은 아닙니다. 즉, 잘못된 결과를 출력하거나 혹은 결과 값이 나오지 않을 수 있습니다. 따라서 우리는 몇몇 경우를 가지고 새로운 함수를 테스트해야 합니다.

 

2.4 몇 가지 미리 정의된 타입들

Haskell에서 미리 정의된 가장 중요한 타입들을 테이블 2에 요약해 놓았습니다.

Bool	True, False
Int	-100, 0, 1, 2...
Integer	-33333333333, 3, 4843056380457832945789457,...
Float/Double	-3.22425, 0.0, 3.0,...
Char	‘a’, ‘z’, ‘A’, ‘Z’,...
String	“Medak”, “Navratil”,...

테이블 2. 미리 정의된 타입들

 

2.5 요약

-           함수는 서명(signature)를 갖습니다. 서명(signature)은 함수 인자와 결과에 대한 타입을 선언하는 명세를 말합니다.

-           들여쓰기는 중요합니다.

1.       최상위 단계의 선언은 최초 열(역자 주: 전체 소스에서 가장 왼쪽으로 들여쓰기 된 것을 의미함)에서 시작하고 최초 열에서 시작하는 그 다음 선언 직전 부분에서 끝납니다.

2.       선언은 어떤 위치에서든 중단될 수 있으며 이전 줄보다 더 많이 들여 쓰기를 하면 다음 줄에서 계속 이어질 수 있습니다.

3.       만약 where 구문을 사용하면 하나 이상의 선언을 이어서 할 수 있습니다. 단, 이 선언들은 반드시 같은 단계의 들여쓰기를 해야 합니다.

-           함수는 최대한 명확하게 작성해야 합니다. (함수의 이름을 설명적으로 만들어야 합니다.) 예를 들어 matrixMult라는 이름의 함수는 mM보다 가독성 면에서 이해하기 쉽습니다.

-           주석 역시 유용합니다. ‘--‘뒤에 오는 것들은 모두 주석으로 처리됩니다. (역자 주: Perl의 #, C++에서의 // 와 유사, 참고로 C/C++의 /*…*/와 같은 주석처리를 위해서는 {-…-}를 사용)

-           함수는 쉽게 수동으로 확인할 수 있는 예제로 테스트하기 바랍니다.

 

연습문제: 위 프로그램을 복소수를 처리할 수 있도록 확장하라. (복소수는 실수의 쌍(pair)으로 표현됩니다.)

 

3. 리스트, 어떻게 이렇게 간단하면서 유용할 수 있는가?

이전 예제에서 우리는 자료형 pair (x1, x2)와 triple (a, b, c)를 보았다. (일반적으로 이런 것들을 튜플(tuple)이라고 한다.) pair는 정확히 두 개의 요소를 가지며 triple은 세 개를 갖는다. 우리는 또한 넷, 다섯 혹은 그 이상의 요소를 갖는 tuple를 만들 수 있지만 그 요소의 개수는 항상 고정적이다. 그러나 튜플의 요소는 다른 타입이 될 수 있다. 예를 들어 pair의 첫 번째 요소는 이름(문자열)이고 두 번째 요소는 나이(수)가 될 수 있다.

리스트는 무엇일까? 리스트는 같은 타입이고 임의의 개수를 갖는 요소들을 처리하는 방법을 제공한다. 리스트는 아무런 요소를 가지지 않을 수도 있다. 빈 리스트는 []로 표기한다. 리스트는 어떤 타입도 가질 수 있지만 모든 요소는 같은 타입이어야 한다. 다시 말하면 리스트는 같은 타입(수, 문자열, Boolean 값...)의 요소에 대한 1차원 집합이다. 리스트의 예는 아래와 같다.

 

          []                                    -- 빈 리스트

          [1, 2]                               -- 정수형 요소 리스트

          [True, False]                   -- Boolean 형 요소 리스트

          [(1, 2), (2, 3)]                  -- 정수형 tuple의 리스트

          [[1, 2], [2, 3, 4]]             -- 정수 리스트의 리스트

 

문자열 역시 리스트이다.

 

          “Name” = [‘N’, ‘a’, ‘m’, ‘e’]

 

리스트의 요소는 첫 번째 요소(리스트의 머리)와 나머지 요소(리스트의 꼬리)에 대해서만 접근할 수 있다. 따라서 만약 리스트의 다른 요소에 접근하려면 리스트를 재귀적으로 읽어야 한다. 예를 들어 다음 함수는 리스트의 n번째 요소에 접근하는 기능을 가지고 있다.

 

          nthListE1 L 1 = head L

          nthListE1 L n = nthListE1 (tail L) (n-1)

 

3.1 재귀: 함수형 프로그래밍의 중요 원칙, 누가 루프(loop)와 카운터(counter)를 훔쳤는가

표준 펙토리얼 함수[1]는 수학적으로 자기 자신을 이용해서 정의된다.

 

          fact n    = 1                      : n == 0

                        = n*fact(n-1)       : n != 0

 

펙토리얼 함수는 수학적 유도과정(초기 상태인 경우와 후속 상태(successor)인 경우에 대한 유도)에 대한 다소 간단한 예이다.

 

1)      p(0),

2)      p(n) => p(n+1)

 

우리는 Haskell에서 이 것을 문법적으로 쉽게 변환할 수 있다.

 

          fact 0 = 1                          -- 초기 단계

          fact n = n * fact (n-1)        -- 유도 과정

 

이 프로그램은 어떻게 동작할까? 6의 펙토리얼인 경우를 예로 들어 보도록 하겠다. n은 6이므로 0이 아니다. 따라서 유도 과정이 적용되므로 6 * fact 5 이다. n은 5이므로 0이 아니다. 따라서 유도 과정은 6 * (5 * fact 4)가 된다. 이것은 n이 0이 될 때까지 계속 된다. 초기 단계가 되었을 때 재귀는 종료된다.

 

          fact 6     ==> 6 * fact 5

                        ==> 6 * (5 * fact 4)

                        ==> 6 * (5 * (4 * fact 3))

                        ==> 6 * (5 * (4 * (3 * fact 2)))

                        ==> 6 * (5 * (4 * (3 * (2 * fact 1))))

                        ==> 6 * (5 * (4 * (3 * (2 * (1 * fact 0)))))

                        ==> 6 * (5 * (4 * (3 * (2 * (1 * 1)))))

                        ==> 6 * (5 * (4 * (3 * (2 * 1))))

                        ==> 6 * (5 * (4 * (3 * 2)))

                        ==> 6 * (5 * (4 * 6)))

                        ==> 6 * (5 * 24)

                        ==> 6 * 120

                        ==> 720

 

위 증명은 한 가지 중요한 사실에 기반하고 있다. 0을 포함한 자연수의 완전한 집합은 두 가지 경우로 망라될 수 있다.

 

1.       자연수는 0이거나 (0인 경우)

2.       또는 다른 자연수의 후속 상태(successor)가 된다. (유도 단계)

 

수학에 대한 이야기를 위에서 잠깐 언급한 이유는 이것이 Haskell에 있는 리스트에 대한 유사한 재귀 상황을 보다 쉽게 이해하도록 만들어 주기 때문이다. 리스트는 두 가지 경우를 갖는다.

 

1.       빈 리스트

2.       하나의 요소와 나머지 요소(빈 리스트도 포함)들로 이루어진 리스트

 

완벽한 정의를 위해 우리는 리스트의 요소들을 서로 합쳐주는(glue) 중요한 함수 하나를 알아야 한다. – 리스트를 합쳐주는 함수 (:)는 ‘cons’라고 발음한다. 이 것은 다음과 같은 타입을 갖는다.

 

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

 

그리고 아래와 같이 동작한다.

 

          1 : 2 : 3 : [] = [1,2,3]

 

이제 두 가지 경우에 대해 리스트를 재귀적으로 정의할 수 있다.

 

          []                       -- 빈 리스트

          (x: xs)                 -- 최소한 하나의 요소를 가진 리스트

 

          List = [] | (a : List)

 

이것은 리스트가 빈 리스트이거나 혹은 하나의 요소와 그 뒤에 또 다른 리스트(이것은 다시 빈 리스트나 혹은 다시 또 다른 리스트에 대해서 재귀적으로 정의될 수 있다)를 갖는다는 것을 의미한다. 변수 a가 의미하는 것은 리스트의 요소가 어떤 타입이든지 가능하다는 것을 뜻한다.[2]

리스트의 구조는 리스트가 저장하는 자료의 형과 상관없다. 단지 리스트의 요소들이 반드시 같은 타입이어야 한다는 제약을 할 뿐이다. 우리는 정수 리스트 혹은 Boolean 이나 부동 소수점 수의 리스트를 가질 수 있지만 5개의 정수와 2개의 Boolean 값을 갖는 리스트를 만들 수는 없다. 이 정의를 응용하면 리스트를 이용한 어떤 함수를 구현하는 것도 가능하다. 예를 들어 리스트의 모든 요소의 합계를 내는 함수를 구현해 보자.

 

          sumList :: [Int] -> Int

          sumList [] = 0

          sumList (x: xs) = x + sumList xs

 

우리는 빈 리스트를 가질 때까지 리스트의 나머지 부분으로부터 재귀적으로 첫 번째 요소를 분리한다. 우리는 빈 리스트의 결과를 이미 알고 있다. 따라서 우리는 이제 분리되는 과정의 역순으로 리스트의 요소들을 더해 나갈 수 있다. 이것은 우리가 마지막 요소가 0과 더해지고 마지막 이전 요소와 이전에 계산한 값이 더해지고 하는 과정이 반복된다는 것을 의미한다. 리스트의 모든 요소를 처리하고 나면 우리는 리스트의 모든 요소에 대한 합계 결과를 얻을 수 있다. 또한 리스트 구성자(constructor)[3]를 사용하여 리스트의 n번째 요소를 읽는 함수를 다시 만들 수 있다.

 

          nthListE1’ = (l:ls) 1 = l

          nthListE1’ = (lLls) n = nthListE1’ ls (n-1)

 

3.2 리스트를 위한 기본 함수들

head	리스트의 첫 번째 요소를 반환한다.
tail	리스트의 첫 번째 요소를 제거한다.
length	리스트의 길이를 반환한다.
reverse	리스트를 역순으로 만든다.
++(concat)	두 리스트를 합친다. [1,2] ++ [3,4] = [1,2,3,4]
map	리스트의 각 요소를 함수에 적용한다.
filter	특정 조건을 만족하는 요소들의 리스트를 반환한다.
foldr	특정 함수와 시작 값을 리스트의 요소들과 결합한다.
zip	두 리스트를 받아 적절한 (같은 위치에 있는) 요소끼리 pair로 만든다.
zipWith	두 리스트를 받아 적절한 (같은 위치에 있는) 요소들을 특정 함수에 적용한다.

테이블 3. 유용한 리스트 함수들

 

리스트에 사용되는 몇몇 중요한 함수들이 있다. 가장 중요한 리스트 함수들을 몇 개를 테이블 3에 보이고 이것들이 무엇인지 간단하게 설명해 놓았다. 위 함수들 중 몇 개(예를 들어 map)는 특별히 흥미로운데 그 이유는 이 함수들이 함수 인자로 함수 자체를 받기 때문이다. – 우리는 이런 함수들을 고차 함수(higher order function)이라고 부른다. 다음 절에서 이런 함수들 몇 개를 사용할 것이다.

 

3.2.1. 여러분의 이름을 ASCII 숫자로 변환하는 코드를 작성하라. (map으로 할 수 있는 일이 무엇인지 아는가?)

여러분은 지금 문자열을 하나 가지고 있고 이 문자열의 각 문자가 ASCII 코드로 무엇인지 알아야 된다고 가정해 보자. Haskell에서 문자열은 문자(character)의 리스트이다. 따라서 이 문제를 해결하기 위해서는 리스트 함수를 사용해야 한다. ASCII 숫자를 계산해 주는 ord 함수를 각 문자에 적용해야 한다. 문자열은 문자의 리스트이고 이것을 ASCII 숫자의 리스트로 코딩해야 하므로 문자열의 각 문자에 ord 함수를 적용해야 한다. 비로 이것이 map이 할 수 있는 일이다. map의 타입 정의는 아래와 같다.

 

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

 

map 함수는 두 개의 인자, 함수와 리스트를 받고 리스트를 결과로 반환한다. 입력된 리스트는 임의의 타입 a의 요소를 가지며 결과로 출력되는 리스트는 임의의 타입 b의 요소를 가진다. – map이 매개 변수로 받는 - 함수는 a타입의 매개변수를 받아 b타입 결과를 반환한다. 위 예제에서는 a 타입이 문자가 되며 b 타입이 정수가 된다. map의 구현은 아래와 같다.

 

          map f [] = []

          map f (x:xs) = f x : map f xs

 

함수 f는 리스트의 모든 요소에 재귀적으로 적용되며 리스트 통합 연산자 ‘:’를 적용하여 새로운 리스트를 생성한다.

문자열을 ASCII 리스트로 만드는 함수는 아래와 같이 작성할 수 있다.

 

          code :: String -> [Int]

          code x = map ord x

 

Hugs에서 정의된 파일을 불러온 후 새 함수를 테스트 해볼 수 있다.

 

          code “Hugs”

 

위 테스트의 결과는 아래와 같다.

 

          [72,117,103,115]

 

3.2.2 다각형의 면적 계산하기

다각형의 면적을 계산해야 한다고 가정해 보자. 다각형은 x좌표와 y좌표로 이루어진 지점들의 리스트이다. 가우스 공식에 의해 면적은 아래와 같이 계산된다.

 

               n

          2F = ∑ (xi – x(i+1))(yi + y(i+1))

               i=1

 

이제 면적을 계산하기 위해서는 리스트 함수를 사용할 필요가 있다. 먼저 다각형에 대해 정의를 내려보자. 이 경우 – 다각형은 - 지점의 리스트로 정의 될 수 있고 각 지점은 좌표의 쌍(pair)이 된다. 테스트를 위해 필요한 다각형은 아래와 같은 형식을 갖는다.(그리고 우리는 – 직관적으로 - 이 다각형의 넓이가 10000이라는 사실을 바로 알 수 있다.)

 

          p = [(100.0, 100.0), (100.0, 200.0), (200.0, 200.0), (200.0, 100.0)] :: [(Float, Float)]

 

함수 p는 우리가 만들 함수를 테스트하기 위해 간단한 다각형을 반환한다.(이 다각형의 넓이는 10000이 되어야 한다.)

먼저 우리는 리스트 함수를 적용할 수 있도록 우리의 리스트 구조를 조정하는 것에 대해 생각해 보아야 한다. 물론 마지막 단계에서는 부분적으로 계산된 결과를 합하고 둘로 나누게 될 것이다. foldl 함수는 리스트의 각 요소를 특정한 함수에 적용하고 시작 점으로 주어진 값을 사용한다. 우리는 요소들을 합하고자 하므로 ‘+’를 사용해야 한다. ‘+’는 인자들 사이에 (x+y)처럼 사용하는 것이 표준이므로 (+)처럼 사용할 수 있도록 함수를 다시 만들어야 한다. ‘(+) x y’는 ‘x + y’와 같다. 우리 함수의 시작 지점은 0이다. 따라서 함수는 아래처럼 작성될 수 있다.

 

          sum_parts :: [Float] -> Float

          sum_pars parts = (foldl (+) 0 parts) / 2

 

우리는 부분 면적 (xi – x(i+1))(yi + y(i+1))를 계산하는 방법을 찾아야 한다. 우리는 아래와 같은 네 개의 리스트를 가지려 한다.

 

list	contents
1	x1, x2, x3, x4
2	x2, x3, x4, x1
3	y1, y2, y3, y4
4	y2, y3, y4, y1

테이블 4. 결과 리스트

 

부분 합을 계산하려면 zipWith를 사용할 수 있다. 이 함수는 아래와 같이 정의될 수 있다. (나는 이미 정의된 함수와 이름이 충돌하는 것을 피하기 위해zipWith’라고 이름을 바꿨다.)

 

          zipWith’ :: (a -> a -> a) -> [a] -> [a] -> [a]

          zipWith’ _ [] _ = []

          zipWith’ _ _ [] = []

          zipWith’ f (a:as) (b:bs) = (f a b) : zipWith’ f as bs

 

첫 번째 줄은 함수의 타입을 정의한다. 함수는 두 리스트와 하나의 함수(리스트의 인자를 합하기 위해 사용되는)를 인자로 받는다. 다음 두 줄에 의해 만약 둘 중 하나의 리스트가 빈 리스트인 경우 재귀를 중단한다. 마지막 줄은 함수가 어떻게 동작하는지를 보여준다. 리스트의 첫 번째 요소를 받아 함수 f에 이 인자들을 적용한다. 그리고 그 결과는 결과 리스트의 요소가 된다.

우리의 남은 공식 부분을 보면 (xi – x(i+1))에 의해 첫 번째 지점의 x 좌표에서 두 번째 지점의 x 좌표를 빼도록 되어 있다. 만약 테이블 4에 있는 리스트를 사용한다면 첫 번째 리스트의 인자와 두 번째 리스트의 인자를 빼는 것이 된다. 따라서

 

          zipWith (-) list1 list2

 

위 구문을 이용해서 리스트의 전체 요소의 차를 구할 수 있다. 그러므로 완전한 공식은 아래와 같다.

 

          zipWith (*) (zipWith (-) list1 list2) (zipWith (+) list3 list4)

 

여기서 리스트를 생성하는 문제만 남은 것은 아니다. list1과 3은 다소 간단하다. 그것들은 어떤 지점에서의 x좌표와y좌표이다. 우리는 map과 다른 두 함수 fst와 snd함수를 리스트의 각 요소에 적용할 수 있다. fst는 pair를 인자로 받아 첫 번째 값을 반환한다. snd 역시 pair를 받아 두 번째 값을 반환한다. 만약 좌표 값이 (x, y) 순서로 주어진다면 우리는 리스트를 아래와 같이 얻을 수 있다.

 

          list1 poly = map fst poly

          list3 poly = map snd poly

 

여기서 poly는 다각형을 의미한다. 가우스 공식은 우리가 x와 y값을 바꾸더라도 동작하므로 주어진 다각형의 좌표가 (x, y)인지 (y, x)인지는 중요하지 않다.

다른 두 리스트는 약간 더 어렵다. 두 경우에서 리스트는 순환한다. 따라서 우리는 첫 번째 요소를 얻어서 그것을 리스트의 마지막 부분으로 옮겨야 한다. 이것은 아래와 같이 할 수 있다.

 

          moveback poly = tail poly ++ [head poly]

 

함수 head와 tail은 리스트를 첫 번째 요소(head)와 나머지 요소(tail)로 분리해 준다. 그리고 그 결과 자체도 리스트이다. 수식을 대괄호로 둘러싸면 그 수식의 요소를 리스트로 만들어 준다.[4] ‘++’함수는 두 리스트를 인자로 받아 첫 번째 리스트의 뒤에 두 번째 리스트를 연결한 리스트를 만들어 준다.

모든 부분을 합치면 최종 함수가 된다. 그리고 이 때 만약 3개 보다 적은 지점을 인자로 받으면(넓이를 구할 수 없으므로) 에러를 표시하는 구문 또한 만든다.

 

          area :: [(Float, Float)] -> Float

          area [] = error “not a polygon”

          area [x] = error “points do not have an area”

          area [x, y] = error “lines do not have an area”

          area ps = abs ((foldl (+) 0.0 parts) / 2) where

                        pars = zipWith (*) (zipWith (-) l1 l2) (zipWith (+) l3 l4)

                        l1 = map fst ps

                        l2 = tail l1 ++ [head l1]

                        l3 = map snd ps

                        l4 = tail l3 ++ [head l3]

 

3.3 다른 유용한 리스트 함수

3.2절에서 보았듯이 함수는 다른 함수를 인자로 받을 수 있다. 3.2.1절에서 사용한 map 함수가 그 한 예이다.

 

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

          map f [] = []

          map f (x : xs) = f x : map f xs

 

함수를 정의할 때는 우리가 사용할 타입을 정확하게 알 필요가 없다. 그러나 실행 시에는 두 타입을 모두 아는 것이 중요하다. 매개 변수 타입은 실행 시간에 알게 된다. (실행 시점이 되어야 명시적인 타입을 가진 데이터 값들을 가지고 작업하게 된다.)  그러나 결과 타입은 모호하지 않아도 된다. 이런 경우 우리는 ‘:: 결과 타입’ 을 추가하면 결과 값의 타입을 구체적으로 명시할 수 있다.

또 다른 중요한 리스트 함수로 filter 함수가 있다. 우리는 (이미 prelude 모듈에 정의되어 있는 함수와 이름이 충돌되는 것을 피하기 위해) 그것의 이름을 바꿔서 구현하도록 하겠다.

 

          filter2 :: (a -> Bool) -> [a] -> [a]

          filter2 f [] = []

          filter2 f (x : xs) = if f x       then x : filter2 f xs

                                                  else filter2 f xs

 

filter 함수는 두 개의 인자를 받는다. 첫 번째 인자는 함수(필터 조건)이고 두 번째 인자는 임의의 타입 a의 리스트이다. 필터 조건 함수는 리스트의 요소를 인자로 받아 Boolean 값을 반환한다. 만약 그 값이 참이면 그 요소는 결과 리스트에 남고 그렇지 않으면 결과 리스트로부터 제거된다.

 

3.4 2차 방정식의 리스트를 위한 근 구하기

2차 방정식의 리스트(2.3절의 예제처럼 3개의 정수 쌍을 저장하는)를 생각해 보자. 이 작업은 두 부분으로 나누어 진다. 우리는 모든 등식이 실수해가 되는 것을 보장해야 한다. 왜냐하면 만약 함수가 복소수 해를 생성하는 것은 오류이기 때문이다. 따라서 우리는 해가 실수이면 참을, 복소수이면 거짓을 반환하는 함수가 필요하다.

 

          real :: (Float, Float, Float) -> Bool

          real (a,b,c) = (b*b – 4*a*c) >= 0

 

우리는 정수 해를 가진 방정식을 여과하기 위한 함수를 아래와 같이 사용할 수 있다.

 

          p1 = (1.0, 2.0, 1.0) :: (Float, Float, Float)

          p2 = (1.0, 1.0, 1.0) :: (Float, Float, Float)

          ps = [p1, p2]

          newPs = filter real ps

          rootsOfPs = map roots newPs

 

ps 함수는 두 개의 2차 방정식을 가진 리스트를 반환한다. 첫 번째 방정식(p1)은 정수 해를 가졌고 p2는 복소수 해를 가졌다. newPs함수는 ps의 요소 중 정수 해를 가진 것을 여과하기 위해 real 함수를 사용한다. 최종적으로 rootsOfPs는 리스트의 각 방정식을 위해 roots함수를 사용한다. 그 결과는 방정식의 해의 리스트가 된다.

 

연습문제: 복소수 근을 계산하기 위한 함수(이전 장에서 연습문제로 제시했던)를 사용하여 2차 방정식의 리스트에 이 함수를 적용해 보라.

 

3.5 또 다른 함수 정의 방법

함수는 항상 다른 방법으로 정의할 수 있다. 보통 정의를 추상화하는 방법이나 사용되는 함수들에서 차이가 있다. 또한 특별한 경우를 처리하기 위해 다른 방식을 사용하기도 한다. 리스트의 길이를 계산하는 함수를 예로 들어 보자. 비록 형태는 다소 틀리지만 모두 같은 결과를 반환한다.  모든 경우에서 추상화는 같다. (모두 [a] 타입을 매개 변수로 받아 Int 형을 결과로 반환한다.)

 

          l1 [] = 0

          l1 (x:xs) = 1 + l1 xs

 

          l2 xs = if xs == [] then 0 else 1 + l2 (tail xs)

 

          l3 xs      | xs == [] = 0

                        | otherwise = 1 + l3 (tail xs)

 

          l4 = sum . map (const 1)

 

          l5 xs = foldl inc 0 xs

                        where inc x _ = x + 1

 

          l6 = foldl’ (\n _ -> n + 1) 0

 

리스트의 길이에서 빈 리스트는 특별한 경우이다. 이 경우 길이는 0이 된다. l1에서 l3까지의 함수들은 이 사실을 기반으로 하여 길이를 순환적으로 계산한다. 그러나 이 함수들은 빈 리스트를 확인하기 위해 서로 다른 방법을 사용한다.

 

n        l1은 패턴 매칭을 사용했다.

n        l2는if-then-else 분기구문을 사용했다.

n        l3는 가드(guard) 표기법을 사용했다.(6.2절에서 이것에 대해 보다 자세히 설명해 놓았다.)

 

l4부터 l6까지의 함수들은 계산 성능을 높이기 위해 또 다른 리스트 함수를 사용했다. 이 함수들은 아래와 같이 동작한다.

 

n        l4는 먼저 리스트의 모든 요소를 1로 바꾸고 단지 리스트 요소들의 합을 구했다.

n        l5는 지역 카운터를 증가시키기 위해 지역 함수를 정의하고 foldl 함수를 사용하여 리스트 전체에 그 함수를 적용했다.

n        l6는 l5와 같은 방법을 사용했지만 람다(lambda) 표현식[5]을 사용해서 함수를 정의했다.

 

3.6 요약

우리는 이 장에서 리스트에 대해 몇 가지를 발견했다. 가장 중요한 것들은 아래와 같다.

n        리스트는 같은 타입을 가진 임의의 개수의 요소들을 표현하기에 매우 적합한 방법이다.

n        prelude.hs 파일에는 리스트를 위한 많은 유용한 함수들이 있다.

n        고차 함수인 map은 리스트의 각 요소에 함수를 적용해 준다.

n        수학적 귀납법은 재귀를 위한 이론적 배경이 된다.

n        재귀는 절차형 프로그램의 루프 구문을 수학적인 방법으로 대체해 준다.

n        리스트는 자연수와 비슷한 형태를 가졌으며 같은 방식으로 재귀가 사용된다.

n        map, filter, foldl/foldr 함수는 리스트에 사용되는 가장 중요한 함수들이며 많은 어플리케이션에서 유용하게 사용된다.

n