[OSSU] <Programming Language, Part A> / Week2

 

(* Syntax : 
if e1 then e2 else e3
where if, then, else are keywords and
e1, e2, e3 are subexpressions

* Type-checking : 
first e1 : bool
e2, e3 : can have any type
but they must have same type
the tye of the entire expressions is also same

* Evaluation rules :
first evaluate e1 to value call it v1
if it's true, evaluate e2, else e3 and that result is the whole expression's result.*)

 

 

---

 

| Errors

 

 

 

 

 

tuples, lists

 

list 는 같은 type만을 가질 수 있다 

6 :: [3, 4]

= [6, 3, 4]

 

[6] :: [[3, 4]]

= [[6], [3,4]]

 

 

list끼리 합치는 함수 @ 

null e : e가 빈 리스트면 true 

 

 

 

 

hd e : 맨 앞 원소

tl e : 맨 뒤 원소

 

 

| LET ,  IN (binding, scoping)

fun silly1 (z : int) =
    let val x = if z > 0 then z else 34
	val y = x+z+9
    in
	if x > y then x*2 else y*y
    end

fun silly2 () =
    let val x = 1 
    in 
	(let val x = 2 in x+1 end) + (let val y = x+2 in y+1 end)
    (* x+1 = 3)                   (y+1 = 3)*)
    end

 

 

| Efficient Algorithm (Big-O)

 

 

(* badly named: evaluates to 0 on empty list *)
fun bad_max (xs : int list) =
    if null xs
    then 0
    else if null (tl xs)
    then hd xs
    else if hd xs > bad_max(tl xs)
    then hd xs
    else bad_max(tl xs)

(* badly named: evaluates to 0 on empty list *)
fun good_max (xs : int list) =
    if null xs
    then 0
    else if null (tl xs)
    then hd xs
    else
	(* for style, could also use a let-binding for (hd xs) *)
	let val tl_ans = good_max(tl xs)
	in
	    if hd xs > tl_ans
	    then hd xs
	    else tl_ans

 

안좋은 알고리즘은 숫자마다 계속 bad_max를 부르니까 기하

 

급수적으로 연산량이 늘어난다 (특히 최대값이 리스트 맨 위에 있을 때)

좋은 알고리즘은 값을 아예 하나의 변수에 저장한다.

 

 

빈 리스트에 대해서도 if null list, then - else -이거 말고도

 

(* better: returns an int option *)
fun max1 (xs : int list) =
    if null xs
    then NONE
    else 
	let val tl_ans = max1(tl xs)
	in if isSome tl_ans andalso valOf tl_ans > hd xs
	   then tl_ans
	   else SOME (hd xs)
	end

base case : 빈 리스트일 경우

그 외 : 1번 과 그 나머지의 max를 비교

           그 나머지가 빈게 아니고, 그 나머지의 max가 1번보다 크면 -> 답은 tl_ans

          그 둘 중에 하나라도 아니면 (비엇거나, 1번이 크면) -> 답은 1번

 

 

fun max2 (xs : int list) =
    if null xs
    then NONE
    else let (* fine to assume argument nonempty because it is local *)
	(* int list -> int *)
	fun max_nonempty (xs : int list) =
		if null (tl xs) (* xs better not be [] *)
		then hd xs
		else let val tl_ans = max_nonempty(tl xs)
		     in
			 if hd xs > tl_ans
			 then hd xs
			 else tl_ans
		     end
	in
	    SOME (max_nonempty xs)
	end

 

base case : 비엇으면 none

max_nonempty

1개짜리 리스트면 1번

아니면 뒤에 애들과 앞의 애들 비교

 

 

 

| Boolean

e1 andalso e2 에서

e1이 false면 e2는 보지도 않고 바로 전체가 false로 들어간다.

 

orelse면 e1이 true일때 e2는 보지도 않고 넘어가고, 아니면 e2까지 확인한다

 

 

 

 

 

e 자체만 쓸 것!!! 그 자체로 true, false가 판별난다 !! 

 

 

Real(float), Int 끼리는 비교할 수 없다. 하나를 바꿔줘야 한다

Real.fromInt 2 ; 2.0 (Int를 real로 바꿔준다)

그리고 real 끼리는 =, <> 비교할 수 없다. 

 

 

| Alias

 

복사하는거다. x,y가 바뀌면 z도 바뀌게 되는 것 

ML에서는 계속 alias를 쓰기 때문에 신경 안써도 되는데, 다른 언어에서는 copy를 만드는건지 alias인지를 계속 신경써줘야한다 (JAVA)