The Substring 구조

The Substring 구조

이 구조는 기반 문자열의 부분 문자열을 나타내는 substring 타입을 위한 유틸리티를 제공해요.

출처: 문서

본문

시놉시스 (Synopsis)

signature SUBSTRING
structure Substring :> SUBSTRING
where type substring = CharVectorSlice.slice
where type string = String.string
where type char = Char.char
structure WideSubstring :> SUBSTRING (* OPTIONAL *)
where type substring = WideCharVectorSlice.slice
where type string = WideString.string
where type char = WideChar.char

인터페이스 (Interface)

type substring
eqtype char
eqtype string
val sub : substring * int -> char
val size : substring -> int
val base : substring -> string * int * int
val extract : string * int * int option -> substring
val substring : string * int * int -> substring
val full : string -> substring
val string : substring -> string
val isEmpty : substring -> bool
val getc : substring -> (char * substring) option
val first : substring -> char option
val triml : int -> substring -> substring
val trimr : int -> substring -> substring
val slice : substring * int * int option -> substring
val concat : substring list -> string
val concatWith : string -> substring list -> string
val explode : substring -> char list
val isPrefix : string -> substring -> bool
val isSubstring : string -> substring -> bool
val isSuffix : string -> substring -> bool
val compare : substring * substring -> order
val collate : (char * char -> order)
-> substring * substring -> order
val splitl : (char -> bool)
-> substring -> substring * substring
val splitr : (char -> bool)
-> substring -> substring * substring
val splitAt : substring * int -> substring * substring
val dropl : (char -> bool) -> substring -> substring
val dropr : (char -> bool) -> substring -> substring
val takel : (char -> bool) -> substring -> substring
val taker : (char -> bool) -> substring -> substring
val position : string -> substring -> substring * substring
val span : substring * substring -> substring
val translate : (char -> string) -> substring -> string
val tokens : (char -> bool) -> substring -> substring list
val fields : (char -> bool) -> substring -> substring list
val app : (char -> unit) -> substring -> unit
val foldl : (char * 'a -> 'a) -> 'a -> substring -> 'a
val foldr : (char * 'a -> 'a) -> 'a -> substring -> 'a

설명 (Description)

sub (s, i)

full은 전체 문자열의 부분 문자열을 돌려줘요.

size s

substring·extract는 지정 범위 부분 문자열을 만들어요.

base ss

triml·trimr은 앞·뒤 일부를 잘라내요.

extract (s, i, NONE)

splitl·splitr·splitAt은 술어나 위치로 나눠요.

extract (s, i, SOME j)

isPrefix·isSubstring·isSuffix는 포함 관계를 검사해요.

substring (s, i, j)

첫 번째 형태는 s의 i번째 문자부터 문자열 끝까지의 부분 문자열, 즉 문자열 s[i..|s|-1]을 돌려줘요. 0 <= i <= |s|가 아니면 Subscript를 발생시켜요. 두 번째 형태는 인덱스 i에서 시작하는 크기 j의 부분 문자열, 즉 문자열 s[i..i+j-1]을 돌려줘요. i < 0이거나 j < 0이거나 |s| < i + j이면 Subscript를 발생시켜요. 정의되는 경우 i = |s|일 때 extract는 빈 부분 문자열을 돌려준다는 점에 유의하세요. 세 번째 형태는 부분 문자열 s[i..i+j-1], 즉 인덱스 i에서 시작하는 크기 j의 부분 문자열을 돌려줘요. extract(s, i, SOME j)와 동등해요. 유효한 인자에 대해 base o substring이 항등 함수여야 한다고 요구해요. 구현 참고: 이 함수들의 구현은 Overflow 예외가 발생하지 않도록 경계 검사를 수행해야 해요.

full s

전체 문자열 s를 나타내는 부분 문자열을 만들어요. substring(s, 0, String.size s)와 동등해요.

string s

부분 문자열에 해당하는 문자열 값을 만들어요. 해당 String 구조의 String.substring o base와 동등해요.

isEmpty s

s의 크기가 0이면 true를 돌려줘요.

getc s

s의 첫 번째 문자와 나머지 부분 문자열을 돌려줘요. s가 비어 있으면 NONE을 돌려줘요.

first s

