어떻게 코딩할 것인가-데이터 설계

Dec 28, 2022

1. 데이터 정의(Data Definition)란?
2. 데이터 종류 별 설계 과정
   • 원자 데이터(Atomic)
   • 범위 데이터(Interval)
   • 열거형 데이터(Enumeration)
   • 항목형 데이터(Itemization)
   • 복합 데이터(Compound data)
   • List 데이터(List data)
   • 참조 관계 데이터

데이터 설계

🗣️ quote

Edx 강의 How to Code 보안 확인 : 외부링크
"https://learning.edx.org/cours..."로 ? 시리즈를 정리한 내용입니다.

데이터 설계는 함수 설계보다 프로그램에 직접적인 영향을 끼치진 않지만, 함수 설계에 크나큰 영향을 끼친다.

• 함수는 데이터를 다루는 방법이기 때문

데이터는 사람이 이해 가능한 문제 영역의 정보(problem domain information)를 프로그램이 이해 가능하게 표현(represent)한 것이다.

이러한 데이터는 개발자가 보았을 때, 다시 문제 영역의 정보로 해석(interpret)할 수 있어야 한다.

• 예를 들어, enum = {1, 2, 3}은 데이터이며, 사람이 이해하는 apple, orange, strawberry는 문제 영역 정보이다. 1은 데이터이며, apple의 표현이며, apple이라는 문제 영역 정보로 해석할 수 있다.

정보의 구조는 데이터의 구조를 정하며, 데이터의 구조는 템플릿의 구조를 정하고 템플릿의 구조는 함수의 구조를 정하고, 이러한 함수가 모여 전체 프로그램을 설계하므로 중요하다.

데이터 정의(Data Definition)란?

데이터 정의는 정보와 데이터의 표현/해석 관계를 수립하는 것이다. 다음과 같은 내용을 정해야 한다.

• 데이터가 새로운 타입으로 어떻게 대치되는가?
• 정보를 어떻게 데이터로 표현하고, 데이터를 어떻게 정보로 해석하는가?
• 데이터를 다루기 위한 템플릿

🧾️ 데이터 정의 예시

