13. FPL (2)

Common Lisp

• Common Lisp는 1980년대 초반 여러 Lisp 방언(dialect)의 특징을 통합하여 만들어진 대형 언어임
• Scheme이 작고 간결한 철학을 지닌 언어인 것과 달리, Common Lisp은 풍부한 기능과 복잡성을 가진 언어
• Features include:
  • Records
  • Arrays
  • Complex numbers
  • Character strings
  • Powerful I/O capabilities
  • Iterative control statements

DEFSTRUCT를 사용한 RECORDS

• DEFSTRUCT는 구조체를 만드는 명령어

(DEFSTRUCT PERSON
  NAME
  AGE)
(SETF P1 (MAKE-PERSON :NAME "ALICE" :AGE 30))
(PERSON-NAME P1) ; → "ALICE"
(PERSON-AGE P1)  ; → 30

• MAKE-PERSON은 :NAME과 :AGE를 받아서 구조체 객체를 생성, 그 결과를 변수 P1에 할당함
• P1 구조체에서 NAME 슬롯을 꺼냄. 결과는 "ALICE"가 됨

MAKE-ARRAY를 사용한 배열

(SETF A (MAKE-ARRAY '(2 3) :INITIAL-CONTENTS '((1 2 3) (4 5 6))))
(AREF A 0 1) ; → 2

• 2x3짜리 2차원 배열 A를 만들고, 초기값으로 ((1 2 3) (4 5 6))을 설정
• AREF는 배열의 특정 위치 값을 꺼낼 때 사용하는 함수
• 위에서는 0행 1열의 값을 꺼내니 2가 나옴

COMPLEX NUMBERS

