14. ヴェクトルと構造体

1. 初めに

一般にヴェクターは同じ長さのリストよりも空間効率が高く、ランダムに選択した要素に対する 平均アクセス時間もリストより早くなります。 一方、ヴェクターの操作は副作用が伴うため、不用意に使うとバグの元になります。

また、構造体も C 言語の構造体と同様のものです。ただ、Lisp 語族にはマクロがあるので、 値にアクセスしたり、値をセットする関数を自動で書いてくれます。

2. ヴェクターの例

例：

'#(1 2 3)             ; 整数のヴェクター
'#(a 0 #\a)           ; シンボル、整数、文字を要素に持つヴェクター

3. ヴェクターにかかわる関数

(vector? obj)

obj がヴェクターなら #t、そうでなければ #f を返す。

(make-vector k)
(make-vector k fill)

k 個の要素を保持したヴェクターを新たに割り当ててそれを返す。 ２番目の引数 fill が与えられた場合、各要素は fill で初期化される。

(vector obj ...)

指定した引数を要素とするヴェクターを新たに割り当てそれを返す。

(vector-length vector)

vector に含まれる要素数を返す。

(vector-ref vector k)

vector の k 番目の要素を返す。

(vector-set! vector k obj)

vector の k 番目の要素を obj にする。

(vector->list vector)

vector をリストに変換する。

(list->vector list)

list をヴェクターに変換する。

(vector-fill! vector fill)

vector の全要素を fill にする。

01:     (define (vector-add v1 v2)
02:       (let ((lenv1 (vector-length v1))
03:     	(lenv2 (vector-length v2)))
04:         (if (= lenv1 lenv2)
05:     	(let ((v (make-vector lenv1)))
06:     	  (let loop ((i 0))
07:     	    (if (= i lenv1)
08:     		v
09:     		(begin
10:     		  (vector-set! v i (+ (vector-ref v1 i) (vector-ref v2 i)))
11:     		  (loop (1+ i))))))
12:     	(error "different dimensions."))))

4. 構造体

5. マスターマインド

1. 数字も桁もあっている数字の数 (bull)
2. 数字はあっているが、桁が違っている数字の数 (cow)

コンピュータと人間が数を当てあい、先に当てたほうが勝ちになります。 両者が同じ推測回数で当てた場合は引き分けです。

5.1. 数字の表現

要素が 10 個のヴェクターを作り、インデックス (k) の数が現れる桁を そのインデックスの値にします。桁は 1 の位から 1,2,3,4 と数えます。 現れない数字のインデックスの値は 0 にします。 先の２つの数字 5601 と 1685 はプログラム内部では次のように表現されます。

5601 → #(2 1 0 0 0 4 3 0 0 0)
1685 → #(0 4 0 0 0 1 3 0 2 0)

数をこのように表現すると２つの数の比較を高速に行うことができます。 すなわち、２つのヴェクターで同じインデックスの値が両方とも正で、その値が 1) 等しければ bull、2) 等しくなければ cow だと数えることができます。 この場合インデックス 6 の値が両方とも 3 で等しいので bull は 1、 インデックス 1, 5, の値が両方とも正で、値が等しくないので cow は 2 になります。 このプログラムでは、 一致度 (score) を (bull*5 + cow) で表わします。

5.2. プログラムの概要

1. 0--9 の異なる数字からなる４桁の数字のヴェクター表現 全てからなるリストを作る。
2. その中から想定数を１つランダムに選ぶ。
3. (1) で作ったリストをシャッフルする。
4. まず、コンピュータの推測値を示して、ユーザーから bull と cow の数を入力してもらう。 次にユーザーの推測値を入力してもらい bull と cow を示す。
5. どちらかの bull が 4 になるまで (4) を繰り返す。両方の bull が同時に 4 になった場合は引き分け。