# Data definitions:
{: #data-definitions}
# TLColor is one of:
{: #tlcolor-is-one-of}
#  - 0
{: #0}
#  - 1
{: #1}
#  - 2
{: #2}
# interp. 0 means red, 1 yellow, 2 green               
{: #interp-0-means-red-1-yellow-2-green}
def FnForTlcolor(c):
	if c == 0:
		pass
	elif c == 1:
		pass
	elif c == 2:
		pass

데이터 정의를 통해 함수 설계에 다음과 같은 영향을 끼친다.

• 데이터 입력과 출력 도메인을 제한
• 테스트를 만드는데 도움을 줄 수 있음
• 템플릿을 만드는데 도움을 줄 수 있음

🧾️ 데이터 정의에 도움을 받은 함수 디자인

# Function Design:
{: #function-design}
# Signature: TLColor -> TLColor
{: #signature-tlcolor-tlcolor}
# Purpose: produce next color of traffic light
{: #purpose-produce-next-color-of-traffic-light}
# Stub : def nextColor_stub(c): return 0
{: #stub-def-nextcolor-stub-c-return-0}

# Tests 
{: #tests}# 테스트를 만드는데 도움을 줄 수 있음, 데이터 입력과 출력 도메인을 제한을 통해 테스트 생성
print(nextColor(0) == 2)
print(nextColor(1) == 0)
print(nextColor(2) == 1)
# Template from TLColor 
{: #template-from-tlcolor}# 템플릿을 만드는데 도움을 줄 수 있음
# function
{: #function}
def nextColor(c):
	if c == 0:
		return 2
	elif c == 1:
		return 0
	elif c == 2:
		return 1

데이터 종류 별 설계 과정

데이터의 종류에 따른 여러 설계 방법과 함수 설계의 예시를 알아보자.

• 예시에서는 하나의 데이터 설계에 하나의 함수 설계가 대치되므로 매우 비효율적이게 보이겠지만, 실제로는 하나의 데이터 설계 이후 여러 함수가 공유하므로 훨씬 낫다.

데이터의 종류에 따라 정의한 결과물들을 이용해 함수 설계를 하므로, 데이터 별 정의는 함수 설계에 직교성을 가진다.

• 쉽게 말해 사용하는 데이터에 따라 함수 설계 방법이 크게 바뀐다는 의미

여기서 배운 데이터 종류는 하나 이상의 성질을 동시에 가지거나 여러 종류의 인자들이 함수 설계시 필요할 수 있는데, 이럴 때는 여기서의 데이터 템플릿을 잘 섞으면 된다.

모든 설계 과정은 다음과 같은 공통 과정을 거친다.

1. 정보의 내재 구조 파악
   • 데이터를 어떤 타입으로 표현해야할 것인가? ex) atomic, Interval, Itemization
2. 가능한 구조 정의(복합 데이터의 경우에만 시행)
3. 데이터 타입 정의
   • 타입명과 데이터의 구성 방법을 기술
4. 정보와 데이터 간의 상호 해석/표현 방법 정의
5. 데이터에 대한 예시들 기술
6. 데이터를 해석/표현하는 하나의 인자를 가진 함수 템플릿 정의
   • 함수의 템플릿을 만드는데 지대한 영향을 끼침
   • 템플릿을 이용해서 꼭 테스트해서 오류를 조기에 찾아내자
   • Data Driven Template 보안 확인 : 외부링크
     "https://courses.edx.org/course..."로 ? 을 참조하여 구현한다.

✍ Data Driven Template(DDT)

Type of data	cond question (if applicable)	Body or cond answer (if applicable)
Atomic Non-Distinct Number String Boolean Image interval like Number[0, 10) etc.	Appropriate predicate type(x)==int type(x)==str type(x)== type(True) type(x)==Image (and (<= 0 x)      (< x 10)) etc.	Expression that operates on the parameter. (... x)
Atomic Distinct Value "red" false empty etc.	Appropriate predicate x=="red" x==false len(x)==0 etc.	Since value is distinct, parameter does not appear. (...)
One Of enumerations itemizations		Cond with one clause per subclass of one of. (cond [<question1> <answer1>]       [<question2> <answer2>]) Where each question and answer expression is formed by following the rule in the question or answer column of this table for the corresponding case. A detailed derivation of a template for a one-of type appears below. It is permissible to use else for the last question for itemizations and large enumerations. Normal enumerations should not use else. Note that in a mixed data itemization, such as ;; Measurement is one of: ;; - Number[-10, 0) ;; - true ;; - Number(0, 10] the cond questions must be guarded with an appropriate type predicate. In particular, the first cond question for Measurement must be (and (number? m)      (<= -10 m)      (< m 0)) where the call to number? guards the calls to <= and <. This will protect <= and < from ever receiving true as an argument.
Compound Position Firework Ball cons etc.	Predicate from structure (posn? x) (firework? x) (ball? x) (cons? x) (often just else) etc.	All selectors. (... (posn-x x) (posn-y x)) (... (firework-y x) (firework-color x)) (... (ball-x x) (ball-dx x)) (... (first x) (rest x)) etc. Then consider the result type of each selector call and wrap the accessor expression appropriately using the table with that type. So for example, if after adding all the selectors you have: (... (game-ball g) ;produces Ball      (game-paddle g)) ;produces Paddle Then, because both Ball and Paddle are non-primitive types (types that you yourself defined in a data definition) the reference rule (immediately below) says that you should add calls to those types' template functions as follows: (... (fn-for-ball (game-ball g))      (fn-for-paddle (game-paddle g)))
Other Non-Primitive Type Reference	Predicate, usually from structure definition (firework? x) (person? x)	Call to other type's template function (fn-for-firework x) (fn-for-person x)
Self Reference		Form natural recursion with call to this type's template function: (fn-for-los (rest los))
Mutual Reference Note: form and group all templates in mutual reference cycle together.		Call to other type's template function: (fn-for-lod (dir-subdirs d) (fn-for-dir (first lod))

• 데이터 템플릿 내부의 비교 구문과 로직 구현 부분을 참조하여 넣으면 된다.

원자 데이터(Atomic)

더 이상 의미를 나눌 수 없는 데이터에 적용하며 기본 내장된 원시 타입들을 이용해 만드는 비원시 타입 데이터이다.

• 예를 들어 Vancouver, Boston, Homead는 각기의 의미를 가지고 있으며 추가로 나누는 것이 불가능하며 원시 타입인 String을 이용해 만들었다.

🧾️ 원자 데이터 정의 예시

# Vancouver, Boston, Homead 같은 도시명들을 원자형으로 표현하고자 한다. 
{: #vancouver-boston-homead-같은-도시명들을-원자형으로-표현하고자-한다}# 1. 정보 내재 구조 파악

# CityName is String 
{: #cityname-is-string}# 3. 데이터 타입 정의
# interp. the name of a city 
{: #interp-the-name-of-a-city}# 4. 해석/표현 방법 정의           

# 5. 데이터에 대한 예시 기술
{: #5-데이터에-대한-예시-기술}
CT1 = "Vancouver"
CT2 = "Boston"

#6. 데이터를 해석/표현하는 함수 템플릿 정의
# def fnForCityname(cn):
{: #def-fnforcityname-cn}
#	# ...cn
#	pass

# Template rules used: 
{: #template-rules-used}# Data Driven Template을 참조하여 정의한다.
# - Atomic non-distinct: String 
{: #atomic-non-distinct-string}# 우리는 CityName을 Atomic non-distinct라고 정의함.

• 함수 템플릿 내의 ...은 만약 데이터가 구분형(distinct)이라면 ...으로 충분하고, 비구분형(non-distinct)라면 ...n 같이 명시해줘야 한다. 구분형에서는 해당하는 조건문 블락에 들어가면 해당 데이터를 더이상 안쓰기 때문이다.

🧾️ 원자 데이터 정의를 사용한 함수 정의 예시

# 최고의 도시의 이름일 경우 참을 돌려주는 함수 만들기
{: #최고의-도시의-이름일-경우-참을-돌려주는-함수-만들기}
# Signature: CityName -> Boolean
{: #signature-cityname-boolean}
# Purpose: produce true if the given city is the best in the world(Karazakarak).
{: #purpose-produce-true-if-the-given-city-is-the-best-in-the-world-karazakarak}
# Stub: 
{: #stub}
def isBestCity_stub(cn):
	return false

# Tests: 특별 케이스, 결과 데이터, 입력 데이터를 고려하여 설정
{: #tests-특별-케이스-결과-데이터-입력-데이터를-고려하여-설정}
print(isBestCity_stub("Skavenblight") == False)
print(isBestCity_stub("Karazakarak") == True)

# Template: CityName 데이터 설계시 만든 템플릿 함수를 개명하여 사용 
{: #template-cityname-데이터-설계시-만든-템플릿-함수를-개명하여-사용}
# def isBestCity(cn):
{: #def-isbestcity-cn}
#	# ...cn
#	pass

# Function
{: #function}
def isBestCity(cn):
	return cn == "Karazakarak" #...cn 부분이 cn을 이용한다는 점에서 힌트를 얻어 만든 함수 	

• 함수 구현 시, 데이터 정의 템플릿을 활용할 때 무조건 데이터 템플릿의 모든 부분을 활용할 필요는 없다.

범위 데이터(Interval)

특정한 범위가 존재하는 데이터를 명시하는데 사용, 나중에 등장할 [[#항목형 데이터(Itemization)|항목형 데이터]]에 부분 데이터로 등장하는 경우가 많다.

🧾️ 범위 데이터 정의 예시: 1~32번까지 존재하는 영화 좌석 번호를 표시할 데이터

# 1. type comment : interval
{: #1-type-comment-interval}
# SeatNum is Integer[1, 32] 
{: #seatnum-is-integer-1-32}
# interp. seat numbers in a row, 1 and 32 are aisle seats
{: #interp-seat-numbers-in-a-row-1-and-32-are-aisle-seats}

# data examples 
{: #data-examples}# 주로 범위의 처음과 끝, 중간과 특수한 부분을 테스트
SN1 = 1 # aisle
SN2 = 12 # middle
SN3 = 32 # aisle

# data template
{: #data-template}
def fNForSeatNum(sn):
	#(... sn)
	pass
# Template rules used: at Data Drive Templates page
{: #template-rules-used-at-data-drive-templates-page}
# - atomic non-distinct: Integer[1, 32]
{: #atomic-non-distinct-integer-1-32}

• ”[” : 해당 값 포함(이상, 이하), “(” : 해당 값 미포함(미만, 초과) ex) [1, 32) = 1~31

🧾️ 범위 데이터 함수 예시: 끝단에 있는 영화 좌석 여부를 알려주는 함수

# Functions:
{: #functions}

# Signature: SeatNum -> Boolean
{: #signature-seatnum-boolean}
# Purpose: produce true if the given seat number is on the aisle
{: #purpose-produce-true-if-the-given-seat-number-is-on-the-aisle}
# tests
{: #tests}
print(isAisle(1)==True)
print(isAisle(16)==False)
print(isAisle(32)==True)

# def isAisle(sn) return false 
{: #def-isaisle-sn-return-false}#stub

# <use template from SeatNum> 
{: #use-template-from-seatnum}# 범위 데이터에서 정의한 템플릿 사용

def isAisle(sn)
	return sn == 1 or sn == 32

• 함수 테스트 작성 시, 범위의 극단값들과 중간 값, 특수 값 등을 고려하고 작성하자.

열거형 데이터(Enumeration)

구분되는 유한 개의 항목으로 표현할 수 있는 데이터, 숫자, 이미지, 문자 등으로 나타낼 수 있다.

• ex) 요일, 성별 등, 원자 데이터와 달리 들어올 데이터가 예상 가능한 표현 내에 있다.

🧾️ 열거형 데이터 정의 예시: 학생의 시험 점수 표시 데이터(A, B, C)

# A, B, C => consists of a fixed number of disinct items 
{: #a-b-c-consists-of-a-fixed-number-of-disinct-items}
# 2.type comment : enumeration
{: #2-type-comment-enumeration}
# LetterGrade is one of:
{: #lettergrade-is-one-of}
# - "A" 
{: #a}
# - "B" 
{: #b}
# - "C" 
{: #c}
# 3.interp. the letter grade in a course
{: #3-interp-the-letter-grade-in-a-course}
# <examples are redundant for enumerations> 4. 예시, 보통 열거형 데이터 전부를 집어넣어 보므로 생략
{: #examples-are-redundant-for-enumerations-4-예시-보통-열거형-데이터-전부를-집어넣어-보므로-생략}
# def fNForLetterGrade(lg): 5. Template for data
{: #def-fnforlettergrade-lg-5-template-for-data}
#	 if Q:
#		A
#    elif Q:
{: #elif-q}
#		A
#    else:
{: #else}
#		A
# if Q A를 DDT를 참고하여 아래처럼 바꿔주면 된다.        
{: #if-q-a를-ddt를-참고하여-아래처럼-바꿔주면-된다}
def fNForLetterGrade(lg): # 5-2. Template for data after Data Driven Table
	if lg == "A":
		# ...
		pass
	elif lg == "B":
		# ...
		pass
	else:
		# ...
		pass
# Template rules used:
{: #template-rules-used}
# - one of: 3 cases
{: #one-of-3-cases}
# - atomic distinct value: "A"
{: #atomic-distinct-value-a}
# - atomic distinct value: "B"
{: #atomic-distinct-value-b}
# - atomic distinct value: "C"
{: #atomic-distinct-value-c}

🧾️ 열거형 데이터 함수 예시: 학생의 시험 점수 한 단계 올려주기 함수

# Functions:
{: #functions}
# Signature: LetterGrade -> LetterGrade
{: #signature-lettergrade-lettergrade}
# Purpose: produce next highest letter grade (no change for A)
{: #purpose-produce-next-highest-letter-grade-no-change-for-a}

# def bumpUp(lg): return "A" 
{: #def-bumpup-lg-return-a}#stub
# 테스트 갯수는 열거형 항목 갯수 만큼
{: #테스트-갯수는-열거형-항목-갯수-만큼}
print(bumpUp("A")=="A")
print(bumpUp("B")=="A")
print(bumpUp("C")=="B")

#<use template from LetterGrade>

def bumpUp(lg):
	if (lg == "A"):
		return "A"
	elif (lg == "B"):
		return "A"
    elif (lg == "C")
	    return "B"

• 열거형의 경우 항목 수 이상 만큼 테스트를 하는게 이상적이다.
  • 항목 수 보다 많은 경우 :
  • 하지만, 일정 항목만 테스트 해도 코드의 모든 부분을 커버할 수 있다면 적게하는 경우도 있다.(Whitebox Test)

항목형 데이터(Itemization)

일부 데이터가 구분되는 데이터가 아닌 다른 부차적 데이터로 이루어진 데이터

🧾️ 항목형 데이터 정의 예시: 새해 카운트다운 데이터

# itemization: 
{: #itemization}
# CountDown is one of:
{: #countdown-is-one-of}
#  - false
{: #false}
#  - Natural[1, 10]
{: #natural-1-10}
#  - "complete" ;; true로 놓으면 숫자도 true이므로 문자열로 표시
{: #complete-true로-놓으면-숫자도-true이므로-문자열로-표시}
# interp. false means not yest started
{: #interp-false-means-not-yest-started}
# Natural[1, 10] means countdown is running and how many seconds left
{: #natural-1-10-means-countdown-is-running-and-how-many-seconds-left}
# "complete" means countdown is over
{: #complete-means-countdown-is-over}

# Examples:
{: #examples}
CD1 = false
CD2 = 10 # just started running
CD3 = 1 # almost over
CD4 = "complete"

# Template
{: #template}
def fnForCountdown(c):
	if c==False (
		#...
		pass
    elif type(c)==int and c >= 1 and c <= 10:
        # 숫자 인지 확인(guard)하지 않으면 < 같은 부등호를 쓰면 string="complete"가 들어오면 오류.
	    #...c # 이후 c의 숫자에 따라 추가로 구현이 다르므로 body에 c를 포함해야 함.
	    pass
    else: # 입력을 CountDown으로 한정하므로 나머지는 굳이 비교 안해도 됨
	    #...
	    pass
#template rules used:
# - one of: 3 cases
{: #one-of-3-cases}
# - atomic distinict: false
{: #atomic-distinict-false}
# - atomic non-distinct: Natural[1, 10]
{: #atomic-non-distinct-natural-1-10}
# - atomic distnict: "complete"
{: #atomic-distnict-complete}

🧾️ 항목형 데이터 함수 예시: 새해 카운트 다운 함수

# Functions:
{: #functions}
# Signature: Countdown -> Image
{: #signature-countdown-image}
# Purpose: produce nice image of current state of countdown
{: #purpose-produce-nice-image-of-current-state-of-countdown}
# Stub: def countdownToImage(c) return "blank"
{: #stub-def-countdowntoimage-c-return-blank}

print(countdownToImage(False) == "blank")
print(countdownToImage(1) == "1")
print(countdownToImage(5) == "5")
print(countdownToImage(10) == "10")
print(countdownToImage("complete") == "Happy New Year!")
# <use template from Countdown>
{: #use-template-from-countdown}

def countdownToImage(c):
	if c == False:
		return "blank"
	elif type(int) == int and c >= 1 and c <= 10:
		return f"{c}"
	else:
		return "Happy New Year!"

• 열거형 데이터가 포함된 부분도 테스트해줘야 한다.

복합 데이터(Compound data)

하나 이상의 같거나 다른 형태의 데이터들과 짝을 이루는 데이터 구조

🧾️ 복합 데이터 정의 예시: 하키 선수 명단

class Player:
	def __init__(self, fn, ln):
		self.fn = fn
		self.ln = ln
# Player is Player(fn:string, ln:string)
{: #player-is-player-fn-string-ln-string}
# interp. Player is a hocky player with
{: #interp-player-is-a-hocky-player-with}
# - fn is the first name
{: #fn-is-the-first-name}
# - ln is the last name
{: #ln-is-the-last-name}
P1 = Player("Bobby", "Orr")
P2 = Player("Wayne", "Gretzky")

def fnForPlayer(p):
	#...(p.fn, p.ln)
	pass

# Template rules used:
{: #template-rules-used}
# - Compound: 2 fields
{: #compound-2-fields}
# - atomic non-distinct: String
{: #atomic-non-distinct-string}
# 만약 서로 다른 형태의 데이터들이 짝지었다면
{: #만약-서로-다른-형태의-데이터들이-짝지었다면}
# 여기에 추가로 정의하자 (ex) atomic distinct: false)
{: #여기에-추가로-정의하자-ex-atomic-distinct-false}

🧾️ 복합 데이터 함수 예시: 사전순 하키선수 이름 함수

# Signature: Player Player -> String
{: #signature-player-player-string}
# Purpose: produce first name of player with the earliest last name in alphabetical order.
{: #purpose-produce-first-name-of-player-with-the-earliest-last-name-in-alphabetical-order}
# Stub:
{: #stub}
# def longerName(p1:Player, p2:Player):
{: #def-longername-p1-player-p2-player}
#	return p1.fn

#Tests:
print(longerName(P1, P2)=="Wayne")

#Templates:
def longerName_stub(p1, p2):
	# ...(p1.fn, p1.ln, p2.fn, p2.ln)
	pass 

def longerName(p1, p2):
	return p1.fn if p1.ln < p2.ln else p2.fn

• 함수 템플릿 부분을 잘 보자

List 데이터(List data)

하나 이상의 타입의 데이터들을 동적인 수만큼 할당 가능한 데이터 구조
강의에서는 재귀를 이용해 동적할당을 처리하지만, 대부분의 프로그래밍 언어에서는 그러하지 않으므로 변경했다.

🧾️ 리스트 데이터 정의 예시: 퀴디치 팀 명단

ListOfString = []
# ListOfString is one of:
{: #listofstring-is-one-of}
# - empty list
{: #empty-list}
# - List of String
{: #list-of-string}
# interp. a list of strings
{: #interp-a-list-of-strings}
LOS1 = []
LOS2 = ["Mcgill", "UBC"]

def fnForLos(los):
	if len(los)==0:
		#...
		pass
	else:
		for e in los:
			#...e
			pass
# Template rules used:
{: #template-rules-used}
# - one if: 2 cases
{: #one-if-2-cases}
# - atomic distinct: empty
{: #atomic-distinct-empty}
# - compound: n fields of string
{: #compound-n-fields-of-string}

참조 관계 데이터

두 개 이상의 데이터가 참조 관계 등으로 인해 정의되어야 할 경우

참조형 데이터에는 총 세가지 종류가 있다.

• **참조형(Reference) **
• 자기 참조형(Self Reference) 재귀
• 상호 참조형(Mutual Reference) 재귀

✍ 참조형 데이터의 참조 관계는 템플릿과 함수에도 동일한 구조를 나타나게 한다.

참조형 데이터

데이터 내부에 다른 데이터 구조가 포함되어 있는 구조

🧾️ 참조 관계의 두 데이터 정의 예시와 템플릿 : 학교별 등록금 정보

# Data definition:
{: #data-definition}
class School:
	def __init__(self, name, tuition):
		self.name = name
		self.tuition = tuition
# Shcool is School(String, Integer[0,])
{: #shcool-is-school-string-integer-0}
# interp. name is the school's name, tuition is interational student's tuition in USD
{: #interp-name-is-the-school-s-name-tuition-is-interational-student-s-tuition-in-usd}

S1 = School("School1", 27797)
S2 = School("School2", 23300)
S3 = School("School3", 28500)

def fnForSchool(s):
	#(...(school-name s)(school-tuition s))
	pass 
# this template is helper funtion for fn-for-los
{: #this-template-is-helper-funtion-for-fn-for-los}

# Template rules used:
{: #template-rules-used}
# - compound: School(String, Integer[0,])
{: #compound-school-string-integer-0}

# ListOfSchool is one of:
{: #listofschool-is-one-of}
# - empty
{: #empty}
# - compound: n fields of School 
{: #compound-n-fields-of-school}# reference from school
# interp. a list of schools
{: #interp-a-list-of-schools}
LOS1 = []
LOS2 = [S1, S2, S3]

def fnForLos(los):
	if len(los)==0: 
		#... 
		pass 
	else: 
		for e in los: 
			#...fnForSchool(e) # mutual recursion from mutual-reference
			pass
			
# Template rules used:
{: #template-rules-used}
# - one of 2 cases:
{: #one-of-2-cases}
# - atomic distinct : empty
{: #atomic-distinct-empty}
# - compound: n fields of School
{: #compound-n-fields-of-school}
# - Mutual reference: School 
{: #mutual-reference-school}# other reference

자기참조형 데이터

데이터 내부에 자신과 같은 구조가 마찬가지로 포함된 데이터 구조

🧾️ 재귀형 데이터 정의 예시와 템플릿: 재귀 구조 숫자 리스트

# Data definition:
{: #data-definition}

# ListOfNumber is one of the
{: #listofnumber-is-one-of-the}
# - empty
{: #empty}
# - [Integer] + ListOfNumber 
{: #integer-listofnumber}# 데이터 설계 중 재귀 구조 발견
# interp. an arbitrary number of Numbers
{: #interp-an-arbitrary-number-of-numbers}

def fnForLon(lon):
	if len(lon)==0:
		#...
		pass
	else:
		#...lon[0]
		#...fnForLon(lon[1:])
		pass

상호참조형 데이터

서로 다른 두 데이터 구조가 서로를 내부에 포함한 구조

• 상호 참조형 데이터 정의 시, 서로 관계된 데이터의 해석, 정의, 예시, 템플릿을 서로 가깝게 두고, 동시에 진행되는 경우가 많다.
• 2차원 배열 등을 입력으로 받을 때 많이 사용됨(arbitrary-arity-tree)

🧾️ 상호참조형 데이터 정의 예시와 템플릿

템플릿을 활용해 함수를 만들때, 추가되는 인자들은 재귀하면서 기반 사례로 수렴하도록 바뀌어야 하므로, 일단 ??? 같은 문자로 놔두고 필요에 따라 바꾸면 된다.

# Data definition:
{: #data-definition}

# Element is (make-elt String Integer ListOfElement)
{: #element-is-make-elt-string-integer-listofelement}
# interp. An element in the file system, with name, and EITHER data or subs.
{: #interp-an-element-in-the-file-system-with-name-and-either-data-or-subs}
#         If data is 0, then subs is considered to be list of sub elements.
{: #if-data-is-0-then-subs-is-considered-to-be-list-of-sub-elements}
#         If data is not 0, then subs is ignored.
{: #if-data-is-not-0-then-subs-is-ignored}

# ListOfElement is one of:
{: #listofelement-is-one-of}
#  - empty
{: #empty}
#  - [Element] + ListOfElement
{: #element-listofelement}
# interp. A list of file system Elements
{: #interp-a-list-of-file-system-elements}

def fnForElt(name, data, loe): # Compound data
	# ... (name) :String
	# (data) : Integer
	# fnForLoe(loe) : Reference
	pass


def fnForLoe(loe):
	if len(loe)==0:
		#...
		pass
	else:
		#...fnForElt(loe[0])
		#...fnForLoe(loe[1:])
		pass

• 가지치기 방식이라고도 불리우는 Backtracking 탐색 등에 사용된다.-> 어떤 자식 노드가 정답이 아니면 자신의 부모 노드로 돌아가 다음 자식 노드를 찾는 방식

🧾️ Backtracking search 템플릿

(define (fn-for-x x)
  (... (fn-for-lox (x-subs x))))        

(define (fn-for-lox lox)
  (cond [(empty? lox) false]
        [else
          (if (not (false? (fn-for-x (first lox))))  ;is first child successful?
              (fn-for-x (first lox))                 ;if so produce that
              (fn-for-lox (rest lox)))]))            ;or try rest of children

함수

고차 함수와 같이 함수를 인자로 받는 경우

• 이때 인자에 들어갈 수 있는 함수의 타입은 시그니처로 구분한다.
• 즉, 오직 같은 인자의 갯수, 인자들의 타입, 결과값의 타입들이 일치하는 함수만 집어넣을 수 있다.

➕ 고차함수(high-order function)?

함수를 인수로 취하거나 결과로 반환할 수 있는 함수

🧾️ 고차 함수의 예시

고차 함수의 시그니처 안에 또 다른 시그니처가 존재하는 것을 주목하자. 같은 시그니처의 함수라면 인자로 들어갈 수 있다.

;; (X -> X) ListOfX -> ListOfX
;; given fn and (list n0 n1 ...) produce (list (fn n0) (fn n1) ...)
(check-expect (map2 sqr empty) empty) 
(check-expect (map2 sqr (list 2 4)) (list 4 16))
(check-expect (map2 sqrt (list 16 9)) (list 4 3))
(check-expect (map2 abs (list 2 -3 4)) (list 2 3 4)) 

(define (map2 fn lon) 
	(cond 
		[(empty? lon) empty] 
		[else (cons (fn (first lon)) (map2 fn (rest lon)))]))