読者です 読者をやめる 読者になる 読者になる

素人がプログラミングを勉強していたブログ

プログラミング、セキュリティ、英語、Webなどのブログ since 2008

連絡先: すかいぷ:javascripter_  か javascripter あっと tsukkun.net skypeのほうがいいです

データ構造等のメモ

Schemeにあるデータ構造についてのメモ。よく分かってない。

数値

1
0.1
99999999999999999999999 ; 大きい数が扱える
(* 1 6) ; 6
(= (0.1 * 6) 0.6) ; # #f 小数が絡むと演算の誤差が入る
(/ 1 7) ; 有理数が扱える

Schemeでは正確数と不正確数に分かれていて、不正確な演算の結果出た数値を使って演算をすると、その結果の数値も不正確になる。
で、正確なのかどうかは、exact?や、inexact?で判定できる。

文字

#\a
#\あ
#\  ; 半角スペース
#\space ; こう書くこともできる。

普通のUnicodeの文字。

文字列

"aa\"bb"
"multi line
string"

普通の文字列。文字のリストではないので、リストとして使いたい時は(string->list "aiueo")のようにする。
string-set!等、文字列を破壊的に操作することのできる関数があるので、immutableではない。

シンボル

'aiueo ; (quote aiueo)と同じ
(car '(foo bar)) ; 'foo。

S式という名の通り、Schemeのプログラムはデータとしてはシンボルとリスト、その他のリテラルに書ける物からできている。
調べたら、文字列をinternした物と書いてあって(internってのは.freezeするという事?)、immutableな文字列との違いがよく分からなかった。

リスト

'(1 2 3) ; 1と2と3
(list 1 2 3)
(cons 1 (cons 2 (cons 3 '())))
'(1 2 . 3) ; . 3は0.3ではない
(cons 1 (cons 2 3))

(import (srfi :1)) 
(circular-list 1 2 3)

リストは、値と次のリストへのポインタを指した物で、Cだと構造体とかを使って表したりする。配列と違って破壊的操作がなくても簡単に作れるので、関数的なプログラムと相性がいい。
'(1 2 . 3)は、(cons 1 (2 3))とほぼ同じで、JavaScriptっぽく表すと[1, [2, 3]]。つまり、リスト以外がcdrの場合ドットを使って表わす。
「ドット対」、「ドットリスト」でGoogle検索する。
最後が空のリストで終わる普通のリストは、正式なリストと言う。
リストはmutableで、set-car!set-cdr!を使えば自由に書き換えることができる。
書き換えると、直接的もしくは間接的に自分自身がcdrになることがある。そのようなリストは循環リストと呼ぶ。circular-listを使うと、循環リストを簡単に作れる。
循環リストのlengthを取るとエラーになる。
'(1 2 3)等で作ったリストはimmutableで、書き換えることはできない。

ハッシュテーブル

(define a-h (make-eq-hashtable))
(hashtable-set! a-h 'key "value")

(define  b-h (make-hashtable equal-hash eq?)) ; a-hと同じ
(hashtable-set! b-h 'k 'v)
(hashtable-ref b-h 'k 'not-found) ; 'v。第三引数に見つからなかった時を返すかを指定する。

(make-eq-hashtable 10) ; サイズを指定することもできる

キーから値を取り出すことができる物。
(hashtable-set hash-fun equal?-func)のような引数を取る。
引数を一つ取り、だいたい一意な整数を返す関数のことをハッシュ関数を呼ぶ。
たまに違う引数に同じ整数を返すことがある。
これを一つ目の引数として渡す。
equal?-funは引数を二つ取り、それが等しいかどうかを比較する関数。ハッシュ値が衝突した時に、この関数を使ってキーが等しいかどうかきちんと調べる。
想像図:

a = [0, 0, 0, 0, 0, ...]
hash_fun("aiueo") -> 3
a[3] = [["aiueo", "val"]]

hash_fun("boo") -> 2
a[2] = [["boo", "val2"]]

hash_fun("xxx") -> 3 ; 衝突した
a[3].push(["xxx", "val3"])

a[3].index_of(lambda (obj) is_equal(obj[0], "xxx")) -> 1
a[3][1][1] -> "val3"

配列(vector)

(make-vector 100) ; 100個の要素を持った配列
(define v (vector 1 2 3))
'#(#(1 2 3) #(4 5 6)) ; 配列の要素には何でも入れられる
(vector-ref v 1) ; 2

普通の配列。cdrを保持しなくていいからメモリ消費が少ない。どの位置にある要素も同じ時間で取り出せる。リストは、後のほうの要素ほど取り出すまでに辿るcdrが増えて遅くなる。
vector-refで範囲外のindexを指定するとエラーになる。

構造体

(define-record-type person
  (fields
    (mutable name) ; (person-name-set! obj "alice") で書き換えられる
    (mutable sex)
    (immutable social-security-number)) ; 変更不可
  (protocol
    (lambda (publisher)
      (lambda (name sex) ; social-security-numberは自動発行にする
        (set! *ssn-count* (+ *ssn-count* 1))
        (publisher name sex *ssn-count*)))))

(make-person "bob" 'man)

昨日はじめて知った。レコードとも言う。クラスのような物?