Clojure 데이터 구조

Clojure 데이터 구조 (Data Structures)

Clojure는 매우 풍부한 데이터 구조 세트를 갖추고 있어요. 그런데 여기서 중요한 건 각각의 구조가 아니라, 그것들이 공통으로 공유하는 성질이에요. 이 공통점을 먼저 짚고 나면 나머지 구조들은 자연스럽게 이해가 돼요.

출처: Clojure 공식문서

본문

모든 데이터 구조가 공유하는 성질

Clojure의 데이터 구조들은 다음 성질을 함께 나눠 가져요.

불변(immutable) 이에요.
읽을 수 있고(read-able), equals 구현에서 올바른 값 동등성(equality) 의미론을 지원해요.
좋은 해시 값(hash) 을 제공해요.
여기에 더해, 컬렉션(collection)들은:
- 인터페이스를 통해 조작돼요.
- 시퀀싱(sequencing) 을 지원해요.
- 영속적(persistent) 조작을 지원해요.
- 메타데이터(metadata) 를 지원해요.
- java.lang.Iterable을 구현해요.
- java.util.Collection 또는 java.util.Map의 비선택(읽기 전용) 부분을 구현해요.

nil

nil은 Clojure의 어떤 데이터 타입에서도 가능한 값이에요. 그 값은 Java의 null과 같아요. Clojure의 조건 시스템은 nil과 false를 중심으로 돌아가는데, 조건 검사에서 nil과 false는 논리적 거짓(logical falsity) 을 나타내고, 그 외의 모든 것은 논리적 참이에요. 거기에 더해 nil은 시퀀스 프로토콜에서 시퀀스의 끝(end-of-sequence)을 알리는 센티널(sentinel) 값으로도 쓰여요.

숫자 (Numbers)

Clojure는 기본적으로 JVM 원시(primitive) 값을 온전히 지원해요. 그래서 숫자를 다루는 코드를 자연스럽게(idiomatic하게) 쓰면서도 높은 성능을 유지할 수 있어요.

Clojure는 또 java.lang.Number에서 파생된 Java 박싱(boxed) 숫자 타입 — BigInteger, BigDecimal — 과 자기만의 Ratio(유리수) 타입도 지원해요. 여기에 몇 가지 특별한 처리가 있어요.

Longs