5.3 プログラムコード

 01:     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 02:     ;;;
 03:     ;;; mastermind.scm
 04:     ;;; by T.Shido
 05:     ;;;
 06:     ;;; User and computer try to locate the four-digit integer set by the opponents each other.
 07:     ;;; One who locates the integer with fewer question is the winner.
 08:     ;;; The four-digit integer contains four of numerals 0--9, like 0123, 3749 etc.
 09:     ;;; The opponents should tell the guesser
 10:     ;;; (1) number of numerals that are shared by the guessed and set numbers
 11:     ;;; at wrong position (cows)
 12:     ;;; and (2) number of numerals at collect position (bulls).
 13:     ;;; 
 14:     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 15:     ;;;
 16:     ;;; The four-digit integers are represented by 10-cell vectors in the program
 17:     ;;; The value of n-th cell is the number of column that n appears in the integer.
 18:     ;;; in n is not appears the value is 0.
 19:     ;;; for example, 1234 is represented as #(0 4 3 2 1 0 0 0 0 0) and
 20:     ;;; 3916 as #(0 2 0 4 0 0 1 0 0 3).
 21:     ;;; With this inner representation, the score of the guess can be calculated faster.
 22:     ;;;
 23:     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 24:     
 25:     
 26:     ;;;
 27:     (define (1- x) (- x 1))
 28:     
 29:     ;;;
 30:     (define (char2int c)
 31:       (- (char->integer c) (char->integer #\0)))
 32:     
 33:     ;;; converting a list of 4 numbers to the vector notation
 34:     (define (ls2nvec ls)
 35:       (let ((vec (make-vector 10 0)))
 36:         (let loop ((i (length ls)) (ls ls))
 37:           (if (> i 0)
 38:     	  (begin
 39:                (vector-set! vec (car ls) i)
 40:                (loop (1- i) (cdr ls)))
 41:             vec))))
 42:     
 43:     ;;; converting the vector notation to string
 44:     (define (nvec2int vec)
 45:       (let loop ((i 0) (n 0))
 46:         (if (= i 10)
 47:             n
 48:     	(let ((j (vector-ref vec i)))
 49:     	  (loop (1+ i) (+ n (if (> j 0)
 50:                                     (* i (expt 10 (1- j)))
 51:                                   0)))))))
 52:     
 53:     ;;;
 54:     (define (int2str i)
 55:       (string-append
 56:        (if (< i 1000) "0" "")
 57:        (number->string i)))
 58:     
 59:     ;;; reading integer from stdin
 60:     (define (read-integer str)
 61:       (string->number (read-from-stdin str)))
 62:     
 63:     ;;;
 64:     (define (read-from-stdin str)
 65:       (display str)
 66:       (newline)
 67:       (read-line))
 68:     
 69:     ;;;
 70:     (define (write-to-stdout . ls)
 71:       (for-each (lambda (obj) (display obj)) ls)
 72:       (newline))
 73:     
 74:     ;;; convert numeral string to the vector representation.
 75:     (define (str2nvec str)
 76:       (let ((vec (make-vector 10 0)))
 77:         (let loop ((i (string-length str)) (ls (string->list str)))
 78:           (if (pair? ls)
 79:     	  (begin
 80:                (vector-set! vec (char2int (car ls)) i)
 81:                (loop (1- i) (cdr ls)))
 82:             vec))))
 83:     
 84:     ;;; calculating the score of guess
 85:     (define (scoring vec0 vec1)
 86:       (let ((n (vector-length vec0)))
 87:         (let loop ((i 0) (score 0))
 88:           (if (< i n)
 89:     	  (let ((d0 (vector-ref vec0 i))
 90:                    (d1 (vector-ref vec1 i)))
 91:                 (loop (1+ i)
 92:     		  (+ score (if (and (< 0 d0) (< 0 d1))
 93:                                    (if (= d0 d1) 5 1)
 94:                                    0))))
 95:             score))))
 96:     
 97:     ;;; show bulls and cows calculated from the score of user's guess
 98:     (define (show-user-score score)
 99:       (write-to-stdout "Number of bulls and cows in your guess:" )
100:       (write-to-stdout "bulls: " (quotient score 5))
101:       (write-to-stdout "cows: " (modulo score 5))
102:       (newline))
103:     
104:     ;;; calculating the score of computer's guess from bulls and cows
105:     (define (read-my-score gu0)
106:       (write-to-stdout "My guess is: " (int2str (nvec2int gu0)))
107:       (write-to-stdout "Give number of bulls and cows in my guess." )
108:       (let ((na5 (* 5 (read-integer "bulls: "))))
109:         (+ na5 (read-integer "cows: ")))) ; the score is calculated by (5 * bull + cow)
110:     
111:     ;;; reading the user guess
112:     (define (read-user-guess)
113:       (newline)
114:       (str2nvec (read-from-stdin "Give your guess.")))
115:     
116:     ;;; shuffling the list of four-digit numbers
117:     (define (shuffle-numbers ls0)
118:       (let ((vec (list->vector ls0)))
119:         (let loop ((n (vector-length vec)) (ls1 '()))
120:           (if (= n 0)
121:               ls1
122:     	  (let* ((r (random n))
123:     		 (v (vector-ref vec r)))
124:     	    (vector-set! vec r (vector-ref vec (1- n)))
125:     	    (loop (1- n) (cons v ls1)))))))
126:     
127:     ;;; making a list of four-digit numbers in which numeral 0--9 appear once
128:     (define (make-numbers)
129:       (let ((ls1 '()))
130:         (letrec ((rec (lambda (i num ls)
131:     		    (if (= i 4)
132:     			(set! ls1 (cons (ls2nvec ls) ls1))
133:     			(for-each 
134:     			 (lambda (n)
135:     			   (rec (1+ i) (delv n num) (cons n ls)))
136:     			 num)))))
137:           (rec 0 '(0 1 2 3 4 5 6 7 8 9) '()))
138:         ls1))
139:     
140:     ;;;
141:     (define (game-over sc0 sc1)
142:       (write-to-stdout
143:        (cond
144:         ((= sc0 sc1) "Draw")
145:         ((> sc0 sc1) "I won.")
146:         (else "You won.")))
147:       'game-over)
148:     
149:     (define (scoring-user-guess an0 gu1)
150:       (let ((sc1 (scoring an0 gu1)))
151:         (show-user-score sc1)
152:         sc1))
153:     
154:     ;;; Practical main function. tail recursive.
155:     (define (mastermind-rec an0 candidates)
156:       (if (null? candidates)
157:           (error "Error. You gave wrong score for my guess, probably.")
158:           (let ((gu0 (car candidates)))
159:     	(let ((sc1 (scoring-user-guess an0 (read-user-guess)))
160:     	      (sc0 (read-my-score gu0)))
161:     	  (if (or (= sc0 20) (= sc1 20))
162:     	      (game-over sc0 sc1)
163:     	      (mastermind-rec an0 
164:     			   (keep-matching-items 
165:     			    (cdr candidates)
166:     			    (lambda (x) (= (scoring gu0 x) sc0)))))))))
167:     
168:     ;;; The main function called from the top-level
169:     (define (mastermind)
170:       (let ((ls0 (make-numbers)))
171:         (mastermind-rec (list-ref ls0 (random (length ls0))) (shuffle-numbers ls0))))

5.4. 遊び方

(compile-file "mastermind.scm")
(load "mastermind")
(mastermind)

6. 練習問題の解答

問題１

01:     (define (inner-product vec1 vec2)
02:       (let ((len1 (vector-length vec1))
03:     	(len2 (vector-length vec2)))
04:         (if (= len1 len2)
05:     	(let loop ((i 0) (pro 0))
06:     	  (if (= i len1)
07:     	      pro
08:     	      (loop (1+ i) (+ pro
09:     			      (* (vector-ref vec1 i)
10:     				 (vector-ref vec2 i))))))
11:     	(error "different dimensions."))))

7. 終わりに

次回は自前の構文を定義する方法について述べます。自前の構文を定義できるのは Lisp 語族の大きな特徴になっています。

HOME

13. 連想リスト、ハッシュ表

もうひとつの Scheme 入門

15. 構文の定義

download

書き込む