(SETF C #C(3 4))
(REALPART C) ; → 3
(IMAGPART C) ; → 4
(ABS C)      ; → 5.0

• #C(3 4)는 복소수 3 + 4i를 표현하는 방법
• REALPART: 실수부만 꺼냄
• IMAGPART: 허수부만 꺼냄
• ABS: 복소수의 크기를 계산 (√(3² + 4²) = 5.0)

문자열(String)

(SETF S "HELLO, LISP!")
(SUBSEQ S 0 5) ; → "HELLO"

• 문자열 변수 S를 정의
• SUBSEQ는 부분 문자열을 자를 때 사용 (0부터 5 전까지)

파일 입출력 (I/O)

(WITH-OPEN-FILE (STREAM "OUTPUT.TXT" :DIRECTION :OUTPUT :IF-EXISTS :SUPERSEDE)
  (FORMAT STREAM "HELLO, FILE!~%"))

• "OUTPUT.TXT"라는 파일을 쓰기 모드로 열어서, "HELLO, FILE!"이라는 문장을 씀
• WITH-OPEN-FILE은 파일을 열고 닫는 것을 자동으로 처리
• STREAM은 파일 스트림(입출력 통로)을 나타내는 변수명
• :DIRECTION :OUTPUT → 파일을 쓰기 모드로 연다는 뜻
• :IF-EXISTS :SUPERSEDE → 파일이 이미 있으면 덮어쓴다(기존 내용 삭제)는 의미

반복문: LOOP

(LOOP FOR I FROM 1 TO 5 DO
  (FORMAT T "I = ~A~%" I))

• FOR I FROM 1 TO 5는 1부터 5까지 반복
• 각 반복마다 I = 1, I = 2, ... 를 출력
• ~A는 값을 자동으로 문자열로 변환해 출력함
• T는 출력 대상을 콘솔(터미널)로
• Common LISP allows both static and dynamic scoping
  • The default scoping for variables is static
  • Declaring a variable to be "special," that variable becomes dynamically scoped

Function

(DEFUN *functionname* (*param1 param2 ... paramN*) (*statements*))

(DEFUN square (x) (* x x))

(DEFUN iterative_member (atm lst)
  (PROG ()
    loop_1
    (COND
      ((NULL lst) (RETURN NIL))      ; 리스트 끝 → 못 찾음
      ((EQUAL atm (CAR lst)) (RETURN T)) ; 찾음 → TRUE
    )
    (SETQ lst (CDR lst))  ; 리스트 다음 요소로 이동
    (GO loop_1)           ; 다시 반복
  ))

(DEFUN recursive_member (atm lst)
  (COND
    ((NULL lst) NIL)
    ((EQUAL atm (CAR lst)) T)
    (T (recursive_member atm (CDR lst)))
  ))

• PROG: 내부에 레이블(label)을 정의하고, 코드 실행 흐름을 제어할 수 있는 구조. 간단한 루프나 점프(비추천)를 만들 때 사용
• GO: PROG 내에서 정의한 레이블로 점프함
• RETURN: PROG 블록에서 값을 반환하며 탈출

Backquote operator (`)

• Similar to the Scheme's QUOTE, except that some parts of the parameter can be unquoted by preceding them with commas
• Common Lisp에서는 ,(쉼표)를 이용해서 일부 표현식을 "평가 가능하게 만들 수 있다"는 게 큰 특징
  • `(a (* 3 4) c) evaluates to (a (* 3 4) c)
  • `(a ,(* 3 4) c) evaluates to (a 12 c)
  • ,(* 3 4) → (* 3 4) 부분만 계산됨

Macros

• Macros are often used in Common LISP to extend the language
  • 매크로는 코드 조각을 생성하거나 바꿔주는 도구
  • 일반 함수와 달리, 매크로는 "코드를 반환하는 함수"처럼 동작함
• Create their effect in two steps:
  • 확장 (Expansion) – 코드가 매크로 정의대로 치환됨
  • 평가 (Evaluation) – 확장된 코드가 실행됨
• Lisp 코드를 확장하고 제어 구조를 새로 정의할 수 있음

새로운 언어 기능처럼 만들 수 있어서 언어를 확장하는 도구로 사용됨

• Some of the predefined functions of Common Lisp are actually macros.
  • 일부 Common Lisp의 기본 제어문들도 사실은 함수가 아니라 매크로임
  • i.e. DOTIMES(주어진 횟수만큼 반복), DOLIST(리스트를 반복), DO
• Users can define their own macros with DEFMACRO (사용자 정의 매크로)

(defun say-hello (x)
  (dotimes (i x 'Stop!)
    (format t "~% Hello ~s" i)))

(say-hello 3)
; Hello 0
; Hello 1
; ...

Common Lisp Symbol Data Type

• Common Lisp has a symbol data type (similar to that of Ruby)
  • 심볼(symbol)은 Lisp에서 이름(name)을 표현하는 데이터 타입
  • The reserved words are symbols that evaluate to themselves (i.e. T and NIL)
  • Symbols are either bound or unbound
  • Bound → 심볼이 어떤 값에 바인딩(연결) 되어 있음
  • Unbound → 심볼이 아직 어떤 값에도 바인딩되지 않음 (에러 발생 가능)

(DEFUN EXAMPLE (X)
  (+ X 1))

(SETF A 10)  ; A는 10에 바인딩됨
B            ; 아무런 바인딩이 없으면 → 에러: unbound variable B

• 함수 인자 → 함수 실행 중 바인딩
• SETF, LET 등으로 값 할당된 변수 → 바인딩됨
• 아무 할당도 없는 일반 심볼 → 바인딩되지 않음 → 에러 발생

ML

A static-scoped functional language with syntax that is closer to Pascal than to Lisp

• ML은 Lisp 계열처럼 괄호로 가득한 문법이 아님

타입 선언(type declarations) 가능하지만, 대부분은 자동으로 추론(type inferencing)됨

fun add x y = x + y; (* ML이 x와 y의 타입을 int로 추론 *)

• It is strongly typed and has no type coercions
  • 타입 간 암묵적 변환(coercion)을 허용하지 않음
  • Type of every variable and expression can be statically determined
• Does not have imperative-style variables
  • 변수는 불변(immutable)이고, 새로운 값을 만들지 기존 값을 변경하지 않음
• Includes exception handling and a module facility for implementing abstract data types
• Includes lists and list operations

ML Specifics

A table called the evaluation environment stores the names of all identifiers in a program, along with their types (like a run-time symbol table)

평가 환경(evaluation environment)은 일종의 런타임 심볼 테이블

프로그램 내의 모든 식별자(identifier)에 대해 이름, 타입, (함수인 경우) 바디를 저장하고, 정적 스코프 규칙에 따라 평가할 때 사용됨

Function declaration form

fun name (formal parameters) = expression;

• Note that infix!

fun cube(x : int) = x * x * x;
(* [In Scheme] (DEFINE (cube x) (* x x x)) *)

• x는 int 타입으로 명시됨
• 결과값은 마지막 표현식인 x * x * x
• 함수의 반환값(return value)은 마지막 표현식의 값
• Expression can be a list of expressions
  • Separated by semicolons and surrounded by parentheses
  • Return value is from the last expression
  • Without side effect, expressions before the last serve no purpose!

fun test () = (
  print "ML is nice\n";
  3 + 4;
  11
);

여러 표현식을 한 줄에 쓸 수 있고, ;로 구분하며 ()로 감쌈

마지막 표현식 11이 이 함수의 반환값. ML은 순수 함수형 언어라, 부수 효과(side effect)가 없으면 앞의 표현식은 무시됨

Type inference

정적 타입 언어지만, 대부분의 경우 타입을 명시할 필요가 없음

왜냐하면 ML의 타입 추론 시스템이 문맥을 보고 타입을 자동으로 결정하기 때문

fun circumf(r) = 3.14159 * r * r;

• Takes a floating-point and produces a floating-point result
• Types are inferred from type of the literal in expression

fun square(x) = x * x;

• No literal and arithmetic operator (명확한 리터럴이 없을 경우, 연산자를 기준으로 추론)

→ type of the parameter and the function are assumed to be numeric

• Default numeric type: int
• square(2.75); → cause an error (not coerce real) (square는 int -> int)
• → square_real(2.75);
• The type could be attached to return value, as in:

fun square(x) : real = x * x;
fun square(x: real): real = x * x;

• 여기서 : real은 함수 반환값의 타입을 지정한 것
• With no type specified, it would default to int (the default for numeric values)
• User-defined overloaded functions are not allowed, so if we wanted a cube function for real parameters, it would need to have a different name
  • 예: fun square(x: int)와 fun square(x: real)을 동시에 정의 불가 → 이름을 다르게 지어야 함

fun square_int(x: int) = x * x;
fun square_real(x: real) = x *. x;

(* 다양한 위치에서의 타입 명시 *)
fun square(x : real) = x * x;
fun square(x) = (x : real) * x;
fun square(x) = x * (x : real);

ML selection

• Similar to that of the imperative languages

if expression then then_expression
else else_expression

where the first expression must evaluate to a Boolean value

fun fact(n : int): int = if n <= 1 then 1
                         else n * fact(n − 1);

(* [In Scheme]
(DEFINE (factorial n)
  (IF (<= n 1)
      1
      (* n (factorial (− n 1))))) *)

• Pattern matching is used to allow a function to operate on different parameter forms

fun fact(0) = 1
  | fact(1) = 1
  | fact(n : int) : int = n * fact(n – 1)

Lists

• Literal lists are specified in brackets
  • [3, 5, 7]
  • []: the empty list
• CONS: binary infix operator ::
  • 앞에 원소를 붙여서 새로운 리스트를 만드는 이항 연산자
  • 4 :: [3, 5, 7], which evaluates to [4, 3, 5, 7]
  • right-associative: 1 :: 2 :: 3 :: []는 1 :: (2 :: (3 :: []))
• CAR is the unary operator hd
  • 리스트의 첫 번째 원소를 반환, 빈 리스트에는 직접 적용X
  • hd [3, 5, 7] → 3
• CDR is the unary operator tl
  • 리스트의 나머지 리스트를 반환 (첫 원소 제외), 빈 리스트에는 직접 적용X
  • tl [3, 5, 7] → [5, 7]
• Availability of patterned function parameters → hd and tl are much less frequently used in ML than CAR and CDR in Scheme

fun length([]) = 0
  | length(h :: t) = 1 + length(t);

fun append([], lis2) = lis2
  | append(h :: t, lis2) = h :: append(t, lis2);

(* [In Scheme]
(DEFINE (length list)
  (COND
    ((NULL? list) 0)
    (ELSE (+ 1 (length (CDR list))))))

(DEFINE (append list1 list2)
  (COND
    ((NULL? list1) list2)
    (ELSE (CONS (CAR list1)
                (append (CDR list1) list2))))) *)

• ML의 패턴 매칭 덕분에 hd, tl 같은 연산자가 함수 정의 내부에서 구조적으로 녹아들어 있음

val statement

• The val statement binds a name to a value (similar to DEFINE in Scheme)

val distance = time * speed;

• As is the case with DEFINE, val is nothing like an assignment statement in an imperative language → name cannot be later rebound to a new value
• If there are two val statements for the same identifier, the first is hidden by the second

val statements are often used in let constructs (지역 변수 블록을 만드는 표현식)

let
  val radius = 2.7
  val pi = 3.14159
in
  pi * radius * radius
end;

(* [In Scheme]
(LET ((radius 2.7) (pi 3.14159))
     (* pi radius radius)) *)

filter

A higher-order filtering function for lists

리스트에서 조건을 만족하는 원소만 남기는 고차 함수

• Takes a predicate function as its parameter, often in the form of a lambda expression

fn(parameter) => expression

• Lambda expressions are defined like functions, except with the reserved word fn

filter(fn(x) => x < 100, [25, 1, 711, 50, 100]);
(* This returns [25, 1, 50] *)

(* 일반함수도 사용 가능 *)
fun isSmall(x) = x < 100;
filter(isSmall, [25, 1, 711, 50, 100]);

map

A higher-order function that takes a single parameter, a function

리스트의 각 원소에 함수를 적용해서 새로운 리스트를 만드는 고차 함수

• Applies the parameter function to each element of a list and returns a list of results

fun cube x = x * x * x;
val cubeList = map cube;
val newList = cubeList [1, 3, 5];
(* This sets newList to [1, 27, 125] *)

(* Alternative: use a lambda expression *)
val newList = map (fn x => x * x * x, [1, 3, 5]);

Function Composition

두 함수를 결합하여 새로운 함수를 만드는 것

• Use the unary operator, o (a lowercase "oh")

val h = g o f;

• First applies function f and then applies function g to the returned value from f

fun double x = 2 * x;
fun square x = x * x;
val doubleThenSquare = square o double;
val result = doubleThenSquare(3); (* 결과: square(double(3)) = square(6) = 36 *)

Currying

• ML functions actually take just one parameter
• If more, it considers the parameters a tuple (commas required)

fun addTuple (a, b) = a + b; (* tuple 인자 *)
addTuple(3, 5); (* OK *)

• Currying: Replaces a function with more than one parameter (여러 인자를 받는 함수를, 하나의 인자만 받는 함수들의 연속으로 바꾸는 방식)

→ a function with one parameter that returns a function that takes the other parameters of the original function

• Can be defined in curried form by leaving out the commas in the parameters

쉼표 없이 인자를 나열하면 자동으로 커링된 함수가 정의됨

fun add a b = a + b;
(* → fun add a = fn b => a + b; *)
(* add는 먼저 a를 받고, 그 결과로 b를 받는 함수를 반환 *)

val result = add 3 5;   (* = 8 *)
val add3 = add 3;       (* = fn b => 3 + b *)
val r = add3 10;        (* = 13 *)

• Tuple vs Curried Form

커링을 쓰면 부분 적용이 가능해서 유용함

Partial Evaluation (부분 평가)

• Curried functions can be used to create new functions by partial evaluation
• Partial evaluation means that the function is evaluated with actual parameters for one or more of the leftmost actual parameters

부분 평가는 함수의 일부 인자만 먼저 적용해서 새로운 함수를 만드는 방식

특히 커링된 함수에서 왼쪽부터 일부 인자에만 값을 주면, 그 값이 고정된 새로운 함수가 반환

fun add a b = a + b;
fun add5 x = add 5 x;
(* Takes the actual parameter 5 and evaluates the add function with 5 as the value of its first formal parameter. *)
(* Returns a function that adds 5 to its single parameter *)
val num = add5 10; (* sets num to 15 *)

(* [In Scheme]
(DEFINE (add x y) (+ x y))
[Curried version]
(DEFINE (add y) (LAMBDA (x) (+ y x)))
((add 3) 4) *)

커링 + partial evaluation을 이용하면, 재사용 가능한 특화 함수를 쉽게 만들 수 있음

Haskell

• Similar to ML: Syntax, static scoped, strongly typed, type inferencing, pattern matching

• Different from ML (and most other functional languages):

e.g., no variables, no assignment statements, and no side effects of any kind

Basic operations

• head: 0th element
• head [2, 3, 4] -- 2
• tail: All elements except element 0
• tail [2, 3, 4] -- [3, 4]
• init: all elements except the last element (initial part of a list)
• init [2, 3, 4] -- [2, 3]
• last: last element
• last [2, 3, 4] -- 4
• take: get elements from front
• take 2 [2, 3, 4] -- [2, 3]
• drop: remove elements from front
• drop 2 [2, 3, 4] -- [4]

head, tail, init, last는 빈 리스트 []에 사용하면 에러가 발생. 예: head [] → runtime error

take과 drop은 길이를 넘는 값을 넣어도 안전함.

• take 5 [1, 2] → [1, 2]
• drop 5 [1, 2] → []
• Indexing from 0 using !!
  • n번째 인덱스에 있는 값을 반환: list !! index

[1, 2, 3, 4] !! 1   -- 2
[1, 2, 3, 4] !! 2   -- 3
[1, 2, 3, 4, 5] !! 0 -- 1
[1, 2, 3] !! 5      -- 에러: index too large
[1, 2, 3] !! (-1)   -- 에러: negative index

Haskell Lists

• List notation: put elements in brackets (리스트는 동일한 타입의 값들로 구성)

directions = ["north", "south", "east", "west"]
length directions -- 결과: 4

• Arithmetic series with the .. operator (산술 수열)
  • 첫 번째 두 항목을 기반으로 증가 간격을 추정
  • [2, 4..10] is [2, 4, 6, 8, 10]
  • 무한 리스트도 생성 가능
  • [1,3..] -- 무한히 2씩 증가하는 수열
  • take 5 [1,3..] -- [1,3,5,7,9]
• Concatenation is with ++ (리스트 연결)
  • [1, 3] ++ [5, 7] results in [1, 3, 5, 7]
  • 시간 복잡도는 앞 리스트의 길이에 비례하므로 앞쪽 리스트가 너무 길면 성능 저하 가능
• CONS, CAR, CDR via the colon operator (infix version of CONS)
  • 1:[3, 5, 7] results in [1, 3, 5, 7]

A list can only contain the same type

• 예: [1, 2, 3]은 OK, 하지만 [1, "two", 3]은 타입 오류

product [1, 2, 3, 4, 5]  -- 120
sum [1, 2, 3, 4, 5]      -- 15
length [1, 2, 3, 4, 5]   -- 5
reverse [1, 2, 3, 4]     -- [4, 3, 2, 1]

• product, sum은 Num 타입 클래스의 인스턴스(예: Int, Integer, Float 등)에만 적용 가능
• reverse는 어떤 타입의 리스트에도 동작. (예: reverse "hello" → "olleh")

Haskell Tuples

A tuple can contain the different type

• 이질성: 튜플은 각 원소가 서로 다른 타입일 수 있음

(False, 'a', True)    -- (Bool, Char, Bool)
(True, ['a', 'b'])    -- (Bool, [Char]) 또는 (Bool, String)

쌍(pair), 즉 두 원소짜리 튜플에 대해서 편리한 접근 함수

• fst: 두 원소짜리 튜플의 첫 번째 원소를 반환
• snd: 두 원소짜리 튜플의 두 번째 원소를 반환

fst (1, "Hello")        -- 1
snd (1, "Hello")        -- "Hello"
fst (snd (1, (2, 3)))   -- 2

Haskell Functions

• Haskell에서는 괄호 없이 공백으로 함수 인자를 전달

f x         -- f(x)
f x y       -- f(x, y) → 실제로는 ((f x) y) 형태로 왼쪽부터 적용
f (g x)     -- f(g(x))
f x (g y)   -- f(x, g(y))
f x * g y   -- f(x) * g(y) ← *가 f x와 g y 결과를 곱함

double x = x + x
quadruple x = double (double x)
take (double 2) [1, 2, 3, 4, 5, 6]  -- [1, 2, 3, 4]
avg ns = sum ns `div` length ns      -- average
-- Function surrounded by backticks: infix binary operator
-- avg ns = div (sum ns) (length ns)

• Because Haskell support polymorphism, this works for any numeric type of x

아래 함수는 구체적인 타입 명시 없이 정의됐지만, Haskell의 타입 추론과 다형성 지원 덕분에, x가 Num 타입 클래스에 속한 어떤 타입이든 사용할 수 있음

square x = x * x
-- [In ML]
-- fun cube(x : int) = x * x * x;
-- ML에서는 구체적인 타입 필요

• Syntax differences from ML

fact 0 = 1
fact 1 = 1
fact n = n * fact (n – 1)

fib 0 = 1
fib 1 = 1
fib (n + 2) = fib (n + 1) + fib n
-- 수식 기반 패턴 매칭: 이 표현은 Haskell에서만 가능
-- n + 2는 패턴 매칭 시 역으로 "2 이상"을 의미함

{- [In ML]
fun fact(0) = 1
  | fact(1) = 1
  | fact(n : int) : int = n * fact(n – 1)

fun fib(0) = 1
  | fact(1) = 1
  | fact(n : int) : int = fact(n – 1) * fact(n – 2)
-- ML은 정수 연산 표현식 기반 패턴은 허용하지 않음
-- 즉, fib(n + 2) 같은 형태는 사용 불가 -}

• Guards can be added to lines of a function definition to specify the circumstances under which the definition can be applied
  • | (파이프) 기호를 사용해 조건을 나열함
  • 각 조건이 True가 되면 해당 결과를 반환
  • An otherwise can appear as the last condition in a conditional expression
  • 마지막에 otherwise를 써서 기본(default) 조건을 지정할 수 있음
  • (otherwise는 사실 True로 정의된 상수)

fact n
  | n == 0 = 1
  | n == 1 = 1
  | n > 0  = n * fact(n – 1)

sub n
  | n < 10    = 0
  | n > 100   = 2
  | otherwise = 1

if-then-else는 하나의 조건만 다루지만 guards는 여러 조건을 깔끔하게 나열할 수 있음

Pattern Parameters

-- product: 재귀적으로 곱셈 수행
product [] = 1
product (a:x) = a * product x
-- length
length [] = 0
length (a:x) = 1 + length x
-- reverse
reverse [] = []
reverse (a:x) = reverse(x) ++ [a]
-- Factorial:
fact n = product [1..n]
-- drop: 리스트에서 앞에서부터 n개를 제거
drop 0 x = x
drop _ [] = []
drop n (a:x) = drop (n-1) x
-- ++: 리스트 연결 연산을 직접 정의한 것
[] ++ y = y
(a:x) ++ y = a : (x ++ y)
-- *: 자연수에 대한 곱셈을 재귀적으로 정의한 것
m * 0 = 0
m * n = m + (m * (n - 1))

let ... in construct

• Similar to ML's let and val

let <바인딩들> in <표현식>

let 안에서는 여러 개의 지역 변수(또는 함수)를 정의할 수 있고, in 뒤에는 실제로 계산할 표현식을 적음

모든 let 내부 바인딩은 immutable(불변)

quadratic_root a b c =
  let
    minus_b_over_2a    = − b / (2.0 * a)
    root_part_over_2a  = sqrt(b ^ 2 − 4.0 * a * c) / (2.0 * a)
  in
    minus_b_over_2a − root_part_over_2a,
    minus_b_over_2a + root_part_over_2a

where construct

함수 본문 아래에 지역 변수를 정의하는 방식

여러 표현식에서 공통으로 쓰이는 중간 결과를 깔끔하게 정리할 수 있음

let ... in은 표현식 내부, where는 함수 정의 바깥에 위치

quadratic_root a b c =
  [minus_b_over_2a - root_part_over_2a,
   minus_b_over_2a + root_part_over_2a]
  where
    minus_b_over_2a   = - b / (2.0 * a)
    root_part_over_2a = sqrt (b ^ 2 - 4.0 * a * c) / (2.0 * a)

List Comprehensions

• Python의 리스트 내포와 비슷하지만, Haskell 특유의 표현력과 수학적인 문법을 잘 보여주는 기능

[<expression> | <qualifiers>]

• <expression>: 결과로 만들어질 각 원소
• <qualifiers>: 변수 생성, 조건 필터링 등

[n * n * n | n <- [1..50]]
-- "a list of all n*n*n such that n is taken from the range of 1 to 50"
-- The qualifier in this example has the form of a generator (n <- [1..50])

• Multiple generators

[(x, y) | x <- [1..3], y <- [4..5]]
-- [(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]
-- x는 1부터 3까지, y는 4부터 5까지 → 모든 조합

• Dependant generator

[(x, y) | x <- [1..3], y <- [x + 1]]
-- [(1,2),(2,3),(3,4)]
-- y는 x에 의존해서 결정됨

concat 정의 (리스트 평탄화)

concat xss = [x | xs <- xss, x <- xs]
concat [[1, 2, 3], [4, 5], [6]]  -- [1,2,3,4,5,6]
-- 외부 리스트 xss에서 리스트 xs를 하나씩 꺼내고, 각 xs 안의 원소 x를 꺼내 리스트로 만듦

조건 필터(guard)

[x | x <- [1..n], 조건식]

• It could be in the form of a test. If qualifiers are in the form of Boolean expressions (guards)

약수 구하기 (factors)

factors n = [x | x <- [1..n], n `mod` x == 0]
-- x가 1부터 n까지 순회하면서, n이 x로 나누어 떨어지면 (n mod x == 0) 리스트에 포함
factors 17  -- [1,17]
factors 15  -- [1,3,5,15]

소수 판별 (prime)

prime n = factors n == [1, n]
-- 소수는 오직 1과 자기 자신만 약수로 가지므로, factors n == [1, n]이면 소수

• The backticks specify the function is used as a binary operator

zip: takes two lists and creates one list

zip [1, 2, 3] ['a', 'b', 'c', 'd']  -- [(1,'a'),(2,'b'),(3,'c')]
-- 두 리스트의 각 요소를 쌍으로 묶음. 더 짧은 리스트 기준으로 잘림

pairs 함수: 인접 쌍 만들기

pairs xs = zip xs (tail xs)
pairs [1, 2, 3, 4]  -- [(1,2),(2,3),(3,4)]
-- xs와 tail xs를 묶어서 (x₁,x₂), (x₂,x₃), ... 형태의 인접쌍 리스트 생성

sorted 함수: 정렬 여부 검사

sorted = and [x <= y | (x, y) <- pairs xs]
-- pairs xs로 인접한 원소 쌍들을 만들고, x <= y 조건을 검사하여 리스트 생성
-- and는 그 리스트의 모든 값이 True인지 확인 (정렬 확인)
sorted [1, 2, 3, 4]     -- True
sorted [1, 2, 5, 3, 4]  -- False

positions 함수: 특정 값의 위치 찾기

positions x xs = [i | (x', i) <- zip xs [0..n], x == x']
  where n = (length xs) - 1
-- zip xs [0..n]을 통해 각 원소와 그 인덱스를 쌍으로 만듦
-- 조건 x == x'인 경우에만 인덱스 i를 결과 리스트에 포함
positions 0 [0, 1, 0, 1, 1, 1, 1, 0]  -- [0,2,7]

String Comprehensions

• String is list of characters. 문자열도 리스트 함수와 comprehension을 그대로 사용

zip "abc" [1, 2, 3]         -- [('a',1),('b',2),('c',3)]
take 3 "asdasd"             -- "asd"
length "adasd"              -- 5
[c | c <- "hello", c /= 'l'] -- "heo"

Quicksort

리스트 내포(list comprehension)와 패턴 매칭을 활용해 아주 간결하게 표현

sort [] = []
sort (h:t) =
  sort [b | b <- t, b <= h]
  ++ [h] ++
  sort [b | b <- t, b > h]
-- sort [3, 1, 4, 2]
-- h = 3, t = [1, 4, 2]
-- 왼쪽 = [1, 2]
-- 오른쪽 = [4]
-- 최종 결과 = sort [1, 2] ++ [3] ++ sort [4]
-- 재귀적으로 수행되어 [1, 2, 3, 4]

• Illustrates the concision of Haskell

Insertion sort

-- 삽입 함수
insert x [] = [x]
insert x (y:ys)
  | x <= y    = x : y : ys
  | otherwise = y : insert x ys
-- 전체 정렬 함수
isort [] = []
isort (x:xs) = insert x (isort xs)
-- isort [3, 1, 4, 2]
-- = insert 3 (isort [1,4,2])
-- = insert 3 (insert 1 (isort [4,2]))
-- = insert 3 (insert 1 (insert 4 (isort [2])))
-- = insert 3 (insert 1 (insert 4 (insert 2 [])))
-- 순차적으로 정렬되어 [1,2,3,4]

{- [In scheme]
(DEFINE (insert atm lst)
  (COND
    ((NULL? lst) (CONS atm '()))
    ((< atm (CAR lst)) (CONS atm lst))
    (ELSE (CONS (CAR lst) (insert atm (CDR lst))))))

(DEFINE (sort lst)
  (if (NULL? lst)
    '()
    (insert (CAR lst) (sort (CDR lst))))) -}

• insert: x를 정렬된 리스트에 올바른 위치에 삽입함. 빈 리스트면 [x]를 반환. 앞의 원소 y와 비교해서 x <= y이면 x를 앞에 붙이고, 그렇지 않으면 y를 유지하고 나머지에 대해 재귀적으로 삽입
• isort: 입력 리스트를 왼쪽부터 하나씩 분해하면서 나머지를 먼저 정렬한 후, insert로 하나씩 앞에 끼워 넣는 방식 (재귀)

Merge sort

merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) =
  if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys

halve xs = splitAt (length xs `div` 2) xs

msort [] = []
msort [x] = [x]
msort xs = merge (msort ys) (msort zs)
  where (ys, zs) = halve xs
-- msort [4,1,5,2,6,3]
-- halve: ([4,1,5],[2,6,3])
-- 재귀적으로 msort 두 번 적용
-- 결과: [1,2,3,4,5,6]

1. merge 함수 – 두 정렬된 리스트를 병합: 두 리스트가 정렬된 상태로 들어오면, 앞에서부터 작은 값을 하나씩 뽑아서 새 리스트를 구성. x <= y일 때 x가 먼저 오고, 아니라면 y가 먼저
2. halve 함수 – 리스트를 반으로 나눔: splitAt은 리스트를 지정한 인덱스에서 둘로 나눔. length xs \div` 2`를 이용해 반으로 쪼개기
3. msort 함수 – 병합 정렬 전체 구현: 기저 조건으로 빈 리스트, 하나짜리 리스트는 정렬된 상태로 그대로 반환. 그렇지 않으면 리스트를 반으로 나누고, 양쪽을 재귀적으로 정렬한 뒤 merge함. where 구문으로 ys, zs 정의

Higher-order functions

• Higher-order function: 함수를 인자로 받거나 함수를 결과로 반환하는 함수

map: 리스트의 각 원소에 함수를 적용하여 새로운 리스트를 만드는 함수

map은 함수 f를 인자로 받는 함수이므로 고차 함수임

map (+1) [1, 3, 5, 7]  -- [2, 4, 6, 8]
-- 1. 리스트 내포 (List Comprehension)
map f xs = [f x | x <- xs]
-- 2. 재귀 (Recursive Function)
map f [] = []
map f (x:xs) = f x : map f xs

foldr: 리스트를 오른쪽에서 왼쪽으로 줄여나가는 함수 (right fold)

f [] = v
f (x:xs) = x `pred` f xs

• If it is an empty element, it returns a specific value v. Otherwise, pred is applied to element x, and f is applied to the remaining tail xs

구문 형태: foldr <operator> <initial_value> <list>

작동 방식: foldr f v [x1, x2, x3] = x1 \f` (x2 `f` (x3 `f` v))`

-- v = 0, pred = +
sum [] = 0
sum (x:xs) = x + sum xs
sum = foldr (+) 0
-- v = 1, pred = *
product [] = 1
product (x:xs) = x * product xs
product = foldr (*) 1
-- v = True, pred = &&
and [] = True
and (x:xs) = x && and xs
and = foldr (&&) True
-- v = 0, pred = \_ n -> 1 + n
length [] = 0
length (x:xs) = 1 + length xs
length = foldr (\_ n -> 1 + n) 0
-- v = [], pred = \x xs -> xs ++ [x]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
reverse = foldr (\x xs -> xs ++ [x]) []
-- length [10,20,30]
-- = 1 + (1 + (1 + 0)) = 3
-- reverse [1,2,3]
-- = 3 : [] → [3]
-- = 2 : [3] → [3,2]
-- = 1 : [3,2] → [3,2,1]

composition

f . g = \x -> f(g x)
-- \x -> expression: 익명 함수(anonymous function)
-- f . g는 g를 먼저 적용하고, 그 결과를 f에 넘김
-- 오른쪽부터 왼쪽으로 적용됨
-- 예: odd = not . even

all: 모든 요소가 조건을 만족하는가?

all p xs = and [p x | x <- xs]
-- 리스트 xs의 각 원소에 함수 p를 적용해서 [Bool] 리스트를 만들고, and를 이용해 모든 값이 True인지 확인
all even [2, 4, 6]  -- True
all even [2, 3, 6]  -- False

any: 하나라도 조건을 만족하는가?

any p xs = or [p x | x <- xs]
-- 리스트 xs의 각 원소에 함수 p를 적용해서 [Bool] 리스트를 만들고, or를 이용해 하나라도 True인지 확인
any odd [2, 4, 6]  -- False
any odd [2, 3, 6]  -- True

Lazy Evaluation

A language is strict if it requires all actual parameters to be fully evaluated

• Does not depend on the order in which the parameters are evaluated
• 예시: Scheme, ML, Java, Python
• f(x + y)를 호출하면, x + y는 무조건 먼저 계산됨
• 단점: 어떤 인자는 실제로 함수 내부에서 사용되지 않더라도 무조건 계산됨

A language is nonstrict if it does not have the strict requirement

• 인자가 사용될 때까지 평가를 미룸 (→ 필요할 때만 평가)
• lazy evaluation을 지원하는 방식으로 구현 가능
• 예시: Haskell
• Benefits:
  • [1] Nonstrict languages are more efficient: Some evaluation is avoided (related to short-circuit evaluation)
  • [2] Lazy evaluation - Only compute those values that are necessary
  • Recall that in Scheme the parameters are fully evaluated before function call
  • Actual parameters are evaluated only once, even if the same actual parameter appears more than once
  • We can make infinite lists
• Infinite data structures: lazy evaluation(지연 평가) 덕분에 무한한 데이터 구조도 안전하게 다룰 수 있음

positives = [0..]          -- 0부터 시작하는 모든 자연수
evens = [2, 4..]           -- 2부터 시작해서 2씩 증가
squares = [n * n | n <- [0..]]
-- Determining if 16 is a square number
squares = [n * n | n <- [0..]]
member squares 16

Member Revisited

member b [] = False
member b (a:x) = (a == b) || member b x

무한 리스트에서 특정 값이 존재하는지 안전하게 검사하는 방법: 리스트를 앞에서부터 순회하며, b와 같은 원소가 있으면 True 반환. 그러나 무한 리스트에 대해 사용하면 위험함 → 예: member 5 [n*n | n <- [0..]]에서 5는 없으므로 끝없이 탐색함

member2 n (m:x)
  | m < n     = member2 n x
  | m == n    = True
  | otherwise = False

• 리스트 (m:x)는 정렬된 상태라고 가정 (예: [0², 1², 2², ...])
• m < n이면 계속 탐색
• m == n이면 True
• m > n이면 더 이상 찾을 필요 없음 → False 즉시 반환
• 불필요한 평가 없이 빠르게 종료 가능
• 무한 리스트에 대해서도 안전하게 동작

squares = [n * n | n <- [0..]]
member2 16 squares  -- True
member2 5 squares   -- False (빠르게 종료)

F#

• Based on Ocaml, which is a descendant of ML and Haskell
• Fundamentally a functional language, but with imperative features (mutable, loop) and supports OOP
  • Has a full-featured IDE, an extensive library of utilities
  • Interoperates with other .NET languages
  • Free from Microsoft and supported by Visual Studio
  • Interoperability between C# and F# is quite easy
• Compared to C#:
  • Simple to write code and easy to maintain
  • Immutability
  • Function itself is a first-class object
  • Supports lazy evaluation

let binding

값을 정의(바인딩)하거나 함수를 선언할 때 사용

let square x = x * x  // function for square
let output = square 5  // 25
let a = 7              // 7

• Mutable function is possible

let mutable mutableX = 5
mutableX <- mutableX + 1  // 6, <- is assignment operator

• It should be carefully considered to use mutable because it breaks functional programming paradigm → Usually, it is possible to implement program without mutable
• Similar to Haskell: Statically typed, strongly typed, type inferencing, pattern matching
• Primitive types: bool, byte, int, float, double, char, unit (no value, 값이 없음)
• Includes a variety of data types: Tuples, lists, discriminated unions, records, and mutable and immutable arrays

Tuple

• Group of values of one or more types. 불변(immutable) 데이터 구조
• Useful for getting multiple inputs and returning outputs

(1,2,3)
("one", 2, a)

• Assessing each element

let (a, b, c) = (1, 2, 3)  // a = 1, b = 2, c = 3

fst와 snd는 2-튜플 전용 함수

let c = fst (1, 2, 3)  // c = 1
let d = snd (1, 2, 3)  // d = 2

3개 이상의 튜플에서는 직접 패턴 매칭이 필요함

let third (_, _, c) = c  // Function that returns the third element
third (1, 2, 3)          // 결과: 3

Struct tuple

• Value type tuple (<-> reference type)
• Stored in the stack, not the heap (더 성능이 우수할 수 있음)

let str = struct (1, 2, 3)      // 선언
let struct (a, b) = struct (1, 2)  // a = 1, b = 2, 구조 분해

• struct 키워드를 튜플 앞에 붙여 선언
• 분해할 때도 반드시 struct 키워드 사용해야 함
• Implicit conversion is not possible (struct tuple과 일반 tuple 간의 암묵적 변환은 불가능)

let (a, b) = struct (1, 2)    // 오류: 구조 분해는 struct로 해야 함
let struct (c, d) = (1, 2)    // 오류: 일반 튜플은 struct 분해 불가

• When we need?
  • Improve performance when the number of elements in the tuple to be used is large or individual elements have complex types
  • Interop with C#
• Supports generic sequences, whose values can be created with generators and through iteration
  • from the .NET namespace System.Collections.Generic.IEnumerable
  • seq<'T>는 .NET의 System.Collections.Generic.IEnumerable<T>의 F# 표현
  • 즉, 일반화된 시퀀스 타입 → 리스트, 배열, 집합 등과 유사하지만 지연 평가(lazy evaluation)가 가능함

List

A List is an ordered, immutable collection of elements of the same type

• Internally implemented as a Singly linked list

let x1 = []               // empty list
let x2 = [ 1; 2; 3; ]    // list with elements 1, 2, and 3
let x3 = [ 1 .. 1000 ]   // List with integers from 1 to 1000 as elements

// CONS → ::
let x = 0 :: [ 1; 2; 3; ]  // [ 0; 1; 2; 3; ]

// LIST → @
let x = [ 1; 2; 3; ] @ [ 4; 5; 6; ]  // [ 1; 2; 3; 4; 5; 6; ] 리스트 연결 (append)

// CAR → Head
let y = x.Head  // 1

// CDR → Tail
let y = x.Tail  // [ 2; 3; ]

Array

• Fixed-sized collection of mutable elements of the same type
• Supports fast random access. .NET의 System.Array에 기반함

let x1 = Array.empty                    // empty array
let x2 = [| 1; 2; 3; |]               // Array with elements 1, 2, and 3
let x3: int array = Array.zeroCreate 10 // array with 10 zeros

let x = [| 1; 2; 3; 4; 5; |]
let ele0 = array1[0]     // a = 1
let subx1 = array1[2..4] // array2 = [| 3; 4; 5; |]
let subx2 = array1[..1]  // array3 = [| 1; 2; |]  slicing
let subx3 = array1[3..]  // array4 = [| 4; 5; |]  slicing

• Slicing copy and return a new array (not change original array)

Sequences

A collection of elements of the same type, which support lazy evaluation

• Generated with range expressions

let x = seq {1..4};;   // generates seq [1; 2; 3; 4], ;; is used in interactive mode
let y = seq {0..10000000};;  // only the needed elements are generated

• Generation of sequence values is lazy

• Default stepsize is 1, but it can be any number

let seq1 = seq {1..2..7}
// Sets seq1 to [1; 3; 5; 7]

• Iterated with a for-in construct

let seq1 = seq {0..3..11};;
for value in seq1 do printfn "value = %d" value;;
// value = 0
// value = 3
// value = 6
// value = 9

• Iterators – not lazy for lists and arrays (sequences are lazy)

let cubes = seq {for i in 1..4 -> (i, i * i * i)};;
// Sets cubes to [(1, 1); (2, 8); (3, 27); (4, 64)]

Functions

• If named, defined with let

let x = a / b  // ← 매개변수 없는 함수처럼 작동

• No difference between a name defined with let and a function without parameters
• The extent of a function is defined by indentation. 함수 내부에서도 let을 중첩 사용 가능

let f =
  let pi = 3.14159
  let twoPi = 2.0 * pi;;  // 2 instead of 2.0 causes error
  twoPi;;

• Does not coerce numeric values (수치 연산 시 정수/실수 타입 명확히 지정해야 함)
• Names in functions can be outscoped, which ends their scope

let으로 같은 이름을 다시 정의하면 이전 변수의 스코프가 종료됨

let x4 =
  let x = x * x
  let x = x * x
  x;;

• The first let in the body of the function creates a new version of x; This terminates the scope of the parameter
• The second let in the body creates another x, Terminating the scope of the second x
• If lambda expressions, defined with fun

fun a b -> a / b
fun x y -> let swap (a, b) = (b, a) in swap (x, y)  // 람다 안에서 내부 함수 정의

• fun a b -> expr는 익명 함수이며, let 없이도 정의 가능
• 람다 내부에서도 let으로 지역 함수 정의 가능
• If a function is recursive, its definition must include the rec reserved word

F#에서 기본적으로 함수 이름은 내부에서 접근 불가 (자기 참조 금지)

let rec factorial x =
  if x <= 1 then 1
  else n * factorial(n − 1)

재귀 함수와 패턴 매칭

let rec factorial n =
  match n with
  | 0 -> 1
  | 1 -> 1
  | _ -> n * factorial (n - 1)

• rec 필수 → 재귀 가능
• match ... with → 다중 분기 시 가독성 및 안정성 향상
• _ → 기본값 또는 "그 외 모든 경우" 처리
• Currying is supported. If a function has multiple arguments, it is automatically treated as currying

F#은 기본적으로 함수에 인자가 여러 개 있어도 자동으로 커링 처리함

튜플 (a, b)을 하나의 인자로 받으면 커링이 되지 않음

let add (a:int) (b:int) = a + b
let add5 = add 5
let result = add5 3  // 8

// If want to prevent currying - Use tuple
let add1 a b = a + b
let add2 (a, b) = a + b

inline

inline 키워드와 다형성(polymorphism)을 이용해 함수 오버로딩을 흉내낼 수 있음

컴파일 타임에 함수 본문이 직접 삽입(inlined)됨. 덕분에 제네릭 타입 연산자 (+, * 등)가 타입 추론을 통해 다양한 타입에서 사용 가능해짐

let add1 a b = a + b
let result1 = add1 1 2
let result2 = add1 "dog" "cat"  // error! 문자열 + 는 지원 안됨

let inline add2 a b = a + b
let result3 = add2 1 2          // 3
let result4 = add2 "dog" "cat"  // "dogcat" 타입 추론 기반 연산 허용 → 오버로딩처럼 동작 가능

• Can mimic function overloading

Functions (collection)

iter: 주어진 함수를 리스트의 각 요소에 대해 실행 (반환값 없음)

let l1 = [1; 2; 3]
List.iter (fun x -> printf "%d " x) l1
List.iteri (fun i x -> printfn "Index %d: %d " i x) l1

map: 리스트의 각 요소에 함수를 적용하고, 그 결과를 새 리스트로 반환

let l1 = [1; 2; 3]
let r1 = List.map (fun x -> x + 1) l1   // [2; 3; 4]
let r2 = List.mapi (fun i x -> x + i) l1 // [1; 3; 5]

filter: 주어진 조건 함수(pred)를 각 요소에 적용하고, 결과가 true인 요소만 추출

let l1 = [1; 2; 3; 4]
let evenList = List.filter (fun x -> x % 2 = 0) l1  // [2; 4]

fold: 리스트의 각 요소를 누적자(acc)와 함께 처리하여 최종 결과 계산

• Results from the previous element are accumulated and applied. Need accumulator (need to set initial)

let sum list = List.fold (fun acc x -> acc + x) 0 list
let r1 = sum [1; 2; 3;]  // 6 (순서: ((0 + 1) + 2) + 3)

let reverse list = List.fold (fun acc x -> x::acc) [] list
let r2 = reverse [1; 2; 3;]  // [3; 2; 1]
// 순서: [] |> 1::[] → [1] |> 2::[1] → [2;1] |> 3::[2;1] → [3;2;1]

do: When we need to do it without saving the result. 반환값은 무시됨 (unit으로 처리됨)

do printf "Hello World"

Function Composition

let negate x = -1 * x
let square x = x * x

let temp = square 3    // 9
let result = negate temp  // -9
// Or:
let result = negate (square 3)  // -9

• Composition (>>): 함수 조합 연산자
• Builds a function that applies its left operand to a given parameter (a function) and then passes the result returned from the function to its right operand (another function)
• The F# expression (f >> g) x is equivalent to the mathematical expression g(f(x))

let composed = square >> negate
let result = composed 3  // 결과: -9 (square 3 = 9 → negate 9 = -9)

let inline (>>) f g x = g (f x)  // Forward composition
let inline (<<) f g x = f (g x)  // Reverse composition

let negateSquare = square >> negate
let result = negateSquare 3  // -9

Pipeline

let even values = List.filter (fun n -> n % 2 = 0) values
let mulFive values = List.map (fun n -> 5 * n) values

let combine1 values =
  let evens = List.filter (fun n -> n % 2 = 0) values
  let mulFives = List.map (fun n -> 5 * n) evens
  mulFives

• In fact, if it is clear that the previous result value is to be passed to value name in the next function, this way would be an unnecessary syntax
• Pipeline (|>): A binary operator that sends the value of its left operand to the last parameter of the call (the right operand)

let inline (|>) x f = f x
let inline (<|) f x = f x

• Used to chain function calls together

let myNums = [1; 2; 3; 4; 5]
let evensTimesFive = myNums
  |> List.filter (fun n -> n % 2 = 0)
  |> List.map (fun n -> 5 * n)
// The return value is [10; 20]

Insert sort

let rec insert n ls =
  match ls with
  | [] -> [n]
  | x::xs ->
    if n > x then x :: insert n xs
    else n :: ls;;

let rec insertSort ls =
  match ls with
  | [] -> []
  | x::xs -> insert x (insertSort xs);;

// insertSort [3; 1; 4; 2];;
// 결과: [1; 2; 3; 4]

Quicksort

let rec quicksort list =
  match list with
  | [] -> []
  | firstElem::otherElements ->
    let smallerElements =
      otherElements
      |> List.filter (fun e -> e < firstElem)
      |> quicksort
    let largerElements =
      otherElements
      |> List.filter (fun e -> e >= firstElem)
      |> quicksort
    smallerElements @ [firstElem] @ largerElements

Why F# is Interesting

• It builds on previous functional languages (ML, Haskell, OCaml 등 기존 함수형 언어들의 이론적/실용적 기반 위에 설계됨)
• It supports virtually all programming methodologies in widespread use today (함수형뿐 아니라 명령형, 객체지향, 데이터 흐름 기반 프로그래밍 등 여러 방식의 개발을 모두 지원함)
• It is the first functional language that is designed for interoperability with other widely used languages (널리 사용되는 언어(C#, VB.NET 등)들과의 .NET 기반 상호운용성이 뛰어남. 즉, F# 코드와 C# 코드를 섞어서 사용할 수 있음)
• At its release, it had an elaborate and well developed IDE and library of utility software (Visual Studio IDE 및 다양한 유틸리티 라이브러리와 함께 출시되어 실무에 바로 사용할 수 있는 환경을 제공함)

Support for Functional Programming in Primarily Imperative Languages

• Support for functional programming is increasingly creeping into imperative languages
  • 예시: 람다 표현식, 불변 변수, 스트림 API 등은 FP의 개념을 차용한 것임
• The most important restriction: Lack of support for higher-order functions
  • 고차 함수란, 함수를 인자로 받거나 함수로 반환하는 함수를 의미
  • 이 제약 때문에 진정한 함수형 프로그래밍 스타일을 구현하기 어렵다는 한계가 있음
• Although modern imperative languages support many functional features, they still primarily rely on mutable state and side effects

Anonymous functions (lambda expressions)

함수에 이름을 붙이지 않고 정의하는 방식 → 일회성 사용이나 고차 함수 인자로 넘길 때 유용함

• JavaScript: leave the name out of a function definition

function name (formal-parameters) {
  body
}

const square = function(x) {
  return x * x;
};
// function(x) { return x * x; } ← 이름이 없는 함수 정의

C#: (input-parameters) => expression

// i => (i % 2) == 0 (returns true or false depending on whether the parameter is even or odd)
List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
var evenNumbers = numbers.Where(i => i % 2 == 0).ToList();
// 결과: [2, 4]
// 여기서 Where는 고차 함수 (함수를 인자로 받는 함수), i => i % 2 == 0는 익명 함수 (람다)

• Python: lambda 매개변수들 : 표현식

f = lambda a, b: 2 * a - b
print(f(3, 1))  # 출력: 5

nums = [1, 2, 3, 4]
squares = list(map(lambda x: x * x, nums))
print(squares)  # 출력: [1, 4, 9, 16]

• Python supports the higher-order functions filter and map (often use lambda expressions as their first parameters)
  • filter(function, iterable): 주어진 함수의 조건을 만족하는 요소만 남김

list(filter(lambda x: x % 2 == 0, [1, 2, 3, 4, 5]))
# Returns [2, 4]

• map: iterable의 모든 요소에 함수를 적용한 결과를 반환

map(lambda x : x ** 3, [2, 4, 6, 8])
# Returns [8, 64, 216, 512]

이런 고차 함수는 함수를 값처럼 다룰 수 있는 함수형 프로그래밍의 특징

• Python supports partial function applications: 여러 개의 인자를 받는 함수 중 일부 인자를 미리 고정해 놓고, 나머지 인자만 나중에 받아서 호출하는 방식
• There are libraries for functional programming: functools, itertools, operator

from functools import partial

def add (x, y, z):
  return x + y + z

add5 = partial(add, 5)
add5(15)  # return 20

from operator import add
add5 = partial(add, 5)
add5(15)  # return 20

def multiply(x, y):
  return x * y

double = partial(multiply, 2)  # x를 2로 고정 (2배 함수)
numbers = [1, 2, 3, 4]
doubled = list(map(double, numbers))  # [2, 4, 6, 8]
print(doubled)

strings = ['apple', 'banana', 'kiwi', 'grape']
print(sorted(strings))  # ['apple', 'banana', 'grape', 'kiwi']

sort_by_length = partial(sorted, key=len)
print(sort_by_length(strings))  # ['kiwi', 'apple', 'grape', 'banana']

Ruby Blocks

• Are effectively subprograms that are sent to methods, which makes the method a higher order subprogram
• Ruby에서는 메서드가 block을 받으면, 그 block을 실행할 수 있음. 즉, 해당 메서드는 고차 함수(higher-order function)로 작동
• We can create blocks with { } or do ~ end. Block can be passed to method

3.times { |i| puts i }

3.times do |i|
  x = i * 2
  p x
end

위 코드에서 times 메서드는 블록을 받아서, i를 0부터 2까지 넘겨주고, 블록 내 코드를 실행

• Block을 사용하는 이유: 반복 제어를 간결하게 처리, 콜백 처리

def custom_each(array)
  for item in array
    yield(item)  # 넘겨받은 block 실행
  end
end

custom_each([1, 2, 3]) do |n|
  puts n * 10
end
# 출력: 10, 20, 30

여기서 yield는 메서드 안에서 block을 호출하는 키워드. block은 메서드 외부에서 정의되지만, 마치 메서드 안에 있는 것처럼 실행

A block can be converted to a subprogram object with lambda

times = lambda {|a, b| a * b}
x = times.(3, 4)  # sets x to 12

times5 = times.curry.(5)  # 첫 번째 인자를 5로 고정한 새로운 함수
x5 = times5.(3)           # sets x5 to 15 (두 번째 인자만 주면 결과 계산됨)

Comparing Functional and Imperative Languages

• Imperative Languages:
  • Complex semantics (상태 변화, 제어 흐름 중심)
  • Complex syntax (반복문, 대입문, 코드 블록 등)
  • Efficient execution (일반적으로 더 효율적임)
  • Concurrency is programmer designed (프로그래머가 직접 병렬 처리 설계)
  • 가변 상태(mutable state) 사용
  • 부수 효과 많음 (대입, 입출력 등)
• Functional Languages:
  • Simple semantics (상태 없는 계산, 표현식 중심)
  • Simple syntax (함수 중심, 표현식 기반)
  • Less efficient execution (상대적으로 덜 효율적임 (불변성, 재귀 등으로 인해))
  • Programs can automatically be made concurrent (자동 병렬화 가능성이 높음)
  • 불변 상태(immutable state) 지향
  • 부수 효과를 피함 (순수 함수 사용)

Summary

• Functional programming languages use function application, conditional expressions, recursion, and functional forms to control program execution
• Lisp began as a purely functional language and later included imperative features
• Scheme is a relatively simple dialect of Lisp that uses static scoping exclusively
• Common Lisp is a large Lisp-based language
• ML is a static-scoped and strongly typed functional language that uses type inference
• Haskell is a lazy functional language supporting infinite lists and set comprehension
• F# is a .NET functional language that also supports imperative and object-oriented programming
• Some primarily imperative languages now incorporate some support for functional programming
• Purely functional languages have advantages over imperative alternatives, but still are not very widely used