기본적으로 Clojure는 자연수(natural number)를 Java의 long 원시 타입 인스턴스로 다뤄요. 그런데 원시 정수 연산의 결과가 원시 값에 담기엔 너무 커지면, java.lang.ArithmeticException이 던져져요. 이런 상황을 위해 Clojure는 아포스트로피(')가 붙은 대체 산술 연산자를 제공해요 — +', -', *', inc', dec'가 있어요. 이 연산자들은 오버플로(overflow)가 나면 자동으로 BigInt로 승격(promote) 되지만, 일반 산술 연산자보다는 효율이 떨어져요.

Ratio

Ratio는 정수 사이의 비율(유리수) 을 나타내요. 정수끼리 나눗셈을 했는데 정수로 줄어들지 않으면, 부동소수점이나 잘림(truncated) 값 대신 ratio가 결과로 나와요 — 즉 22/7은 22/7로 남아요.

전염 (Contagion)

BigInt와 부동소수점 타입은 연산을 넘어 "전염(contagious)" 돼요. 다시 말해, BigInt가 포함된 정수 연산의 결과는 BigInt가 되고, double이나 float가 포함된 연산의 결과는 double이 돼요.

BigInt · BigDecimal 리터럴

BigInt와 BigDecimal의 숫자 리터럴은 접미사 N과 M 으로 구분해요.

예시 표현식	반환값
`(== 1 1.0 1M)`	`true`
`(/ 2 3)`	`2/3`
`(/ 2.0 3)`	`0.6666666666666666`
`(map #(Math/abs %) (range -3 3))`	`(3 2 1 0 1 2)`
`(class 36786883868216818816N)`	`clojure.lang.BigInt`
`(class 3.14159265358M)`	`java.math.BigDecimal`

숫자 관련 함수

계산: + - * / inc dec quot rem min max
자동 승격 계산: +' -' *' inc' dec'
비교: == < <= > >= zero? pos? neg?
비트 연산: bit-and bit-or bit-xor bit-not bit-shift-right bit-shift-left
유리수: numerator denominator
형변환: int bigdec bigint double float long num short

문자열 (Strings)

Clojure의 문자열은 Java 문자열이에요. 그리고 Clojure 문자열은 Java 메서드를 직접 호출할 수 있어요.

user=> (map (fn [x] (.toUpperCase x)) (.split "Dasher Dancer Prancer" " "))
("DASHER" "DANCER" "PRANCER")

문자 (Characters)

Clojure의 문자는 Java Character예요.

키워드 (Keywords)

키워드는 자기 자신으로 평가되는 상징적 식별자(symbolic identifier) 예요. 덕분에 아주 빠른 동등성 검사를 제공해요. 심볼과 마찬가지로 이름과 선택적인 네임스페이스를 가지며, 둘 다 문자열이에요. 맨 앞의 :는 네임스페이스나 이름에 포함되지 않아요.

키워드는 인자 하나(맵)와 선택적 인자 하나(기본값)를 받는 IFn의 invoke()를 구현해요. 예를 들어 (:mykey my-hash-map :none)은 (get my-hash-map :mykey :none)과 같은 뜻이에요.

키워드 관련 함수

keyword keyword?

심볼 (Symbols)

심볼은 보통 다른 무엇인가를 가리키는 데 쓰는 식별자예요. 프로그램 폼(form)에서 함수 파라미터, let 바인딩, 클래스 이름, 클래스 멤버, 전역 var를 가리키는 데 쓰여요. 이름과 선택적 네임스페이스를 가지며 둘 다 문자열이고, 메타데이터를 가질 수 있어요.

심볼도 키워드처럼 인자 하나(맵)와 선택적 기본값 인자를 받는 IFn의 invoke()를 구현해요. 예를 들어 ('mysym my-hash-map :none)은 (get my-hash-map 'mysym :none)과 같은 뜻이에요.

심볼 관련 함수

symbol symbol? gensym — 그리고 리더(reader) 매크로의 # 접미사도 함께 보면 좋아요.

컬렉션 (Collections)

Clojure 컬렉션은 전부 불변(immutable) 이면서 영속적(persistent) 이에요. 특히 컬렉션은 구조 공유(structural sharing) 를 이용해 '수정된' 버전을 효율적으로 만들 수 있고, 모든 성능 보장이 영속적 사용을 기준으로 잡혀 있어요. 그래서 컬렉션은 효율적이면서 본질적으로 스레드 안전(thread-safe) 해요.

컬렉션은 추상(abstraction)으로 표현되고, 이를 구체적으로 구현한 실체(realization)는 하나 이상일 수 있어요. 특히 '수정' 연산은 새 컬렉션을 만들어내므로, 새 컬렉션은 원본과 같은 구체 타입이 아닐 수 있지만, 같은 논리적(인터페이스) 타입은 유지해요.

모든 컬렉션은 크기를 구하는 count, '추가'를 위한 conj, 그리고 컬렉션 전체를 훑는 시퀀스를 얻는 seq를 지원해요. 다만 각 타입마다 구체적인 동작은 조금씩 달라요.

컬렉션이 seq를 지원하기 때문에, 모든 시퀀스 함수를 어떤 컬렉션에서든 쓸 수 있어요.

Java 컬렉션 해시

Java 컬렉션 인터페이스는 List, Set, Map의 hashCode() 값을 계산하는 알고리즘을 규정해요. Clojure 컬렉션은 hashCode() 구현에서 이 규격을 모두 따릅니다.

Clojure 컬렉션 해시

Clojure는 컬렉션(과 다른 타입)에 더 좋은 해시 성질을 주는 자체 해시 계산을 제공하는데, 이를 hasheq 값이라고 불러요.

IHashEq 인터페이스는 hasheq() 함수를 제공해 hasheq 값을 얻는 컬렉션을 표시해요. Clojure에서 hash 함수로 hasheq 값을 계산할 수 있어요.

순서가 있는 컬렉션(vector, list, seq 등)은 다음 알고리즘으로 hasheq를 계산해야 해요. 여기서 unchecked-add-int와 unchecked-multiply-int를 써서 정수 오버플로 계산을 얻는 점을 눈여겨보세요.

(defn hash-ordered [collection]
  (-> (reduce (fn [acc e] (unchecked-add-int
                            (unchecked-multiply-int 31 acc)
                            (hash e)))
              1
              collection)
      (mix-collection-hash (count collection))))

순서가 없는 컬렉션(map, set)은 다음 알고리즘을 사용해요. map 항목(entry)은 키와 값의 순서 있는 컬렉션으로 취급돼요. 여기선 unchecked-add-int가 정수 오버플로 계산에 쓰여요.

(defn hash-unordered [collection]
  (-> (reduce unchecked-add-int 0 (map hash collection))
      (mix-collection-hash (count collection))))

mix-collection-hash 알고리즘은 구현 세부사항이라 바뀔 수 있어요.

리스트 (Lists, IPersistentList)

리스트는 컬렉션이고, ISeq 인터페이스를 직접 구현해요. (빈 리스트도 ISeq를 구현하지만, 빈 시퀀스에 대해 seq 함수는 항상 nil을 반환해요.) count는 O(1)이고, conj는 항목을 리스트 맨 앞에 놓아요.

리스트 관련 함수

리스트 만들기: list list*
리스트를 스택처럼 다루기: peek pop
리스트 확인하기: list?

벡터 (Vectors, IPersistentVector)

벡터는 연속된 정수로 인덱스된 값들의 컬렉션이에요. 벡터는 log32N 단계로 인덱스로 항목에 접근할 수 있어요. count는 O(1)이고, conj는 항목을 벡터 맨 끝에 놓아요. 벡터는 또 항목을 역순으로 돌려주는 rseq를 지원해요.

벡터는 인자 하나를 받는 IFn의 invoke()를 구현하는데, 그 인자를 인덱스로 간주해 마치 nth처럼 자기 자신에서 찾아요. 그래서 벡터는 자기 인덱스의 함수라고 할 수 있어요. 벡터 비교는 먼저 길이로 하고, 그다음 각 요소를 순서대로 비교해요.

벡터 관련 함수

벡터 만들기: vector vec vector-of
벡터 확인하기: get nth peek rseq vector?
벡터 '변경': assoc pop subvec replace

맵 (Maps, IPersistentMap)

맵은 키를 값에 매핑하는 컬렉션이에요. 두 종류가 제공되는데, 해시 맵(hashed) 과 정렬 맵(sorted) 이에요. 해시 맵은 hashCode와 equals를 올바르게 지원하는 키가 필요하고, 정렬 맵은 Comparable을 구현하거나 Comparator 인스턴스인 키가 필요해요. 해시 맵은 정렬 맵보다 빠른 접근(log32N 대 logN)을 제공하지만, 정렬 맵은, 말 그대로, 정렬돼 있어요. count는 O(1)이에요.

conj는 항목으로 또 다른(단일 항목일 수 있는) 맵을 기대하고, 기존 맵에 그 항목들을 더한 새 맵을 반환해요. 이때 기존 항목을 덮어쓸 수도 있어요. conj는 또 MapEntry나 두 항목(키와 값)의 벡터도 받아요. seq는 키/값 쌍인 맵 항목(entry)들의 시퀀스를 반환해요. 정렬 맵은 항목을 역순으로 돌려주는 rseq도 지원해요.

맵은 인자 하나(키)와 선택적 기본값 인자를 받는 IFn의 invoke()를 구현해요. 즉 맵은 자기 키의 함수예요. nil 키와 값은 허용돼요.

맵 관련 함수

새 맵 만들기: hash-map sorted-map sorted-map-by
맵 '변경': assoc dissoc select-keys merge merge-with zipmap
맵 확인하기: get contains? find keys vals map?
맵 항목 확인하기: key val

StructMap

참고: StructMap을 쓰는 대부분의 경우, 이제는 레코드(records) 를 쓰는 게 더 나아요.

많은 맵 인스턴스가 같은 기본 키 집합을 공유하는 경우가 있어요 — 다른 언어에서 맵을 struct나 object로 쓸 때 그렇죠. StructMap은 키 정보를 효율적으로 공유하면서, 선택적으로 성능이 향상된 접근자(accessor) 도 제공해 이 사용법을 지원해요.

StructMap은 모든 면에서 맵이에요 — 같은 함수 집합을 지원하고, 다른 모든 맵과 상호운용되며, 영속적으로 확장 가능해요(즉 struct map이 기본 키에만 국한되진 않아요). 유일한 제한은 기본 키 중 하나로부터 struct map을 dissoc(제거)할 수 없다는 것이에요. struct map은 기본 키를 순서대로 유지해요.

StructMap은 먼저 create-struct나 defstruct로 구조 기반(struct basis) 객체를 만들고, 그다음 struct-map이나 struct로 인스턴스를 만들어 사용해요.

(defstruct desilu :fred :ricky)
(def x (map (fn [n]
              (struct-map desilu
                :fred n
                :ricky 2
                :lucy 3
                :ethel 4))
             (range 100000)))
(def fred (accessor desilu :fred))
(reduce (fn [n y] (+ n (:fred y))) 0 x)
 -> 4999950000
(reduce (fn [n y] (+ n (fred y))) 0 x)
 -> 4999950000

위 예시에서 두 reduce의 결과가 같다는 점이 핵심이에요 — 키워드 :fred로 접근한 값이나 accessor로 만든 fred로 접근한 값이 같은 합을 내죠.

StructMap 관련 함수

구조 기반 설정: create-struct defstruct accessor
개별 struct 만들기: struct-map struct

ArrayMap

코드 폼을 조작할 때 키 순서를 유지하는 맵이 필요하면 편리해요. ArrayMap이 바로 그런 맵이에요 — 말 그대로 key val key val … 형태의 배열로 구현돼요. 그래서 선형(linear) 탐색 성능을 가지며, 아주 작은 맵에만 적합해요. 완전한 맵 인터페이스를 구현해요. 새 ArrayMap은 array-map 함수로 만들 수 있어요. 주의할 점은, array map은 '수정'되지 않은 상태에서만 정렬 순서를 유지한다는 거예요. 이후에 assoc을 반복하면 결국 hash-map으로 '변해버려요'.

집합 (Sets)

집합은 고유 값들(unique values)의 컬렉션이에요. hash-set용 리터럴 문법이 따로 있어요.

#{:a :b :c :d}
-> #{:d :a :b :c}

hash-set과 sorted-set 함수로도 집합을 만들 수 있어요.

(hash-set :a :b :c :d)
-> #{:d :a :b :c}

(sorted-set :a :b :c :d)
-> #{:a :b :c :d}

컬렉션에 들어 있는 값들의 집합도 set 함수로 얻을 수 있어요.

(set [1 2 3 2 1 2 3])
-> #{1 2 3}

집합은 컬렉션이에요.

(def s #{:a :b :c :d})
(conj s :e)
-> #{:d :a :b :e :c}

(count s)
-> 4

(seq s)
-> (:d :a :b :c)

(= (conj s :e) #{:a :b :c :d :e})
-> true

집합은 disj로 '제거'를 지원하고, contains?와 get 도 지원해요. get은 찾으면 키와 같게 비교되는, 집합에 담긴 객체 자체를 반환해요.

(disj s :d)
-> #{:a :b :c}

(contains? s :b)
-> true

(get s :a)
-> :a

집합은 get을 쓰듯 자기 구성원의 함수예요.

(s :b)
-> :b

(s :k)
-> nil

Clojure는 union / difference / intersection 같은 기본 집합 연산을 제공해요. 여기에 더해, '관계(relation)' — 즉 단순히 맵들의 집합 — 를 위한 일부 의사 관계대수(pseudo-relational algebra) 지원도 제공해요 — select / index / rename / join이 있어요.

Clojure 데이터 구조