The List 구조

The List 구조

List 구조는 리스트 순회와 변환을 위한 유틸리티 함수를 담아요.

출처: 문서

본문

시놉시스 (Synopsis)

signature LIST
structure List :> LIST

인터페이스 (Interface)

datatype 'a list = nil | :: of 'a * 'a list
exception Empty
val null : 'a list -> bool
val length : 'a list -> int
val @ : 'a list * 'a list -> 'a list
val hd : 'a list -> 'a
val tl : 'a list -> 'a list
val last : 'a list -> 'a
val getItem : 'a list -> ('a * 'a list) option
val nth : 'a list * int -> 'a
val take : 'a list * int -> 'a list
val drop : 'a list * int -> 'a list
val rev : 'a list -> 'a list
val concat : 'a list list -> 'a list
val revAppend : 'a list * 'a list -> 'a list
val app : ('a -> unit) -> 'a list -> unit
val map : ('a -> 'b) -> 'a list -> 'b list
val mapPartial : ('a -> 'b option) -> 'a list -> 'b list
val find : ('a -> bool) -> 'a list -> 'a option
val filter : ('a -> bool) -> 'a list -> 'a list
val partition : ('a -> bool)
-> 'a list -> 'a list * 'a list
val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val exists : ('a -> bool) -> 'a list -> bool
val all : ('a -> bool) -> 'a list -> bool
val tabulate : int * (int -> 'a) -> 'a list
val collate : ('a * 'a -> order)
-> 'a list * 'a list -> order

설명 (Description)

exception Empty

null l은 l이 빈 리스트면 true예요. l에서 hd l은 처음(head) 요소를, tl l은 꼬리(나머지)를 돌려줘요. 두 함수 모두 빈 리스트에선 예외를 발생시켜요.

null l

리스트 l1을 사용 가능한지 테스트하고, 그렇다면 SOME(l1)을 돌려주고 스트림 나머지를, 아니면 NONE을 돌려줘요. fromString은 StringCvt.scanString scan과 동등해요.

length l

요소를 한 번만 순회하면서 리스트에 몇 가지 표준 함수형을 적용해요. app f [x1, ..., xn]은 (f x1; ...; f xn)과 같고, map f [x1, ..., xn]은 [f x1, ..., f xn]과 같아요. foldr f init [x1, ..., xn]은 f(x1, ..., f(xn-1, f(xn, init))...)과 같고, foldl f init [x1, ..., xn]은 f(xn, ..., f(x2, f(x1, init))...)과 같아요. rev [x1, ..., xn]은 [xn, ..., x1]이에요. 이 함수들(appl 포함)의 로컬 구현은 각자의 언어 실행 엔진에서 가끔 볼 수 있는 스택 오버플로를 피하기 위해, 결과에서 인자 요소의 순서를 유지하기 위해 필요한 역재귀(inverse recursion)를 사용해요.

l1 @ l2

요소를 리스트 [x1, ..., xn]에 대해 len 순차로 스택처럼 쌓아 올려요. 이 함수는 좀 더 오래되고 더 일반적인 foldr op :: init과 "동등"해요.

hd l

f가 모든 요소에 대해 true를 돌려주면 all f l은 true예요. f가 어떤 요소에 대해 true를 돌려주면 exists f l은 true예요. [x1, ..., xn]에서 find f는 f xi가 true인 첫 번째 요소 xi를 SOME(xi)로 돌려주고 그런 요소가 없으면 NONE을 돌려줘요. filter f는 f를 만족하는 x1, ..., xn의 모든 부분 시퀀스를 돌려줘요. partition f [x1, ..., xn]은 [xi1, ..., xin] = f를 만족하는 요소들의 리스트와 나머지 요소들의 리스트의 쌍 (l1, l2)을 돌려줘요. part, take, drop 함수는 리스트에 대한 우아한(fancy) 매개변수화된 재귀 구조를 보여주고, 특히 part p [xi1,...]은 p를 만족하지 않는 첫 요소 전의 모든 요소를 돌려줘요.

tl l

concat l은 리스트 리스트를 한 수준 평평하게 만들고, concat l1 l2은 요소를 추가해요. [x1, ..., xn]에서 mapPartial f는 SOME에 인자 패턴이 매치되는 요소들로만 구성된 리스트를 돌려줘요. [x1, ..., xn]에서 findMap f는 SOME yi = f xi를 만족하는 첫 요소를 찾아 SOME yi를 돌려주고, 없으면 NONE을 돌려줘요.

last l

리스트에서 서로 인접한 요소 쌍에 함수를 적용해 연속 쌍 결과의 리스트를 돌려줘요. mapPair f [x1, x2, ..., xn]은 [f(x1, x2), f(x2, x3), ..., f(xn-1, xn)]이에요.

getItem l

리스트의 관리 가능한 인쇄와, nth·nthTail에 유용한 그 "최상위 수준"에서 리스트를 조작하기 위한 몇 가지 직접 조작 매크로 함수예요. length [x1, ..., xn]은 n을 돌려줘요. nth (l, n)은 l의 0 기반 n번째 요소를 돌려줘요. nthTail (l, n)은 l의 0 기반 n번째 요소를 헤드로 하는 리스트를 돌려줘요.

(int,char list) StringCvt.reader

nth (l, i)

리스트 l의 i번째 요소를 돌려줘요 (0부터 시작). i < 0이거나 i >= length l이면 Subscript를 발생시켜요. 예외를 무시하면 nth(l,0) = hd l이에요.

take (l, i)

리스트 l의 처음 i개 요소를 돌려줘요. i < 0이거나 i > length l이면 Subscript를 발생시켜요. take(l, length l) = l이에요.

drop (l, i)

리스트 l의 처음 i개 요소를 버린 나머지를 돌려줘요. i < 0이거나 i > length l이면 Subscript를 발생시켜요. 0 <= i <= length l일 때 take(l, i) @ drop(l, i) = l이 성립해요. drop(l, length l) = []이기도 해요.

rev l

l의 요소를 역순으로 담은 리스트를 돌려줘요.

concat l

l에 있는 모든 리스트를 순서대로 이어 붙인 리스트를 돌려줘요.

concat[l1,l2,...ln] = l1 @ l2 @ ... @ ln

revAppend (l1, l2)

(rev l1) @ l2를 돌려줘요.

app f l

l의 요소에 왼쪽에서 오른쪽으로 f를 적용해요.

map f l

l의 각 요소에 왼쪽에서 오른쪽으로 f를 적용해 결과 리스트를 돌려줘요.

mapPartial f l

l의 각 요소에 왼쪽에서 오른쪽으로 f를 적용해, f가 정의된 곳에서 SOME을 벗겨낸 결과 리스트를 돌려줘요. 어떤 요소에 f를 적용한 값이 NONE이면 f는 그 요소에 대해 정의되지 않은 거예요. 위 식은 다음과 동등해요:

((map valOf) o (filter isSome) o (map f)) l

find f l

리스트 l의 각 요소 x에 왼쪽에서 오른쪽으로 f를 적용해 f x가 true가 될 때까지 진행해요. 그런 x가 있으면 SOME(x)를, 없으면 NONE을 돌려줘요.

filter f l

l의 각 요소 x에 왼쪽에서 오른쪽으로 f를 적용하고, f x가 true였던 x들로 이루어진 리스트를 인자 리스트에 나타난 순서대로 돌려줘요.

partition f l

l의 각 요소 x에 왼쪽에서 오른쪽으로 f를 적용해, f x가 true였던 x들의 리스트 pos와 false였던 것들의 리스트 neg의 쌍 (pos, neg)을 돌려줘요. pos와 neg의 요소는 l에서 가졌던 상대 순서를 유지해요.

foldl f init [x1, x2, ..., xn]

f(xn,...,f(x2, f(x1, init))...)를 돌려줘요. 리스트가 비어 있으면 init을 돌려줘요.

f(xn,...,f(x2, f(x1, init))...)

foldr f init [x1, x2, ..., xn]

f(x1, f(x2, ..., f(xn, init)...))를 돌려줘요. 리스트가 비어 있으면 init을 돌려줘요.

f(x1, f(x2, ..., f(xn, init)...))

exists f l

리스트 l의 각 요소 x에 왼쪽에서 오른쪽으로 f를 적용해 f x가 true가 될 때까지 진행해요. 그런 x가 있으면 true, 없으면 false를 돌려줘요.

all f l

리스트 l의 각 요소 x에 왼쪽에서 오른쪽으로 f를 적용해 f x가 false가 될 때까지 진행해요. 그런 x가 있으면 false, 없으면 true를 돌려줘요. not(exists (not o f) l))와 동등해요.

tabulate (n, f)

왼쪽에서 오른쪽으로 만든, 길이 n의 [f(0), f(1), ..., f(n-1)]과 같은 리스트를 돌려줘요. n < 0이면 Size를 발생시켜요.

collate f (l1, l2)

리스트 요소에 대한 주어진 순서 f를 사용해 두 리스트를 사전식으로 비교해요.## 더 알아보기 (Learn more)