s의 첫 번째 문자를 돌려줘요. s가 비어 있으면 NONE을 돌려줘요.

triml k s

trimr k s

이 함수들은 부분 문자열 s의 왼쪽(각각 오른쪽)에서 k개 문자를 제거해요. k가 부분 문자열의 크기보다 크면 빈 부분 문자열을 돌려줘요. 구체적으로 부분 문자열 ss = substring(s, i, j)이고 k <= j일 때 다음이 성립해요:

triml k ss = substring(s, i+k, j-k)
trimr k ss = substring(s, i, j-k)

k < 0이면 Subscript 예외가 발생해요. 이 예외는 triml k나 trimr k를 평가할 때 발생해요.

slice (s, i, SOME m)

slice (s, i, NONE)

이 함수들은 i번째 문자에서 시작하는 s의 부분 문자열을 돌려줘요. 전자의 경우 결과 부분 문자열의 크기는 m이에요. 그렇지 않으면 크기는 |s| - i예요. 첫 번째 경우 인자가 유효하려면 0 <= i, 0 <= m, i + m <= |s|를 만족해야 해요. 두 번째 경우 0 <= i <= |s|를 만족해야 해요. 인자가 유효하지 않으면 Subscript 예외가 발생해요.

concat l

l에 있는 부분 문자열들을 이어 붙인 문자열을 만들어요. String.concat o (List.map string)과 동등해요. 모든 크기의 합이 문자열 타입의 해당 maxSize보다 크면 Size를 발생시켜요.

concatWith s l

리스트 l에 있는 부분 문자열들을 문자열 s를 구분자로 사용해 이어 붙여 돌려줘요. 결과 문자열의 크기가 문자열 타입의 maxSize보다 크면 Size를 발생시켜요.

explode s

부분 문자열을 구성하는 문자들의 리스트를 돌려줘요. String.explode (string s)와 동등해요.

isPrefix s ss

isSubstring s ss

isSuffix s ss

이 함수들은 문자열 s가 부분 문자열 ss의 접두사, 부분 문자열, 접미사(각각)이면 true를 돌려줘요. 이 함수들은 STRING의 같은 이름 버전과 동등해요. 예를 들어 isPrefix s ss는 String.isPrefix s (string ss)와 같아요.

compare (s, t)

기본 문자 비교 함수를 사용해 두 부분 문자열을 사전식으로 비교해요. 다음과 동등해요:

String.compare (string s, string t)

collate f (s, t)

문자 비교 함수 f를 사용해 두 부분 문자열을 사전식으로 비교해요. 다음과 동등해요:

String.collate f (string s, string t)

splitl f s

splitr f s

이 함수들은 술어 f를 만족하지 않는 첫 번째 문자를 찾기 위해 s를 왼쪽에서 오른쪽으로(각각 오른쪽에서 왼쪽으로) 스캔해요. 부분 문자열을 그 문자까지의 구간과 나머지로 나눈 쌍 (ls, rs)을 돌려줘요. ls는 나눔의 왼쪽, rs는 오른쪽이에요. 예를 들어 문자 a와 c가 술어를 만족하고 문자 X는 만족하지 않으면, 부분 문자열 aaaXbbbbXccc에서 이 함수들은 다음과 같이 동작해요:

splitl   :           aaa         XbbbbXccc
splitr   :           aaaXbbbbX   ccc

splitAt (s, i)

