lambda(ラムダ)式
lambda式の例
; (λx.x*x)3
==> ((lambda (x) (* x x)) 3)
9
;; 次の定義は「(define (compare f x y) (if (f x y) 'yes 'no))」 と同じ
; λf.λ<x,y>. if(f(x,y))then 'yes else 'no
==> (define compare (lambda (f x y) (if (f x y) 'yes 'no)))
#<unspecified>
==> (compare < 2 3)
yes
==> (compare > 2 2)
no
==> (compare string<? "x" "y")
yes
;;次の定義は「(define (compare2 f) (lambda (x y) (if (f x y) 'yes 'no)))」と同じ
==> (define compare2 (lambda (f) (lambda (x y) (if (f x y) 'yes 'no))))
#<unspecified>
==> ((compare2 <) 2 3)
yes
==> ((compare2 >) 2 2)
no
==> (define symbol<=? (compare2 (lambda (a b) (string<=? (symbol->string a) (symbol->string b)))))
#<unspecified>
==>> (symbol<=? 'x 'y)
yes
==>> (symbol<=? 'yes 'no)
no
[kadai17]
以下の関数を作成せよ．
- 1引数関数fを引数として，f(1)を計算する1引数関数apply1
==> (apply1 (lambda (x) (+ x 1))) 2 ==> (apply1 (lambda (y) (* (+ y 1) (+ y 1)))) 4 ==> (apply1 zero?) #f ==> (apply1 -) -1 - lambda式で表される1変数多項式と数値mを引数として，{f(m)}2を計算する2引数関数square-poly
;; f(x)=x+1について，{f(2)}2を計算する． ==> (square-poly (lambda (x) (+ x 1)) 2) 9 ;; f(x)=x2+2x+1について，{f(3)}2を計算する． ==> (square-poly (lambda (x) (+ (* x x) (* 2 x) 1)) 3) 256 - kを引数として，引数をk倍する1引数関数を返す1引数関数ktimes
==> (define 8times (ktimes 8)) #<unspecified> ==> (8times 10) 80 ==> ((ktimes 3) 4) 12 - 1引数関数f,1引数関数gを引数として，合成関数(g・f)を返す2引数関数composite-func．ただし(g・f)(x) = g(f(x))と定義する．またfの値域は，gの定義域に含まれるものとする．
==> (define squ+1 (composite-func (lambda (x) (* x x)) (lambda (x) (+ x 1)))) #<unspecified> ==> (squ+1 3) 10
[kadai18]
以前のinsersion sortのプログラム(kadai12,kadai13)では，整数用，文字列用というように扱うデータによって異なるプログラムを作成したが，それらのプログラムの構造はほとんど同じであった．そこで，これらを一般化して，比較関数を引数に追加して，いろいろな種類のデータに対してさまざまな基準でソートを行うことを考える．
- 関数isortを以下のように拡張せよ．新しいisortは，
(isort cmp dat)
のように比較関数cmpとソートするデータdatをとる2引数関数 であり，与えられた関数cmpを比較基準として，datをソートする．<動作例>
==> (isort < '(1 5 4 2 3)) (1 2 3 4 5) ==> (isort > '(1 5 4 2 3)) (5 4 3 2 1) ;; (modulo x y)は，xをyで割った余りを返す関数 ;; 以下の比較関数では整数全体の集合が全順序集合ではなくなるが， ;; 推移律は成り立っており，それなりに動作する． ==> (isort (lambda (x y) (< (modulo x 5) (modulo y 5))) '(1 5 4 2 3)) (5 1 2 3 4) ==> (isort (lambda (x y) (string<? (symbol->string x) (symbol->string y))) '(x a y b z)) (a b x y z)なお，並べ替えるデータdatに対して，適切な比較関数cmpが引数 として与えられるものと仮定してよい．データdatの種類に応じて比較関 数を自動的に選び出すというようなことはここでは考えない． 実際，上の例のように，まったく同じ型のデータでも並べ替える基準を変えたい場合 にはそのようなことは原理的にできない． もちろんデータの型により基準が一意的に決まってよく， 並べ方を変える場合には別の型を定義するのであればできるが， その場合にはオブジェクト指向の，あるいはオブジェクト指向的な プログラミングを行うのが一つの方法である． そのようなことは，例えば何回か後に説明するclosureを使っても行える (が，授業ではそれを実現する具体的なコードについてまでは説明しない)． - リストを要素とするリストを要素のリストの長さの短い順でソートする関数
lsortを定義せよ．lsortは，isortに適当な比較関数を与えることで定義できる．
==> (lsort '((a b c) (y z) (1) ())) (() (1) (y z) (a b c))
(メイルのサブジェクトは，kadai19optとすること)
リストあるいはアトムを要素にもつ一般的なリストは，リストあるいはアトムをノード(節)として，リストであるノードから，その各要素(リストまたはアトム) に対してエッジ(枝)を張ってつなげていくと，末端がアトムである木のような構造をもっていることがわかる．
この木構造において，木の末端となっていてエッジをもたないノード，すなわち，アトムであるノードを葉と呼ぶ．また，あるノードからのびている各エッジのそれぞれの先の部分を部分木と呼ぶ．
葉がすべて数であるようなリストに関して，その全てのノードにおいて，各部分木が，その一番左の葉の値の小さい順に並ぶようにソートする関数ntsortを定義せよ．
==> (ntsort '(3 2 1))
(1 2 3)
==> (ntsort '((9 8 7) (2 3 1) (5 6 4)))
((1 2 3) (4 5 6) (7 8 9))
==> (ntsort '(7 (3 2) (((8) (5 4) (1 0)) (9 3 6))))
((((0 1) (4 5) (8)) (3 6 9)) (2 3) 7)
;; 数に関しては，そのものを返す．
==> (ntsort 4)
4
;; 空リストに対しては，空リストを返す．
==> (ntsort '())
()
[kadai20]さまざまな場面で「リストの各要素に対して同じことを行った結果をリストにする」処理が必要になることがある．
;; リストのリストの各要素の長さを求めてリストにする．
;; listlenが定義されているものとする．
(define (listlens x)
(if (null? x)
'()
(cons (listlen (car x)) (listlens (cdr x)))))
;; 数値リストのリストの各要素の合計を求めてリストにする．
(define (sums-of-lists x)
(if (null? x)
'()
(cons (list-sum (car x)) (sums-of-lists (cdr x)))))
;; 数値のリストxをベクトルとみなして大きさの二乗を求める
(define (norm2 x)
;; 数値リストの各要素を二乗する局所関数の定義
(define (square-list y)
(if (null? y)
'()
(cons (* (car y) (car y)) (square-list (cdr y)))))
(list-sum (square-list x)))
;; 数値リストの各要素を合計する関数
(define (list-sum y)
(if (null? y)
0
(+ (car y) (list-sum (cdr y)))))
;;
;; 関数の実行例
;;
==> (listlens '((a b) (c) () (d e f)))
(2 1 0 3)
==> (sums-of-lists '((9 0 1) (5 6 7) (4 3 2)))
(10 18 9)
==> (norm2 '(1 2 3 4 5))
55
ここで挙げた次の関数は，お互いに非常に似た構造をしている．
- listlens
- sums-of-lists
- norm2内のsquare-list
(map1 func data)
map1は，リストdataの各要素に1引数関数funcを適用したリストを生成することになる．またこのmap1を用いてlistlens,sums-of-listsおよびsquare-listを記述せよ．
[kadai21]
kadai20で挙げたlist-sumをよく見ると，やはりlistlensなどと似た構造をしていることが分かる．
(define (listlens x)
(if (null? x)
'()
(cons (listlen (car x)) (listlens (cdr x)))))
(define (list-sum y)
(if (null? y)
0
(+ (car y) (list-sum (cdr y)))))
異なっているのは次の点である．
- 引数が( )のとき，0を返すか，あるいは( )を返すか
- carを処理するのに，そのまま使うか，あるいはlistlenで処理するか
- carを処理した結果とcdrを再帰処理した結果を，+でまとめるか，あるいはconsでまとめるか
(gmap1 func comb init data)
なおkadai20と同様「func」がリスト「data」の各要素に適用する1引数関数である． 「comb」はcarを処理した結果とcdrを再帰処理した結果をまとめる関数であり， 「init」は引数dataが( )のときに返す値である．
[kadai22opt]:選択問題(必ずしもやらなくてよい)
-
kadai20のmap1は，1引数関数と1つのリストを引数とする関数である．では，2引数関数と2つのリストを引数とする関数map2はどのように記述できるだろうか．さらに，一般にn引数関数とn個のリストを引数とする関数map-nはどのように記述できるか．関数map-nを作成せよ．
ただしmap-nへ渡す関数の引数の数は(map-nの)呼び出しごとに一定で、1個以上であると仮定してよい．
ヒント: map-nの定義中で可変個の引数を関数に送る際には applyを用いる． また，呼び出された関数側で可変個の引数を扱う方法についてはlambda式の説明をよく読むこと．==> (map1 car '((a b c) (d e f))) (a d) ==> (map2 + '(1 2 3) '(4 5 6)) (5 7 9) ==> (map-n + '(1 2 3) '(4 5 6)) (5 7 9) ==> (map2 cons '(a b c) '(d e f)) ((a . d) (b . e) (c . f)) ==> (map-n cons '(a b c) '(d e f)) ((a . d) (b . e) (c . f)) ==> (map-n car '((a b c) (d e f))) (a d) ==> (map-n + '(1 2 3 4) '(5 6 7 8) '(9 10 11 12)) (15 18 21 24) -
葉として数値のみをもつ木構造の葉の合計を求める関数
treesumを定義せよ．
==> (treesum '(1 (2 (3 4)) ((5 (6 7)) 8) (9))) 45 ==> (treesum '()) 0さらにkadai21のgmap1にあたる4引数関数gtreemap1を定義してみよ．またgtreemap1を用いてtreesumを記述せよ．さらにgtreemap1により，木の高さを計算するtree-heightを記述してみよ．なお木の高さとは，各エッジの長さを1として，木の根(一番外側のリストに対応するノード)から最も遠いノードまでの距離(エッジの長さの合計)であると する．==> (tree-height '(1 (2 (3 4)) ((5 (6 7)) 8) (9))) 4 ==> (tree-height '()) 0