[함수형언어] 5주차 수업 내용 정리

05.09 5주차 수업 내용 정리

다양한 재귀함수

문제 1: 정수의 리스트를 파라미터로 받아, 그 접두어의 리스트를 반환하는 함수 prefix를 정의하라.

• 접두어: 리스트의 첫 요소로부터 적당한 길이의 리스트
• 단, 빈 리스트 []는 접두어에 포함되지 않음

(* prefix: int list -> (int list) list *)
let test1 = prefix [1; 2; 3; 4] = [[1], [1; 2], [1; 2; 3], [1; 2; 3; 4]]
let test2 = prefix [] = []
let test 3 = prefix [1] = [[1]]

let rec prefix lst = match lst with
	[] -> []
	| first :: rest -> [first] :: add_to_each first (prefix rest) 
	
(* 파라미터로 받은 리스트 각각의 요소에 새로운 요소를 가져다 붙이는 함수 add_to_first를 새로 정의 *)
let rec add_to_each n lst = match lst with
	[] -> []
	| first :: rest -> (n :: first) :: add_to_each n rest

문제 2: 리스트에서 최소값을 찾아 반환하라.

귀소변수 정의

• let 변수 = 식 1 in 식 2: 식 1을 실행해서, 그 결과에 변수라는 일시적인 이름을 붙임 -> 그 뒤 식 2를 실행하는데, 이때 변수를 사용하는 것이 가능

let rec minimum lst = match lst with
	[] -> max_int
	| first :: rest -> 
		let min_rest = minimum rest in
		if first <= min_rest
		then first
		else min_rest

문제 3: gakusei_t 형의 레코드를 받아, 그 안에서 A, B, C, D 성적을 받은 사람이 각각 몇 명인지 계산하라.

• 패턴 매치와 국소변수정의

let rec shukei lst = match lst with
	[] -> (0, 0, 0, 0)
	| {namae = n; tensuu = t; seiseki = s} :: rest ->
	let (a, b, c, d) = shukei rest in
	if s = "A" then (a + 1, b, c, d)
	else if s = "B" then (a, b + 1, c, d)
	else if s = "C" then (a, b, c + 1, d)
	else (a, b, c, d + 1)

문제 4: 두 개의 리스트를 결합하는 함수를 작성하라.

let rec append lst1 lst2 = match lst1 with
	[] -> lst2
	| first :: rest 
		-> first :: append rest lst2

문제 5: 두 개의 오름차순으로 정렬된 리스트를 병합 정렬하는 함수를 작성하라.

let rec merge lst1 lst2 = match (lst1, lst2) with
	(* 두 리스트가 모두 비어 있다면 빈 리스트 반환 *)
	([], []) -> []
	(* lst1이 비어 있고 lst2에 값이 있다면 lst2 자체를 반환 *)
	| ([], first2 :: rest2) -> lst2
	(* lst2가 비어 있고 lst1에 값이 있다면 lst1 자체를 반환 *)
	| (first1 :: rest1, []) -> lst1
	(* 두 리스트에 모두 요소가 있다면, 두 리스트의 첫 요소를 비교 *)
	(* 더 작은 값을 선택하고 그 값을 결과 리스트의 머리로 삼음 *)
	(* 그 값을 선택한 쪽 리스트는 나머지(rest)로 재귀 호출 *)
	| (first1 :: rest1, first2 :: rest2) ->
		if first1 < first2
		then first1 :: merge rest1 lst2
		else first2 :: merge lst1 rest2