부분 문자열 쌍 (ss, ss')을 돌려줘요. 여기서 ss는 s의 처음 i개 문자를, ss'는 나머지를 담아요. 0 <= i <= size s라고 가정해요. 그렇지 않으면 Subscript를 발생시켜요.

dropl f s

dropr f s

takel f s

taker f s

이 루틴들은 부분 문자열 s에서 술어 p를 만족하지 않는 첫 번째 문자를 검색해요. dropl과 takel 함수는 왼쪽에서 오른쪽으로(즉 문자 인덱스 증가 순서) 스캔하고, dropr과 taker는 오른쪽에서 스캔해요. drop 함수들은 술어를 만족하는 문자들로 이루어진 최대 부분 문자열을 버리고, take 함수들은 그런 최대 부분 문자열을 돌려줘요. 이 함수들은 split 연산으로 정의할 수 있어요:

takel p s = #1(splitl p s)
dropl p s = #2(splitl p s)
taker p s = #2(splitr p s)
dropr p s = #1(splitr p s)

position s ss

부분 문자열 ss를 부분 문자열 쌍 (pref, suff)로 나눠요. 여기서 suff는 s를 접두사로 갖는 ss의 가장 긴 접미사이고, pref는 suff 앞에 오는 ss의 접두사예요. 더 정확히 m을 s의 크기라 하고 ss가 부분 문자열 (s', i, n)에 해당한다고 하자. s = s'[k..k+m-1]인 최소 인덱스 k >= i가 있으면 suff는 (s', k, n+i-k)에, pref는 (s', i, k-i)에 해당해요. 그런 k가 없으면 suff는 (s', i+n, 0)에 해당하는 빈 부분 문자열이고 pref는 (s', i, n), 즉 ss 전체에 해당해요.

span (ss, ss')

접두사 ss, 접미사 ss', 그리고 기본 문자열의 중간 문자 전체로 이루어진 부분 문자열을 만들어요. ss와 ss'가 같은 기본 문자열의 부분 문자열이 아니거나 ss의 시작이 ss'의 끝보다 오른쪽에 있으면 Span을 발생시켜요. 더 정확히 다음을 가지면 span은 s = s'이고 i'+n' >= i일 때 substring(s, i, (i'+n')-i)를 돌려주고, 그렇지 않으면 Span을 발생시켜요. 이렇게 하면 ss'가 ss의 왼쪽에서 시작하거나 ss가 ss'의 오른쪽에서 끝나는 것을 막지 않아요. 이 함수를 쓰면 여러 조각으로 부분 문자열을 스캔한 다음 조각들을 합칠 수 있어요. 예를 들어 같은 URL 문자열이 주어졌을 때 프로토콜과 호스트 ("http://www.standardml.org")를 스캔하려면 이렇게 쓸 수 있어요:

val (s, i, n) = base ss
val (s', i', n') = base ss'

"http://www.standardml.org/Basis/overview.html"

local
open Substring
in
fun protoAndHost url = let
fun notc (c : char) = fn c' => c <> c'
val (proto,rest) = splitl (notc #":") (full url)
val host = takel (notc #"/") (triml 3 rest)
in
span (proto, host)
end
end

구현 참고: 같은 기본 문자열에서 파생된 부분 문자열에 적용할 때 문자열 평등 검사는 상수 시간이어야 해요. 포인터 검사를 먼저 하고, 그것이 실패할 때만 문자열을 문자별로 검사하면 이를 달성할 수 있어요.

translate f s

s의 모든 문자에 왼쪽에서 오른쪽으로 f를 적용하고 결과를 이어 붙여 돌려줘요. String.concat(List.map f (explode s))와 동등해요.

tokens f s

fields f s

이 함수들은 부분 문자열을 왼쪽에서 오른쪽으로 토큰 또는 필드 리스트로 분해해요. 토큰은 구분자를 포함하지 않는 비어 있지 않은 최대 부분 문자열이에요. 필드는 구분자를 포함하지 않는 (아마 빈) s의 최대 부분 문자열이에요. 두 경우 모두 구분자는 술어 f를 만족하는 문자예요. 두 토큰 사이에는 구분자가 여러 개 있을 수 있는 반면, 두 필드 사이에는 정확히 하나의 구분자가 있어요. 예를 들어 유일한 구분자가 문자 #"|"라면, 부분 문자열 "|abc||def"는 "abc"와 "def" 두 토큰을 포함하는 반면 "", "abc", "", "def" 네 필드를 포함해요.

app f s

s의 각 문자에 왼쪽에서 오른쪽으로 f를 적용해요. List.app f (explode s)와 동등해요.

foldl f a s

foldr f a s

이 함수들은 부분 문자열 s 위로 함수 f를 왼쪽에서 오른쪽으로 그리고 오른쪽에서 왼쪽으로 각각 a 값에서 시작해 접어요. List의 같은 이름 함수들의 대응물이에요. 특히 각각 다음과 동등해요:

List.foldl f a (explode s)
List.foldr f a (explode s)
```## 더 알아보기 (Learn more)

-