マエカワの備忘録的な何か

思い立ったが吉日

プログラミング言語演習 scheme編

リストを表示するのはこれまでの言語では[]だったが、schemeでは()を用いていく.空白を用いてデータの区分けをする.
iEDのターミナル上の応答型エディタではhistoryや方向キーが対応しないため、少し入力しずらい。

1.リストの先頭に要素を足す

>'(2 3)
(2 3) ;普通のリスト表示.'は次の値がデータですよーってことを表す.
>
>cons 1'(2 3)
>#<procedure:cons>
>1
>(2 3) ;これはなんかやばそう
>
>(cons 1'(2 3))
(1 2 3)
>
>(cons '+(cons 1'(2 3)))
(+ 1 2 3) ;これは1+2+3を表している.
>
>(eval (cons '-(cons 1'(2 3))))
-4 ;evalは評価関数.ここでは1-2-3=-4を実行して表示している.

2.演算の表記

前置記法で演算を行う.また、データであることを表す時も前置記法としてシングルクオテーションをつける.たとえば

>(+ 1 2 3)
6
>
>(* 3 (+ 1 2 3))
18 ;(1+2+3)*3=18を表示している
>
>(cons '+(cons 1'(1 2 3 4)))
(+ 1 1 2 3 4) ;+は数字ではないので、'を前にくっつけずに入力実行するとエラーが出てしまう.
>
>(cons '+ '(cons 1 '(1 2 3 4)))
(+ cons 1 '(1 2 3 4)) ;(cons 1 '(1 2 3 4))の前に'があることによって、データとして認識した

3.関数指定、ラムダ演算

関数を定義するとき、ラムダ演算というものを実行する.

(define 関数名 (lambda (引数 ...) 式))

って言う形をとる.
たとえば、2乗する関数を定義してみる.

>(define pow2 (lambda (x) (* x x)))
>
>(pow2 3)
9
>
>((lambda (x) (* x x)) 3) ;define関数はlambda演算に名前をつける役割のみを持っている.
9

4.条件式 if文

形式は
(if 条件 帰結式 代替式)
で表す.if文は構文(ご指摘を受けまして直しました.)であるため、値を持つ必要がある.つまり帰結式は省略できない.

>(define !(lambda (x)(if (= (- x 1) 0) 1 (* x (! (- x 1))))))
>
>(! 3)
6
>
>(! 4)
24

define文で書いたのは
  \displaystyle \begin{cases}1&if x-1=0&\\x*(x-1)!&otherwise&\end{cases}
という xの階乗の定義そのもの.

構文と手続きの違い….難しいな.

5.ちょっと高度なcond式

elseが無ぇ...と思いましたが、cond条件式というものを使えば出すことができるようです.
(cond (条件1 式1)
(条件2 式2)

(else 式n) )
っていう形で書くことができるそうです.たとえば、二つの引数の乗算をの結果が0より大きいか0より小さいか、0なのかを評価する関数を定義してみる.

>(define compare (lambda (x y) (cond ( (> (* x y) 0) '(larger than 0) ) ( (< (* x y) 0) '(less than 0) ) ( (= (* x y) 0) '(equal 0) ) )))
>
>(compare 3 4)
(larger than 0)

6.演算子の適用

(+ 1 2 3 4)って書くのはめんどい.なんで、(1 2 3 4)に"+"演算子を適用しようってニュアンス.
 (apply 関数 リスト)
の形で表しマース.
では、平均値を表示する関数を定義しましょう.

>(define ave (lambda (l) ( / (apply + l) (length l) ) ) )
>
>(ave '(1 2 3 4 5 6 7 8 9 10))
11/2

ここでの(length l)はlの要素数を表すもの.四則演算のみならず、defineで定義した関数に関しても適用できるのがみそ.

7.写像を表現しましょう

applyの進化版っぽくとらえてます.形はapplyのときと同じく
 (map 関数 リスト)
使い方もapplyと同じような気がする.すべての要素を負の数にするminus関数を定義、mapで写像として移してやる.

>(define minus (lambda (x) (if (> x 0) (* x -1) x ) ) )
>
>(map minus '(-1 2 -3 -4 5 6 -7))
(-1 -2 -3 -4 -5 -6 -7)
>
>;ためしにapplyでもやってみる
>(apply minus '(-1 2 -3 -4 5 6 -7))
procedure minus: expects 1 argument, given 7: -1 2 -3 -4 5 6 -7
>;怒られました.どうやら、applyの最終的な値は一つ.mapは集合全体に適用できるらしい.

8.リストの操作についてもうちょっと

ここまで出てきたリスト操作として先頭に一つのデータを加えるconsがあった.ここではほかのリスト操作についてやっていく.
・car:リストの先頭のデータを取得
・cdr:リストの2要素目以降からなるリストを取得
・cons:リスト先頭に要素を加える
これが基本的なもの.これらを駆使していくことで、リストを自由自在に、なりたいところ。。。

練習

1.リスト生成
もろにリスト操作の問題.引数として与えられた数を1ずつデクリメントしていった時のリストを生成.

>(define numlist (lambda (x) (if (= x 1) '(1) (cons x (numlist(- x 1))) ) ) )
>
>(numlist 5)
(5 4 3 2 1)
>(numlist 1)
(1)

numlistは関数であり、リストであることを忘れてはいけない.

2.リストのリスト(?)の作成
リストを引数としてそれらのリストを結合し、一つのリストにするような関数の定義.

>(define myappend (lambda (l) (if (= l '()) ('()) ( append '(car l) ( myappend( cdr l ) ) ) ) ) )
>
>(myappend '((1 2 3) (a b) (c d)) )

めんどくさいやり方で考えていたようです。。。これでもエラーが出たので、すなおにapply使っていきます.

>(define myappend (lambda (l) (apply append l)))
>
> (myappend '((1 2 3) (a b) (c d)) )
(1 2 3 a b c d)

できた(キムタク風).

3.二つの変数を用いたmap処理
(times 3 '(1 2 3 4)) → (3 6 9 12)
(times 5 '(2 8 5)) → (10 40 25)
こんな漢字の処理をさせたい.
mapで処理を行いたいが、変数が二つある.どうすればいいだろうか.
名前なし関数をmap内に定義する.
所見で書いたものが下のプログラム.

>(define times (lambda (x l) (map (lambda (l) (* l x)) l)))
>
> (times 3 '(1 2 3 4))
(3 6 9 12)

一応吐き出してくれるものはあっている.けど、times関数内の変数lと名前なし関数内の変数lがかぶってて超絶分かりにくい.ということで、名前なし関数内の方をnに置き換えます.

>(define times (lambda (x l) (map (lambda (n) (* n x)) l)))
>
> (times 3 '(1 2 3 4))
(3 6 9 12)

これで見やすくなった!!
変数の数に自由度を持たせるために名前なし関数を定義....なるほどなぁ.

4.2乗平均平方根の計算
(rms '(1 2 3)) → 2.160246899469287
こんな漢字の処理をさせたい.
初見コードは下に

>(define rms (lambda (l) (sqrt (/ (apply + (map (lambda (n) (* n n)) l)) (length l)))))
> (rms '(1 2 3))
2.160246899469287

うまくいきました.やった!!
mapで2乗にしてapplyで足し会わせるという演算でした.前の問題のノウハウが活かされてます.

これで基本的な練習問題は終了.次からいよいよ課題に移ります.

課題1
木構造について、map処理と同じ処理賀できるmap-tree関数というものをつくってみる.要するにmapの上位互換.
こんな感じになります.mapのときは(pair? tree)の部分は無いんですが、木構造になることによってペアか層で無いかの判定が必要になってきました.

>(define map-tree (lambda (fn tree) 
                   (cond ((null? tree) '() )
                         ((pair? tree ) (cons (map-tree fn (car tree)) (map-tree fn (cdr tree)))) 
                         (else (fn tree)))
                   )
  )
>
> (define TREE '(1 (2 (3 4)) 6 (7 8 9)) )
> (map-tree even? TREE)
(#f (#t (#f #t)) #t (#f #t #f))

んで、今度はconsでつなげていた部分をmapを使って一気にやってしまおうってことをします.変数二つの関数をmapに対応させる.そう、練習問題の3番目っすね.名前無し関数を使っていきましょう.ということで、つくられたコードがこちら.

>(define map-tree (lambda (fn tree) 
                   (cond ((null? tree) '() )
                         ((pair? tree ) (map (lambda (tree) (map-tree fn tree)) tree)) 
                         (else (fn tree)))
                   )
  )
>
> (define TREE '(1 (2 (3 4)) 6 (7 8 9)) )
> (map-tree even? TREE)
(#f (#t (#f #t)) #t (#f #t #f))

こうなります.名前無し関数内のtreeの部分をtに変えてもいいかも知れないですね.
変数名がかぶっているけど別々のものとして扱うのをみると、javaのコンストラクタの定義の時を思い出します.

課題2