CIDA Lab @ UoS

과제 1. OCaml에 익숙해지기

   

  • 제출기한 : 3월 30일 월요일 11:59pm
  • 주의: 반복문(loop) 없이 순수 재귀 함수(recursive function)로만 문제를 해결하세요.

   

제출 방법

제출 방법: 아래 두 가지 파일을 하나의 압축 파일(학번_hw1.zip)로 묶어 Uclass 과제 게시판에 업로드해주세요. 코드 파일만 제출하거나 실행 화면이 누락된 경우 감점될 수 있습니다.

  1. 코드 파일 — 작성한 코드를 hw1.ml로 저장합니다.
  2. 실행 화면 캡처 — utop 또는 터미널에서 각 문제의 함수를 직접 실행한 결과 화면을 캡처하여 hw1_screenshot.png (또는 .jpg)로 저장합니다.
    • 캡처 화면에는 각 문제의 함수 이름과 예시 입력·출력이 모두 보여야 합니다.
    • 예시: ```ocaml # last [“a”; “b”; “c”; “d”];;
      • : string option = Some “d” # gcd 48 18;;
      • : int = 6 ```

   

과제 진행 시 어려운 점이 있으면 온라인 강의실 게시판을 이용해 질문하세요. 게시판을 통해 하기 어려운 질문이라면 아래 TA 이메일을 통해 문의하시기 바랍니다.

  • TA 이메일: seongminkim16@gmail.com

   

패턴 매칭(Pattern Matching)에 익숙해지기

패턴 매칭(pattern matching)을 활용하여 리스트(list)를 다루는 기본 함수들을 구현합니다. 각 문제는 match ... with 구문을 사용하여 빈 리스트([])와 원소가 있는 리스트(h :: t) 두 경우를 분리해서 처리하는 방식으로 풀 수 있습니다.

1. 리스트의 마지막 원소 (Tail of a List)

리스트(list)의 마지막 원소(element)를 반환하는 함수를 구현하세요. 함수의 타입(type)은 'a list -> 'a option이 되어야 합니다.

리스트가 비어 있을 때는 마지막 원소가 존재하지 않으므로 None을, 원소가 하나 이상 있을 때는 마지막 원소를 Some으로 감싸서 반환합니다.

## last ["a" ; "b" ; "c" ; "d"];;
- : string option = Some "d"
## last [];;
- : 'a option = None

2. 리스트의 마지막 두 원소 (Last Two Elements of a List)

리스트(list)의 마지막 두 원소(element)를 튜플(tuple)로 묶어 반환하는 함수를 구현하세요. 원소가 두 개 미만이면 None을 반환합니다.

## last_two ["a"; "b"; "c"; "d"];;
- : (string * string) option = Some ("c", "d")
## last_two ["a"];;
- : (string * string) option = None

3. 리스트의 N번째 원소 (N’th Element of a List)

리스트(list)에서 N번째 원소(element)를 반환하는 함수를 구현하세요. 0부터 시작하는 인덱스(0-index)를 사용합니다. 즉, 첫 번째 원소의 인덱스(index)는 0, 두 번째 원소의 인덱스는 1입니다. 인덱스가 범위를 벗어나면 None을 반환합니다.

## at 2 ["a"; "b"; "c"; "d"; "e"];;
- : string option = Some "c"
## at 2 ["a"];;
- : string option = None

힌트: let rec at position = function 형태로 시작하면 마지막 인자에 대해 바로 패턴 매칭을 적용할 수 있습니다.

4. 리스트의 길이 (Length of a List)

리스트(list)의 원소(element) 수를 반환하는 함수를 구현하세요.

## length ["a"; "b"; "c"];;
- : int = 3
## length [];;
- : int = 0

심화: 꼬리 재귀(tail recursion) 방식으로 구현할 수 있나요? 누산기(accumulator) 인자를 추가해서 시도해 보세요.

5. 리스트 뒤집기 (Reverse a List)

리스트(list)를 역순으로 뒤집은 새 리스트를 반환하는 함수를 구현하세요.

## rev ["a"; "b"; "c"];;
- : string list = ["c"; "b"; "a"]

6. 팰린드롬 판별 (Palindrome)

리스트(list)가 팰린드롬(palindrome)인지 확인하는 함수를 구현하세요. 팰린드롬이란 순서를 앞에서 읽으나 뒤에서 읽으나 동일한 배열을 말합니다 (예: ["x"; "a"; "m"; "a"; "x"]).

## is_palindrome ["x"; "a"; "m"; "a"; "x"];;
- : bool = true
## not (is_palindrome ["a"; "b"]);;
- : bool = true

힌트: 위에서 구현한 rev 함수를 활용하세요. 원래 리스트와 뒤집은 리스트가 같은지 비교하면 됩니다.

   

재귀(Recursion)와 꼬리 재귀(Tail Recursion)에 익숙해지기

꼬리 재귀(tail recursion)는 재귀 호출이 함수의 마지막 연산이 되도록 작성하는 방식입니다. 결과를 누산기(accumulator) 인자에 축적해 나가는 방식으로 구현하면, OCaml 컴파일러가 꼬리 호출 최적화(tail call optimization)를 적용하여 스택 오버플로(stack overflow) 없이 큰 입력도 처리할 수 있습니다.

아래 문제들을 꼬리 재귀(tail recursion) 방식으로 구현합니다.

7. 최대공약수 구하기 (GCD)

두 정수 a, b의 최대공약수(GCD, Greatest Common Divisor)를 구하는 함수를 구현하세요. 유클리드 호제법을 사용합니다: gcd(a, b) = gcd(b, a mod b)이며, b = 0일 때 a가 최대공약수입니다. 재귀 호출이 마지막 연산이므로 자연스럽게 꼬리 재귀(tail recursion)가 됩니다.

## gcd 48 18;;
- : int = 6

8. 팩토리얼 (Factorial)

자연수 n에 대해 n! (팩토리얼, factorial)을 계산하는 함수를 구현하세요. 누산기(accumulator) 인자를 활용하여 꼬리 재귀(tail recursion) 방식으로 구현합니다.

## factorial 5;;
- : int = 120

   

변형 타입(Variant)과 튜플(Tuple)에 익숙해지기

9. 변형 타입 (Variant)

요일을 나타내는 타입(type)을 정의하고, 주어진 요일의 다음 요일을 반환하는 함수를 구현하세요. 변형 타입(variant)은 type day = Sun | Mon | ... 형태로 정의하며, 패턴 매칭(pattern matching)으로 각 경우를 처리합니다.

## get_next_day Sun;;
- : day = Mon

10. 튜플 뒤집기 (Tuple Swap)

튜플(tuple)의 두 원소 순서를 맞바꿔 반환하는 다형 함수(polymorphic function)를 작성하세요. 타입 변수(type variable) 'a, 'b를 사용하면 어떤 타입의 튜플에도 적용할 수 있습니다.

## swap (3, 2);;
- : int * int = (2, 3)
## swap ("first", "second");;
- : string * string = ("second", "first")
Search