Schemeの課題 --- (4) 16-19

Copyright(C)1995, 2007 by 桜川貴司
Copyright(C)1998-2005 by 日置尋久

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

[kadai16]
以下の関数を作成せよ.

  1. 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
    
  2. 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
    
  3. kを引数として,引数をk倍する1引数関数を返す1引数関数ktimes
            ==> (define 8times (ktimes 8))
    	#<unspecified>
            ==> (8times 10)
    	80
            ==> ((ktimes 3) 4)
    	12
    
  4. 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
    

[kadai17]
以前のinsersion sortのプログラム(kadai12,13)では,整数用,文字列用というように扱うデータによって異なるプログラムを作成したが,それらのプログラムの構造はほとんど同じであった.そこで,これらを一般化して,比較関数を引数に追加して,いろいろな種類のデータに対してさまざまな基準でソートを行うことを考える.

  1. 関数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を使っても行える (が,授業ではそれを実現する具体的なコードについてまでは説明しない).
  2. リストを要素とするリストを要素のリストの長さの短い順でソートする関数 lsortを定義せよ.lsortは,isortに適当な比較関数を与えることで定義できる.
    	==> (lsort '((a b c) (y z) (1) ()))
           (() (1) (y z) (a b c))
    
[kadai17opt] [オプション問題]※必ずしも解かなくてよい
(メイルのサブジェクトは,kadai17optとすること)

リストあるいはアトムを要素にもつ一般的なリストは,リストあるいはアトムをノード(節)として,リストであるノードから,その各要素(リストまたはアトム) に対してエッジ(枝)を張ってつなげていくと,末端がアトムである木のような構造をもっていることがわかる.
この木構造において,木の末端となっていてエッジをもたないノード,すなわち,アトムであるノードを葉と呼ぶ.また,あるノードからのびている各エッジのそれぞれの先の部分を部分木と呼ぶ.
葉がすべて数であるようなリストに関して,その全てのノードにおいて,各部分木が,その一番左の葉の値の小さい順に並ぶようにソートする関数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 '())
       ()

[kadai18]

さまざまな場面で「リストの各要素に対して同じことを行った結果をリストにする」処理が必要になることがある.

        ;; リストのリストの各要素の長さを求めてリストにする.
	;; 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
ここで挙げた次の関数は,お互いに非常に似た構造をしている. そこでこれらを一般化した2引数関数map1を作成せよ.
        (map1 func data)
map1は,リストdataの各要素に1引数関数funcを適用したリストを生成することになる.またこのmap1を用いてlistlens,sums-of-listsおよびsquare-listを記述せよ.



[kadai19]

kadai18で挙げた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)))))
異なっているのは次の点である. そこで,kadai18のmap1をさらに一般化して4引数関数gmap1を作成し,gmap1を用いて,listlenslist-sumを記述せよ. なお,listlensの記述時にはlistlenにあたるものをgmap1を用いて記述して用いよ. また(square-list,list-sumを用いないで)gmap1のみを用いてnorm2を記述せよ.gmap1の仕様は次の通りとする.
        (gmap1 func comb init data)

なおkadai18と同様「func」がリスト「data」の各要素に適用する1引数関数である. 「comb」はcarを処理した結果とcdrを再帰処理した結果をまとめる関数であり, 「init」は引数dataが( )のときに返す値である.

[kadai19opt]:選択問題(必ずしもやらなくてよい)
(メイルのサブジェクトは,kadai19optとすること)

  1. kadai18の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)
    
  2. 葉として数値のみをもつ木構造の葉の合計を求める関数 treesumを定義せよ.
            ==> (treesum '(1 (2 (3 4)) ((5 (6 7)) 8) (9)))
            45
            ==> (treesum '())
            0
    
    さらにkadai19のgmap1にあたる4引数関数gtreemap1を定義してみよ.またgtreemap1を用いてtreesumを記述せよ.さらにgtreemap1により,木の高さを計算するtree-heightを記述してみよ.なお木の高さとは,各エッジの長さを1として,木の根(一番外側のリストに対応するノード)から最も遠いノードまでの距離(エッジの長さの合計)であると する.
            ==> (tree-height '(1 (2 (3 4)) ((5 (6 7)) 8) (9)))
            4        
            ==> (tree-height '())
            0
    

5回目(の説明)のまとめ

kadai12-kadai15のページへ