12. シンボル型

1. 初めに

今回は Lisp 語族に特徴的なデータ型：シンボルについて説明します。一言で言うとシンボルとは、文字列をアドレスで管理するデータ型です。従って、シンボル同士を比較するときは、eq? などのアドレスを比較する関数が使え、高速に比較できます。一方、文字列を素直に比較すると１文字１文字比較していかなければならないため、比較に時間がかかります。高速に比較が行えるという特徴から、シンボル型は後述する連想リストやハッシュ表のキーとして利用されます。

2. シンボル型の基本的な関数

以下にシンボル型の基本的な関数を挙げます。

(symbol? x)

x がシンボルのとき #t を返します。

(string->symbol str)

str をシンボルに変換します。処理系によりますが、str は小文字に変換しておかないと同じ綴りでも同一のアドレスにアサインされません。MzScheme では次のようになります。

> (eq? (string->symbol "Hello") 'Hello)
#t        ; 処理系によっては #f になる
> (eq? (string->symbol "Hello") (string->symbol "Hello"))
#t
> (symbol->string  (string->symbol "Hello"))
"Hello"

(symbol->string sym)

sym を文字列に変換します。

3. テキスト中の単語のカウント

お決まりの例としてテキスト中の現れる単語をカウントするプログラムを示します。このプログラムではハッシュ表や連想リストを使っていますが、それらの詳しい説明は次の章にあります。

(require rnrs/hashtables-6)


(define (list->symbol ls0)
  (string->symbol (list->string (reverse ls0))))

   
(define (char-in c . ls)
  (let loop((ls0 ls))
    (if (null? ls0)
	#f
	(or (char=? c (car ls0))
	    (loop (cdr ls0))))))

   
(define (read-words fname)
  (with-input-from-file fname
    (lambda ()
      (let loop((w '()) (wls '()))
	(let ((c (read-char)))
   	  (cond
   	   ((eof-object? c)
	    (reverse (if (pair? w)
			 (cons (list->symbol w) wls)
			 wls)))
   	   ((char-in c #\Space #\Linefeed #\Tab #\, #\.  #\ #\( #\) #\= #\? #\! #\; #\:)
	    (loop '() (if (pair? w)
			  (cons (list->symbol w) wls)
			  wls)))
   	   (else
   	    (loop (cons (char-downcase c) w) wls))))))))

   
(define (sort-by-frequency al)
  (sort al (lambda (x y) (> (cdr x) (cdr y)))))



(define (hashtable->alist h)
  (let ((keys (hashtable-keys h)) (size (hashtable-size h)))
    (let loop ((i 0) (ls1 '()))
      (if (= i size)
	  ls1
	  (let* ((k (vector-ref keys i)) (v (hashtable-ref h k #f)))
	    (loop (+ i 1) (cons (cons k v) ls1)))))))


(define (wc fname)
  (let ((wh (make-eq-hashtable)))
    (let loop((ls (read-words fname)))
      (if (null? ls)
	  (sort-by-frequency (hashtable->alist wh))
	  (let ((k (car ls)))
            (hashtable-set! wh k (+ 1 (hashtable-ref wh k 0)))
            (loop (cdr ls)))))))

> (wc "opensource.txt")
((the . 208) (to . 142) (a . 104) (of . 103) (and . 83) (that . 75) (is . 73) (in . 65) (i . 64)
(you . 55) (it . 54) (they . 48) (for . 46) (what . 38) (work . 37) (but . 35) (have . 32) (on . 32)
(people . 32) (are . 30) (be . 29) (do . 29) (from . 27) (so . 26) (like . 25) (as . 25) (by . 24)
(source . 24) (not . 23) (open . 23) (can . 23) (we . 22) (was . 22) (one . 22) (it's . 22) (an . 21)
(this . 20) (about . 20) (business . 18) (working . 18) (most . 17) (there . 17) (at . 17) (with . 16)
(don't . 16) (just . 16) (their . 16) (something . 15) (than . 15) (has . 15) (if . 15) (when . 14)
(because . 14) (more . 14) (were . 13) (office . 13) (own . 13) (or . 12) (online . 12) (now . 12)
(blogging . 12) (how . 12) (employees . 11) (them . 11) (think . 11) (time . 11) (company . 11)
(lot . 11) (want . 11) (companies . 10) (could . 10) (know . 10) (get . 10) (learn . 10) (better . 10)
(some . 10) (who . 10) (even . 9) (thing . 9) (much . 9) (no . 9) (make . 9) (up . 9) (being . 9)
(money . 9) (relationship . 9) (that's . 9) (us . 9) (anyone . 8) (average . 8) (bad . 8) (same . 8)
..........)

簡単な説明：

(list->symbol ls0): 文字列のリスト ls0 をシンボルにする。単語１つをファイルから読み込むときに使う。
(cahr-in c . ls): 文字 c が ls にあるときは #t をないときは #f を返す。
(read-words fname): ファイル名 fname のファイルを読み、シンボルのリストを返す。大文字は小文字に変換し、単語の区切りにきたら、読み込んだ文字のリスト (w) をシンボルに変換してシンボルのリスト (wls) に加える。
(sort-by-frequency al): 単語と出現回数の連想リスト al を出現回数の降順にソートする。
(hashtable->alist h): ハッシュテーブル h を連想リストに変換する。
(wc fname): ファイル名 fname のファイルを読み、出現回数の多い順に並べた連想リストを返す。シンボルを使っているので、キーの比較に最も高速な比較関数 eq? を使う eq-hash-table が使える。 read-words で作った単語のリストを順番に調べていき、単語別に出現回数をカウントしていく。カウントし終わったらハッシュ表を連想リストに変換してソートする。

4. 終わりに

今回はシンボル型について説明しました。シンボルを利用すると文字列の処理を高速に行うことができます。文字列を処理するプログラムを書くときは使ってみることをお勧めします。