EECS-101 전자계산입문 고차함수 박성우 2008년5월 29일 지금까지정수나부동소수와같은기본적인자료형의조합을인자로받고결과값으로반환하는 함수에대해서배웠다. 이번강의에서는함수자체를다른함수의인자로이용하거나결과값으로 이용하는 방법을 배운다. 1 고차함수의 의미 계산은무엇을어떻게처리하여결과값을얻는지설명하는것으로이루어진다. 여기서 무엇 과 결 과값 은계산의대상체로서정수나부동소수와같은기본자료형의조합으로표현하며, 어떻게 는 계산의중간과정으로서함수를이용하여표현한다. 사실기본적으로제공되는 +와 *와같은연산 자도내부적으로는함수로정의되어있기때문에모든계산의중간과정이함수로표현된다는것은 틀린설명이아니다. 이렇게함수는계산에서대상체를어떻게변환하고생성하는지를표현하는특 별한지위를가지며,정수나부동소수와같은기본자료형은계산의대상체로만이용되는보조적인 지위를 가진다. 정수와부동소수와같이함수의인자나결과값으로이용할수있는자료형을일종객체 first-class object 라 고부른다. 여기서 일종 이란특별한지위를가진다는뜻에서의일종이아니라 (특별한처리를요 하는특급우편물과는대조되는)편지나엽서와같은일종우편물처럼일반적인처리를요한다는뜻 에서의일종이다.즉정수나부동소수는함수간에전달되는일종우편물에비유하는것이다. 그러면함수자체를일종객체로이용할수있을까? 즉함수의인자로서함수를전달받고함수의 결과값으로함수를반환할수있을까? 대부분의프로그래밍언어는함수를일종객체로허용하지않 지만 OCAML의경우는허용한다. 따라서함수도일종객체의위치를가지게되고이러한의미에서 OCAML에서정의하는모든함수는일종함수 first-class function 라고말한다. 함수를인자나결과값으로이용하는함수를고차함수 higher-orderfunction 이라고한다. (기본자료 형만을인자와결과값으로이용하는함수는일차함수 first-order function 이라고한다. 지금까지다룬모 든함수는일차함수이다.) 고차함수는다음과같은세종류로나눌수있다. 가장일반적인형태의 고차함수는 세번째이다. 함수를인자로받고기본자료형만을결과값에이용하는고차함수 1
기본자료형만으로이루어진인자를받아서함수를결과값으로반환하는고차함수 기본자료형과함수를인자와결과값에모두이용하는고차함수 다음절에서는여러가지예를통해서고차함수가어떤경우에유용한지를설명한다. 2 고차함수의 예??장에서대상체만바뀌고중간과정은동일한계산이반복될때함수를이용하면전체연산식을간 단하게표현할수있음을배웠다. 마찬가지로이용하는함수만바뀌고중간과정은동일한계산이 반복될때고차함수를이용하면전체연산식을간단하게표현할수있다. 예를통해서고차함수가 실제로 어떻게 이용되는지 살펴보자. 2.1 함수를인자로받는고차함수 함수 f를받아서 0에적용한결과를반환하는고차함수를생각해보자. 모든함수는일종객체이므 로정수나부동소수형인자를이용할때와같은방식으로 f를형식인자로이용하면된다. let app zero f = f 0 몸통연산식에서 f는정수연산식 0에적용되므로 int타입을인자로받는모든함수에 app zero를 적용할수있다. 예를들어주어진정수를 1증가시키거나감소시키는함수 inc와 dec를가정하 자. let inc = fun x -> x + 1;; let dec = fun x -> x - 1;; app zero를 inc과 dec에적용하면각각 inc 0과 dec 0을계산한다. # app zero inc;; - : int = 1 # app zero dec;; - : int = -1 조금더복잡한예로서함수 f를받아서 0에두번적용한결과를반환하는고차함수를정의해보 자. # let app twice zero f = f (f 0);; val app twice zero : (int -> int) -> int = <fun> app twice zero의 타입 (int -> int) -> int를 그대로 해석하면 int -> int 타입 의값을받아서 int타입의값을반환함을의미한다. 그런데 int -> int타입의값은사실 int -> int타입을가지는함수이다. 따라서 app twice zero의타입은 int -> int타입 의함수를받아서정수를반환함을나타낸다. app twice zero를 inc과 dec에적용하면각각 inc (inc 0)과 dec (dec 0)을 계산한다. 2
# app twice zero inc;; - : int = 2 # app twice zero dec;; - : int = -2 함수 f를받아서0에세번적용한결과를반환하는고차함수도유사하게정의할수있다. # let app thrice zero f = f (f (f 0));; val app thrice zero : (int -> int) -> int = <fun> # app thrice zero inc;; - : int = 3 # app thrice zero dec;; - : int = -3 위의 함수들을 일반화하면 함수 f를 받아서 0에 n번 적용한 결과를 반환하는 고차함수 app times zero를자기호출함수형태로정의할수있다. # let rec app times zero f n = if n = 0 then 0 else f (app times zero f (n - 1));; val app times zero : (int -> int) -> int -> int = <fun> 만약 n = 0이면 f는 0번적용되므로 (즉한번도적용되지않으므로)결과값은 0이된다. 그렇 지않으면 f를 0에 (n 1)번적용한결과에다시한번더 f를적용하여총 n번을적용하게된다. app times zero는다음과같이이용할수있다. # app times zero inc 10;; - : int = 10 # app times zero dec 10;; - : int = -10 2.2 함수를결과값으로반환하는고차함수 함수를결과값으로반환하기위해서는 fun키워드를이용하여만든연산식이함수를나타내는하 나의값이라는점을이해하면된다.예를들어 inc의정의를살펴보자. let inc = fun x -> x + 1 이정의를그대로해석하면연산식 fun x -> x + 1의계산결과가변수 inc에저장됨을알수 있다. 그런데 fun x -> x + 1은그자체가이미하나의값으로서주어진정수를 1증가시키는 함수를나타낸다. 따라서이정의는실질적으로주어진정수를 1증가시키는함수 inc를생성하는 것으로 해석되는 것이다. 3
fun키워드를이용하여함수를생성할때다른지역변수나인자를이용할수있다. 예를들면 다음함수는인자로정수 n이주어졌을때주어진정수를 n증가시키는새로운함수를반환한다. # let incr n n = fun x -> x + n;; val incr n : int -> int -> int = <fun> 따라서 incr n 10은주어진정수를 10증가시키는함수가되고 incr n (-10)은주어진정수를 10감소시키는함수가된다. # (incr n 10) 0;; - : int = 10 # (incr n (-10)) 0;; - : int = -10 함수 incr n은 정수를 받아서 int -> int 타입의 함수를 반환하므로 int -> (int -> int) 타입을가지게된다. 그런데위의실행예에서는타입이 int -> int -> int로출력되고있는 데 이는 int -> int -> int와 int -> (int -> int)는 완전히 동등한 타입임을 의미한 다.설명을돕기위해서 incr n과비슷한함수 incr n 을생각해보자. # let incr n n x = x + n;; val incr n : int -> int -> int = <fun> incr n 은정수 n과 x를인자로받아서 x + n을결과값으로반환하므로 int -> int -> int 타입을가진다. 중요한점은이두개의함수 incr n과 incr n 이완전히동등하다는점이다. 즉 다음과같이 incr n을 incr n 으로해석해도되고반대로 incr n 을 incr n으로해석해도된 다. (??장에서소개한키워드 fun을이용하지않는함수정의방식도같은원리를이용하고있다.) incr n은 incr n 과동등하므로 incr n 10 0의계산결과는10이다. incr n 은 incr n과동등하므로 incr n 10의계산결과는주어진정수를 10증가시키 는함수가된다. # incr n 10 0;; - : int = 10 # incr n 10;; - : int -> int = <fun> 이원리를이용하면함수를결과값으로반환하는고차함수를여러가지형태로작성할수있다. 예를들면정수 a와 b를인자로받아서함수 f(x) = ax + b를반환하는고차함수 linear는다음과 같이여러가지형태로작성할수있다. 4
let linear a b x = a * x + b;; let linear a b = fun x -> a * x + b;; let linear a = fun b x -> a * x + b;; let linear a = fun b -> fun x -> a * x + b;; let linear = fun a -> fun b -> fun x -> a * x + b;; let linear = fun a b x -> a * x + b;; 이원리를일반화하면다음두타입은완전히동등하다는결론을얻게된다. T 1 -> T 2 -> -> T n 1 -> T n T 1 -> (T 2 -> -> (T n 1 -> T n ) ) 2.3 함수를인자로받고결과값으로반환하는고차함수 세번째형태의고차함수는위에서살펴본고차함수형태들을일반화시킨경우이다. 예로서함수 f와 g를받아서새로운함수 h(x) = f(x) + g(x)를생성하는고차함수 combine은다음과같이작 성할수있다. let combine f g = let h x = f x + g x in h 만약임시로 h라는함수를생성하지않고바로최종결과값을반환하고자하면다음과같이작성하 면된다. let combine f g = fun x -> f x + g x 이정의는2.2절에서설명한원리를이용하여다음과같이간단하게만들수있다. let combine f g x = f x + g x 다음예는 combine을이용하여새로운함수를만든뒤 0에적용하는예이다. # let h = combine (fun x -> x + 1) (fun y -> y - 1) in h 0;; - : int = 0 여기서 함수 fun x -> x + 1과 fun y -> y - 1이 정수와 부동소수처럼 값으로 취급되고 있음을볼수있다. 다른예로서함수 f와 g를받아서합성 composition 함수 g f를반환하는고차함수 compose는 다음과같이작성할수있다. let comp f g = fun x -> g (f x) 이정의는다음과같이간단하게만들수있다. let comp f g x = g (f x) 5
3 타입변수와 다형함수 고차함수를작성하다보면함수의타입을정확하게결정할수없는상황이종종발생한다. 예를들 어 2.3절에서 정의한 combine을 생각해보자. let combine f g = fun x -> f x + g x 연산식 f x + g x로부터다음과같은두가지사실을추론할수있다. 함수적용 f x와 g x는실제인자 x를공유하므로함수 f와 g의형식인자타입은동일하다. 함수 f와 g는모두 int타입의값을반환한다. 따라서 combine은구체적으로결정할수없는타입 T에대해서 (T -> int) -> (T -> int) -> (T -> int) 타입을가진다고결론을내릴수있다. 여기서중요한점은타입 T는사실아무타입이나될수있 다는사실이다. 예를들어 T = int로해석하여 int -> int타입의함수들을인자로이용할수 있고 T = bool로해석하여 bool -> int타입의함수들을인자로이용할수있다. # combine (fun x -> x + 1) (fun y -> y - 1);; - : int -> int = <fun> # combine (fun x -> if x then 1 else 0) (fun y -> if y then 0 else 1);; - : bool -> int = <fun> OCAML에서는 T와같이구체적으로결정할수없는타입을타입변수 typevariable 라고부르며 a, b, c등의형태로표시한다. 예를들어 combine의타입을표시할때타입변수 a를이용할수 있다. # let combine f g = fun x -> f x + g x;; val combine : ( a -> int) -> ( a -> int) -> a -> int = <fun> 보통 a가포함된타입은 아무타입 a에대해서 라는선언이내포되어있다고생각하면된다. 따라서 combine의타입은다음과같이해석할수있다. 아무타입 a에대해서 a -> int타입의함수두개를받아서 a -> int타입의함수를 반환한다. 타입에타입변수가포함된함수는다형함수 polymorphicfunction 이라고부른다. 연산식의타입에는여러개의타입변수가이용될수있다. 예를들어다음함수 pair의타입에 는두개의타입변수 a와 b가이용되고있다. # let pair x y = (x, y);; val pair : a -> b -> a * b = <fun> 6
여기서인자 x와 y가서로다른타입변수를가지는이유는아무런관계가없는두인자는같은타입 을가질필요가없기때문이다. 예를들면 x가 int타입을가질때 y는똑같이 int타입을가져도 되지만 bool타입을가져도되는것이다. # pair 0 0;; - : int * int = (0, 0) # pair 0 true;; - : int * bool = (0, true) pair의타입은다음과같이해석할수있다. 아무타입 a와 b에대해서 a타입의인자와 b타입의인자를받아서 a * b타입의 튜플을 반환한다. 7