티스토리 뷰
마지막으로 조금 남은 기초 용어들에 대해서만 정리합니다.
- Lift
- 함수와 파라미터를 받아 함수에 파라미터를 적용한 결과를 반환하는 것. 이 때, LiftA2, Lift 가 있고 전자는 2개 인자를 받아 map, ap을 적용하고 후자는 map을 적용합니다.
- Equational Reasoning
- 응용 프로그램이 부수 효과가 없는 순수 함수(표현식)들로만 구성되었다면 최종 시스템은 부분들로부터 유도가 가능하다는 추론입니다.
- 두 표현식은 아래 조건의 경우 동등합니다
- 두 표현식이 같은 값을 평가하거나,
- 두 표현식이 모두 무한 루프를 돌거나,
- 두 표현식이 모두 같은 예외를 던지거나.
- 아래의 규칙에 의존할 수 있습니다.
- 반사성(reflexivity) : 어떤 표현식 e 에 대하여 e == e 입니다.
- 대칭성(symmetry) : 표현식 e1, e2 에 대하여 e1 == e2 이면 e2 == e1 입니다.
- 전이성(transitivity) : 표현식 e1, e2 그리고 e3 에 대하여 e1 == e2 이고 e2 == e3 이면 e1 == e3 입니다.
- 적합성(congrueence) : 표현식 e1, e2 그리고 e 에 대하여 e1 == e2 이면 e[e1/x] == e[e2/x] 입니다.
- 알파동치(alpha-equivalence) : 표현식 e1, e2 에 대하여 e1 이 e2 에서 변수 이름만 다른 경우 e1 == e2 입니다.
- 문법 설탕(syntatic sugar) : 정의에 의하여 함수 f 가 x = e 로 정의되면 이름 있는 함수 fun : x → e 가 있을 때 둘은 같습니다.
- 평가(eval) : 표현식 e1, e2에 대하여 e1의 평가 결과가 e2라면(e1 → e2) e1 == e2 입니다.
-
(1) 1 == 1 (reflexivity)
(2) let x = 3 in x + x == let x = 3 in x + x (reflexivity)
(3) 1 + 2 == 3 (eval)
(4) 3 == 1 + 2 ((3), symmetry)
(5) -5 + 8 == 3 (eval)
(6) -5 + 8 == 1 + 2 ((4), (5), transitivity)
(7) let x = 1 in x == let y = 1 in y (alpha)
(8) 1 + 2 == (fun x -> 1 + x) 2 (eval, symmetry)
(9) let f x = x+1 in f 3
== let g = fun y -> y+1 in g 3 (alpha (twice), syntactic sugar)
(10) (fun x -> 1 + x) 2 == -5 + 8 ((6), (8), transitivity, symmetry)
(11) (-5 + 8) * y == (1 + 2) * y ((6), congruence)
- Lazy evaluation
- 지연 평가
- 표현식을 필요할 때까지 평가하지 않고 최대한 미루다가 정말 필요한 경우에 평가를 하는 방법
- Monoid
- 항등원을 갖는, 결합 법칙을 따르는 이항 연산을 갖춘 대수 구조
- 공리
- 임의의
- 임의의
- 임의의
- 이항 연산을 갖춘 항등원이 존재하는 구조이므로,
- Maybe
- List
- Ordering 등
- Monad 또한 모도이드 처럼 동작
- 전부 모노이드
- Corecursion
- co- 가 붙은 것들은 mathematical dual 이라 한다. '대비되는 개념'으로 간단히 생각할 수 있다(Co-monad, Co-monoid, Co-routine 등).
- 공재귀.
- 재귀가 기본 최소 단계(Base case)를 찾을 때까지(종료 조건 판별) 자가 호출을 통한 판별 방식이라면(Top-down), 공재귀는 최소 단계(Base case)에서 시작하여 목적하는 단계로 찾아가는 방법(Bottom-up).
- 함수형 자료구조의 암묵적 infinite 자료구조의 finite 한 처리를 가능하게 하는 개념
- 이러한 특성으로 Generator 생성시에도 사용됨
댓글