
\documentclass[a4j,10pt,onecolumn,oneside,notitlepage,final]{jarticle}
%Preamble

\begin{document}
\section*{演習}
情報数学の10月22日（水）Scheme 実習３のページ\\%urlがうまく表現できない。
\begin{verbatim}
(http://banon.ueda.info.waseda.ac.jp/oess/IM/Html/
        class_rsc/materials/2003-10-22.html)
\end{verbatim}
%banonにおいてあるのですな。今度内部から見てみよう。
をOcamlに直して解いてみる。

\subsection*{let 構文}
\verb|(let ((x (* 3 3))) (list x x x))| 
を実際に評価してみよ.

\begin{description}
\item [1.] Scheme

Schemeで実行すると
\begin{verbatim}
> (let ((x (* 3 3))) (list x x x))
(9 9 9)
\end{verbatim}
\item{2.} Ocaml

まず、SchemeをOcamlに直さないといけない。
\begin{verbatim}
let x = 3 * 3 in [x;x;x];;
\end{verbatim}
実行すると
\begin{verbatim}
# let x = 3 * 3 in [x;x;x];;
- : int list = [9; 9; 9]
\end{verbatim}
となり、Schemeと同じになった。こちらのほうが簡潔そうである。
\end{description}
\subsection*{関数を引数にとる関数}

\verb|map|関数をそれぞれ自分で作ってみて実行し比較してみる。

\begin{description}
\item [1.]Scheme
\begin{verbatim}
(define mymap
  (lambda (f x)
   (cond
     ((null? x) '())
     (else (cons (f (car x)) (mymap f (cdr x)))))))
\end{verbatim}
\verb|(mymap (lambda (x) (* x x)) '(-2 1 0 1 2 3))|を実行してみる。
\begin{verbatim}
> (define mymap
     (lambda (f x)
        (cond
          ((null? x) '())
          (else (cons (f (car x)) (mymap f (cdr x)))))))
> (mymap (lambda (x) (* x x)) '(-2 1 0 1 2 3))
(4 1 0 1 4 9)
\end{verbatim}
mapはリストの中身に対して関数適用を行う。
きちんと各要素に２乗しているのが見て取れる。
\item [2.]Ocaml

xをlに変えておく。tapleとして引数は渡す。
\begin{verbatim}
let rec mymap (f, l) = 
 match l with 
  [] -> [] | 
   x :: rest -> f x :: mymap (f, rest) ;;
\end{verbatim}

OcamlでもSchemeで実行したものと同義のものを実行してみる。つまり、\\
\verb|mymap ((fun x -> x * x), [-2; 1; 0; 1; 2; 3]);;|
を実行する。

\begin{verbatim}
# let rec mymap (f, l) = 
   match l with [] -> [] |
     x :: rest -> f x :: mymap (f, rest) ;;
val mymap : ('a -> 'b) * 'a list -> 'b list = <fun>
#   mymap ((fun x -> x * 2), [-2;1;0;1;2;3]);;
- : int list = [-4; 2; 0; 2; 4; 6]
\end{verbatim}
OcamlでもSchemeと同じ結果になった。ただし、それを実現するまでの違いに注意する。
%funはつよいので括弧をつけないと文末までいってしまうので注意。
\end{description}
\subsection*{関数を返す関数}
consをカリー化してみる
\begin{description}
  \item[1.] Scheme
\begin{verbatim}
(define cons1
  (lambda (a)
    (lambda (b) (cons a b))))
\end{verbatim}
注意すべき点は、lambdaが２個あるという点である。
これによって、関数を返す関数を実現できる。
また、カリー化関数は使うときも注意をしなければならない。
\begin{verbatim}
> (cons 1 '(2 3))
(1 2 3)
> (cons1 1 '(2 3))
procedure cons1: expects 1 argument, given 2: 1 (2 3)
> ((cons1 1) '(2 3))
(1 2 3)
\end{verbatim}
実際使ってみると、cons1は２引数では実行できない事が分かる。
カリー化により、１引数の関数を返す関数になっているからである。
これは間違え易いので、カリー化をするときは気をつけること。
\item [2.]Ocaml
\begin{verbatim}
let cons1 a = fun b -> a :: b ;;
\end{verbatim}
Ocamlの方が記述する事が少ない。また、括弧もないので分かり易いだろう。
Schemeと同様に、実際に使ってみる。
\begin{verbatim}
# let cons1 a = fun b -> a :: b ;;
val cons1 : 'a -> 'a list -> 'a list = <fun>
# cons1 34 [] ;;
- : int list = [34]
# cons1 45 [32];;
- : int list = [45; 32]
\end{verbatim}
Schemeでは、カリー化した関数につける括弧に気をつけなければならなかった。
しかし、Ocamlではそんな事を一切気にすることなくカリー化した関数を使用できる。
Ocamlの方が、カリー化は使いやすいと言える。
\end{description}
\subsection*{演習１}
\begin{description}
  \item[1.] 数学記法の$\sum $は，１引数関数（単項関数)$f$および 下限$a$，上限$b$をもらって，$f(a)+f(a+1)+\cdots +f(b)$を返す「関数」とみることができる.$\sum $を Scheme で定義せよ．
  \item[2.] (myexpt 2) が 二乗関数，(myexpt 3) が三乗関数，... （以下同様）として使えるように，myexpt を定義せよ．
\end{description}

\subsubsection*{Answer}
Scheme、Ocamlの双方でプログラムを実行してみる。
\paragraph*{1.}
\begin{description}
  \item[1.]Schemeの場合
\begin{verbatim}
(define sigma
  (lambda (f)
    (lambda (a)
      (lambda (b)
        (cond
          ((>= b a) (+ (f a) (((sigma f) (+ a 1)) b)))
          (else 0))))))
\end{verbatim}
\begin{verbatim}
(define sigma
  (lambda (f)
    (lambda (a)
      (lambda (b)
        (cond
          ((>= b a) (+ (f a) (sigma f (+ a 1) b)))
          (else 0))))))
\end{verbatim}
以上の２つの関数sigmaを良く見比べてもらいたい。
最初は下のものだったが、これでは実はうまくいかない。
何故なら、再帰部分でカリー化が失敗しているからである。
Schemeでカリー化をするときは括弧に出来るだけ気をつける。

上のものは括弧の付け方がカリー化に適したものになっている。
実行すると
\begin{verbatim}
> (define sigma
  (lambda (f)
    (lambda (a)
      (lambda (b)
        (cond
          ((>= b a) (+ (f a) (((sigma f) (+ a 1)) b)))
          (else 0))))))
> (((sigma (lambda (x) (* x x))) 1) 9)
285
> (((sigma (lambda (x) (- x 1))) 0) 5)
9
\end{verbatim}
となる。

\item [2.]Ocamlの場合
\begin{verbatim}
let rec sigma f = fun a -> fun b -> 
    if b >= a then f a + sigma f (a+1) b else 0 ;;
\end{verbatim}
Schemeよりも見やすく、簡単にかける。
実行すると、
\begin{verbatim}
# let rec sigma f = fun a -> fun b -> 
   if b >= a then f a + sigma f (a+1) b else 0 ;;
val sigma : (int -> int) -> int -> int -> int = <fun>
# sigma (fun x -> x * x) 1 9 ;;
- : int = 285
# sigma (fun x -> x - 1) 0 5 ;; 
- : int = 9
\end{verbatim}
となる。
if内部は逆のほうが良かったかもしれない。
\end{description}
\paragraph*{2.}
\begin{description}
  \item[1.] Schemeの場合
\begin{verbatim}
(define myexpt
  (lambda (n)
    (lambda (x)
      (cond
        ((= n 0) 1)
        (else (* ((myexpt (- n 1)) x) x))))))
(define sq
  (myexpt 2))
(define cu
  (myexpt 3))
\end{verbatim}
もちろんカリー化を使い、n乗するプログラムを返す関数myexptを作る。
ここではnをうまく使って、再帰で実現している。
sq,cuは引数を２乗、３乗するプログラムである。
実行してみると、
\begin{verbatim}
> (sq 4)
16
> (cu 7)
343
\end{verbatim}
となった。良さそうである。
\item [2.]Ocamlの場合
\begin{verbatim}
let rec myexpt n = 
  fun x -> if n = 0 then 1 
    else (myexpt (n-1) x) * x ;;
\end{verbatim}
Schemeのプログラムを変えただけである。
\begin{verbatim}
# let rec myexpt n = 
    fun x -> if n = 0 then 1 
      else (myexpt (n-1) x) * x ;;
val myexpt : int -> int -> int = <fun>
# let sq = myexpt 2;;
val sq : int -> int = <fun>
# let cu = myexpt 3;;
val cu : int -> int = <fun>
# sq 4;;
- : int = 16
# cu 7;;
- : int = 343 
\end{verbatim}
カリー化をすることで、実現できた。  
\end{description}

\subsection*{演習２}
\begin{description}
  \item[1.] 「与えられた関数を２回適用する」関数，つまり，たとえば ((double list) 777) を評価すると ((777)) が返ってくるような関数 \verb|double| を定義せよ． 
  \item[2.] (double (double f)) は，「関数 f を４回適用する」関数になりそうである．では ((double double) f) は何をする関数だろうか？
\end{description}
\subsubsection*{Answer}
\paragraph*{1.}
\begin{description}
  \item[1.] Schemeの場合
\begin{verbatim}
(define double
  (lambda (f)
    (lambda (x)
      (f (f x)))))
\end{verbatim}
実際に使ってみる。
\begin{verbatim}
> ((double list) 777)
((777))
\end{verbatim}
これでよさそうだ。
\item [2.]Ocamlの場合\\
資料に載っている。それをそのまま使う。
\begin{verbatim}
let double f x = f (f x);;
\end{verbatim}
\begin{verbatim}
# let double f x = f (f x);;
val double : ('a -> 'a) -> 'a -> 'a = <fun>
\end{verbatim}
定義は出来た。しかし、list処理を実行しようとすると、
\begin{verbatim}
# (double (fun x -> x :: []) 777);;
Characters 18-19:
  (double (fun x -> x :: []) 777);;
                    ^
This expression has type 'a list but is here used with type 'a
\end{verbatim}
のようにエラーとなった。

これは、引数となっている関数に原因がある。
問題は型で、関数を２回適用しようとすると、この場合一回目と型が違ってしまう。
それによって型エラーが出たのである。
これは今は解決できないので保留という事にしておく。

\paragraph*{2.}
\begin{description}
  \item[1.] Schemeの場合
\begin{verbatim}
(define four1
  (lambda (f)
    (double (double f))))

(define four2
  (lambda (f)
    ((double double) f)))
    
> ((four1 list) 777)
((((777))))

> ((four2 list) 777)
((((777))))
\end{verbatim}
doubleを２回適用する関数fourを２種類作った。
その上で、list処理させてみた。
結果、一見同じように見える。
そこでもっと違う関数を適用してみる事にする。
\begin{verbatim}
> ((four1 (lambda (x)
            (* x x))) 2)
65536
> ((four2 (lambda (x)
            (* x x))) 2)
65536
> ((four1 (lambda (x)
            (- x x))) 2)
0
> ((four2 (lambda (x)
            (- x x))) 2)
0
\end{verbatim}
どうも、この方法では良く分からない。
埒が明かないのでtraceしてみる。
\begin{verbatim}
> (trace four1)
(four1)
> ((four1 list) 777)
|(four1 #<primitive:list>)
|#<procedure:14:4>
((((777))))

> (trace four2)
(four2)
> ((four2 list) 777)
|(four2 #<primitive:list>)
|#<procedure:14:4>
((((777))))
\end{verbatim}
four関数で見る限り、全く同じ事をしている。
仕方がないのでdouble自体をtraceしてみる。

\begin{verbatim}
> (trace double)
(double)

> (double (double list))
|(double #<primitive:list>)
|#<procedure:14:4>
|(double #<procedure:14:4>)
|#<procedure:14:4>
#<procedure:14:4>

> ((double double) list)
|(double #<procedure:traced-double>)
|#<procedure:14:4>
|(double #<primitive:list>)
|#<procedure:14:4>
|(double #<procedure:14:4>)
|#<procedure:14:4>
#<procedure:14:4>
\end{verbatim}
(double (double list))はそのまま定義できているが、
((double double) list)は再帰的に定義されている。
しかし、結果は同じという珍しいものになっている。
仕事量からすると上の定義のほうがよさそうだ。

\end{description}
\item [2.] Ocamlの場合\\
今度はOcamlでやってみる。型を表示してくれるので面白い結果になるかもしれない。
\begin{verbatim}
# let four1 x = double (double x);;
val four1 : ('a -> 'a) -> 'a -> 'a = <fun>

# let four2 x = (double double) x;;
val four2 : ('a -> 'a) -> 'a -> 'a = <fun>
\end{verbatim}
traceをかけてみる。
\begin{verbatim}
# four1 (fun x -> x * x);;
four1 <-- <fun>
four1 --> <fun>
- : int -> int = <fun>

# four2 (fun x -> x * x);;
four2 <-- <fun>
four2 --> <fun>
- : int -> int = <fun>
\end{verbatim}
逆にOcamlでは何も分からないということが判明した。
結果的に、両者は同じ事をする関数であるといえる事が分かった。
\end{description}
\subsection*{演習３}
(a b c d) および (p q) という２本のリストを受け取ると、両者の「直積」 ((a p) (a q) (b p) (b q) (c p) (c q) (d p) (d q)) を返すような関数 product をなるべく簡潔に定義せよ． 

\subsubsection*{Answer}
http://www.altum.jp/math/exp2a/prac/12.htmlより、直積のSchemeのプログラムは
\begin{verbatim}
(define (direct-product G H)
  (apply append
         (map (lambda (x)
                      (map (lambda (y) (list x y)) H)
                      ) G)
         )
  )
\end{verbatim}
となる。
%applyが良く分からなかったので調べてみる。
%\verb|http://www.altum.jp/math/exp2a/intr/11.html|より
%"リストの中身を全て足したいとか、全てかけたいとか、そういう感じのことを手早く実行するには、 apply を使います。 (apply 関数 リスト) とすることで、リストを展開したものを引数として関数を実行します。例えば、 (apply + '(1 2 3 4)) とすると、 (+ 1 2 3 4) を実行して 10 を得ます。もちろんこういう演算子的な操作だけでなく、 (apply expt '(10 5)) とすれば 100000 となりますし、 (apply positive? '(7)) とすれば \verb|#t| となります。" 
%まず、applyをOcamlで実現したい。
%applyは畳み込み関数foldに似ている。
%よってfoldを使って実現してみる。
%> (apply  - '(1 2 3 4 5 6 7))
%-26
%となったので、これは
%\begin{verbatim}
%# fold_right (fun x y -> x - y) [1;2;3;4;5;6;7] 0;;
%- : int = 4
%# fold_left (fun x y -> x - y) 0 [1;2;3;4;5;6;7];;
%- : int = -28
%\end{verbatim}
%合わない。リストの最初が問題だ。関数適用が始まる位置が違う。
%それは置いておいて、
%\verb|let myapply_append l1 = fun l2 -> fold_left append (l1) l2 ;;|
%混乱。
%let product l1 l2 =

実際にSchemeで実行してみると、
\begin{verbatim}
> (define (direct-product G H)
  (apply append
         (map (lambda (x)
                      (map (lambda (y) (list x y)) H)
                      ) G)
         )
  )
> (direct-product '(1 2) '(3 4 5))
((1 3) (1 4) (1 5) (2 3) (2 4) (2 5))
> (direct-product '(2 3 4 5) '(2 3))
((2 2) (2 3) (3 2) (3 3) (4 2) (4 3) (5 2) (5 3))
\end{verbatim}
となった。
これをOcamlでも実装したい。
\begin{verbatim}
let direct_product g = 
 fun h -> map (fun x -> map (fun y -> x :: y :: []) h) g;;
# let direct_product g = 
   fun h -> map (fun x -> map (fun y -> x :: y :: []) h) g;;
val direct_product : 'a list -> 'a list -> 'a list list list = <fun>
# direct_product [1;2] [3;4];;
- : int list list list = [[[1; 3]; [1; 4]]; [[2; 3]; [2; 4]]]
\end{verbatim}

%ここまで出来た。Schemeではここでapplyを適用してlistを一個はずしているといえる。言えない。
上のプログラムだと、listの中身がおかしくなっている。
作ったリストをmapでリストに戻すからおかしくなるのだろう。

schemeだと
\begin{verbatim}
> (append '(1 2) '(3 4) '(5 6))
(1 2 3 4 5 6)
\end{verbatim}
が出来るが、Ocamlだと
\begin{verbatim}
# (@) [1;2;3] [4;5;6] [7;8;9];;
Characters 0-3:
  (@) [1;2;3] [4;5;6] [7;8;9];;
  ^^^
This function is applied to too many arguments,
maybe you forgot a `;'
# (+) 1 2;;
- : int = 3
# (@) [1] [2];;
- : int list = [1; 2]
\end{verbatim}
となってしまう。
appendはそのままでは引数を複数取れないし、applyもない（はず）。
しかし、appendの定義を少し変えれば出来そうだ。
applyとappendの機能を併せ持つような関数を定義してみる。
\begin{verbatim}
let rec apply_append l =
  match l with [] -> [] | 
   x :: rest -> append x (apply_append rest);;
\end{verbatim}
これを使うと、
\begin{verbatim}
let direct_product g = fun h -> 
 apply_append (map (fun x -> map (fun y -> x :: y :: []) h) g);;
\end{verbatim}
が定義できる。実際に使ってみる。
\begin{verbatim}
# let rec apply_append l = 
   match l with [] -> [] | 
    x :: rest -> append x (apply_append rest);;
val apply_append : 'a list list -> 'a list = <fun>
# let direct_product g = fun h -> 
   apply_append (map (fun x -> map (fun y -> x :: y :: []) h) g);;
val direct_product : 'a list -> 'a list -> 'a list list = <fun>
# direct_product [1;2] [3;4];;
- : int list list = [[1; 3]; [1; 4]; [2; 3]; [2; 4]]
# direct_product [1;2;3] [4;5;6];;
- : int list list =
[[1; 4]; [1; 5]; [1; 6]; [2; 4]; [2; 5]; [2; 6]; [3; 4]; [3; 5]; [3; 6]]
\end{verbatim}

となり、出来ていることがわかった。
\subsection*{リスト処理パターンの発見と畳み込み (fold) 関数}
\begin{verbatim}
(define sum-list
  (lambda (x)
    (cond
      ((null? x) 0)
      (else (+ (car x) (sum-list (cdr x)))))))
\end{verbatim}
Ocamlに直すと、
\begin{verbatim}
let rec sum_list l = match l with [] -> 0 | x :: rest -> x + (sum_list rest);;
\end{verbatim}


\begin{verbatim}
# let rec sum_list l = 
   match l with [] -> 0 
    | x :: rest -> x + (sum_list rest);;
val sum_list : int list -> int = <fun>
# sum_list [1;2;3;4;5;6;-2];;
- : int = 19
# sum_list [-1;-2;-3;-4;-5];;
- : int = -15
# sum_list [2];;
- : int = 2
\end{verbatim}

\begin{verbatim}
(define fold-right
  (lambda (f x unit)
    (cond
      ((null? x) unit)
      (else (f (car x) (fold-right f (cdr x) unit))))))
\end{verbatim}
Ocamlでは
\begin{verbatim}
let rec fold_right f l e =
 match l with
  [] -> e
  | x :: rest -> f x (fold_right f rest e);;
\end{verbatim}
\subsection*{演習４}
\begin{description}
  \item[1.] この fold-right を使って，これまでに出てきた sum-list, mymax, myappend と同じ機能を実現してみよ． 
  \item[2.] fold-right とは左右逆に (f ... (f (f (f unit a1) a2) a3) ... an) を計算する関数 fold-left は， 
\begin{verbatim}
(define fold-left
  (lambda (f unit x)
 	(cond
 	  ((null? x) unit)
 	  (else (fold-left f (f unit (car x)) (cdr x))))))
\end{verbatim}
と書ける．これを使って sum-list や mymax を定義してみよ．さらに，これを使って myreverse が定義できるかどうか，工夫してみよ． 
\end{description}
\subsubsection*{Answer}
\paragraph*{1.}
\begin{description}
  \item[1.]Schemeの場合
\begin{verbatim}
> (define sum-list
   (lambda (x)
      (fold-right + x 0)))
> (sum-list '(1 2 3 4 5 6 7 8 9))
45
> (sum-list '(-1 -2 -3 -4))
-10
\end{verbatim}
ただ単にfole-rightの引数に+を入れるだけで実現できる。xはリスト、unitは0である。\\

mymaxは以下のものであった。
\begin{verbatim}
(define mymax
  (lambda (l)
	(cond
	  ((null? l) "Not defined")
	  ((null? (cdr l)) (car l))
	  ((< (car l) (mymax (cdr l))) (mymax (cdr l))) 
	  (else (car l))))))
\end{verbatim}
これを改良すると
\begin{verbatim}
(define mymax
  (lambda (l)
    (cond
     ((null? l) "Not defined")
      (else (fold-right (lambda (x y)
        (cond
        ((< x y) y)
        (else x))) l -111)))))
\end{verbatim}
fold-rightの引数となる関数にcondを使う事でうまく比較を表現した。

この方法の問題点はリストがすべて-111以下ならばうまくいかないということである。
\begin{verbatim}
> (mymax '(1 3 5 6 7 ))
7
> (mymax '(5 67 9 33 235 35 67 ))
235
> (mymax '(-123 -567 -222))
-111
> (mymax '())
"Not defined"
> (mymax '(1 2 3 5 9))
9
\end{verbatim}
うまくいかせる方法もあるのだろうが、ちょっと分からなかった。\\

myappendは以下の様なものであった。
\begin{verbatim}
(define myappend
  (lambda (x y)
    (cond
      ((null? x) y)
      (else (cons (car x) (myappend (cdr x) y))))))
\end{verbatim}
これをfold-rightを使って定義すると
\begin{verbatim}
(define myappend
  (lambda (x y)
    (fold-right cons x y)))
\end{verbatim}

実際に使ってみると
\begin{verbatim}
> (myappend '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
> (myappend '(3 5 6) '())
(3 5 6)
\end{verbatim}


\item [2.]Ocamlの場合
\begin{verbatim}
let sum_list l = fold_right (fun x y -> x + y) l 0;;
\end{verbatim}
使ってみると
\begin{verbatim}
# let sum_list l = 
   fold_right (fun x y -> x + y) l 0;;
val sum_list : int list -> int = <fun>
# sum_list [1;2;3;4;5];;
- : int = 15
# sum_list [-2;3;4;5];;
- : int = 10
# sum_list [];;
- : int = 0
\end{verbatim}

mymaxの場合は少し難しく
\begin{verbatim}
let mymax l = if (null l) then "Not defined" 
 else fold_right (fun x y -> if (x < y) then y else x) l -111;;

\end{verbatim}
これで実行してみようとしたところ
\begin{verbatim}
# let mymax l = if (null l) then "Not defined" 
   else (fold_right (fun x y -> if (x < y) then y else x) l 0);;
Characters 51-101:
  let mymax l = if (null l) then "Not defined" 
   else (fold_right (fun x y -> if (x < y) then y else x) l 0);;
   
This expression has type 'a -> 'a but is here used with type int
\end{verbatim}
%# (fun x y -> if (x < y) then y else x);;
%Characters 30-34:
%  (fun x y -> if (x < y) theb y else x);;
%                                ^^^^
%Syntax error
%# (fun x y -> if (x < y) then y else x);;
%- : 'a -> 'a -> 'a = <fun>
%#   let mymax l = fold_right (fun x y -> if (x < y) then y else x) l 0;;
%Characters 52-106:
%    let mymax l = if (null l) then "Not defined" else (fold_right (fun x y -> if (x < y) then y else x) l 0);;
%                                                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
%This expression has type int but is here used with type string
%
というエラーが出た。Ocamlの強い型制限によって、Schemeのようにはいかないことが分かる。
そこで妥協して
\begin{verbatim}
#   let mymax l = fold_right (fun x y -> if (x < y) then y else x) l 0;;
val mymax : int list -> int = <fun>
# mymax [1;2;3;4;6];;
- : int = 6
# mymax [3;4;6;9;2;45;7];;
- : int = 45
\end{verbatim}
とした。実行もよさそうだ。
ただし、例によってリストの要素が全て0より小さいときは問題が起こる。

Ocamlでは型が違うとエラーが起こってくる。そこが難しい。

\begin{verbatim}
let myappend l1 l2 = fold_right (fun x y -> x :: y) l1 l2;;
\end{verbatim}

myappendを実行すると以下のようになる。
\begin{verbatim}
# let myappend l1 l2 = fold_right (fun x y -> x :: y) l1 l2;;
val myappend : 'a list -> 'a list -> 'a list = <fun>
# myappend [1;2;3] [4;5;6];;
- : int list = [1; 2; 3; 4; 5; 6]
# myappend [3;5;7] [24;667;23];;
- : int list = [3; 5; 7; 24; 667; 23]
\end{verbatim}
\end{description}
\paragraph*{2.}
fold-leftをOCamlで書くと
\begin{verbatim}
let rec fold_left f e l = 
 match l with [] -> e | x :: rest -> fold_left f (f e x) rest;;
\end{verbatim}
\begin{description}
  \item[1.] Schemeの場合

\begin{verbatim}
> (define sum-list
   (lambda (x)
      (fold-left + 0 x)))
> (sum-list '(1 2 3 4 5 6 7 8 9))
45
> (sum-list '(-1 2 -3 4))
2
\end{verbatim}

\begin{verbatim}
(define mymax
  (lambda (l)
    (cond
      ((null? l) "Not defined")
      (else (fold-left (lambda (x y)
        (cond
          ((< x y) y)
          (else x))) -111 l)))))
> (mymax '(1 2 3 4 5))
5
> (mymax '(3 4 7 2 3 98 3 2 ))
98
\end{verbatim}

\begin{verbatim}
(define myreverse
  (lambda (seq)
    (fold-left (lambda (x y)
      (cons y x)) '() seq)))
> (myreverse '(2 4 5))
(5 4 2)
> (myreverse '(1 2 3 4 5 6 7 8 9))
(9 8 7 6 5 4 3 2 1)
\end{verbatim}
\item [2.] Ocamlの場合
\begin{verbatim}
let sum_list l = fold_left (fun x y -> x + y) 0 l;;
\end{verbatim}

\begin{verbatim}
# let sum_list l = fold_left (fun x y -> x + y) 0 l;;
val sum_list : int list -> int = <fun>
# sum_list [1;2;43;5];;
- : int = 51
# sum_list [1;-2;5;7];;
- : int = 11
# sum_list [-4;0];;
- : int = -4
\end{verbatim}

Ocamlでmyreverseを定義すると
\begin{verbatim}
let myreverse l = fold_left (fun x y -> y :: x) [] l;;
\end{verbatim}

\begin{verbatim}
# let myreverse l = fold_left (fun x y -> y :: x) [] l;;
val myreverse : 'a list -> 'a list = <fun>
# myreverse [1;2;3;4;5];;
- : int list = [5; 4; 3; 2; 1]
# myreverse [];;
- : 'a list = []
# myreverse [[1;2;4];[2;3;5];[4;7;8]];;
- : int list list = [[4; 7; 8]; [2; 3; 5]; [1; 2; 4]]
\end{verbatim}
\end{description}

\subsection*{演習５（汎用ソーター）}
\begin{description}
  \item[1.] 整数を要素とするリストを降順に整列（ソーティング）する関数を書け．効率は O(n2) よりも悪くなければよいものとする．
  \item[2.] 降順にしか整列できないのでは汎用性に欠けるので，上で書いた整列関数の「整数を要素とする」および「降順」という部分を一般化した整列関数を書け．たとえば (sort >= '(3 1 4 1 5 9)) を実行すると (9 5 4 3 1 1) が返ってくるようになっていればよい．（順序判定のための >= を引数に指定しているところに注目．)
  \item[3.]それを用いて，「多数の x-y 座標 （リスト (x y) で表現，x, y は整数） のリストをもらって，x 座標の小さな順 （ただし x 座標が同じ点は y 座標の小さな順） に並べ替える」 作業を行なってみよ．
  
\begin{description}
  \item[例] ((4 2) (1 3) (3 5) (8 6) (4 7) (8 1)) を与えたら
     ((1 3) (3 5) (4 2) (4 7) (8 1) (8 6)) が返ってくればよい．
\end{description}

\end{description}

\subsubsection*{Answer}
%2.の比較関数の参考
%\verb|http://www.stdio.h.kyoto-u.ac.jp/~hioki/gairon-enshuu/kadai2003/3.html|
Ocamlの資料に２種類ソートが載っている。
insertion sortで考えてみる。
\begin{verbatim}
let rec insert (x : float) = 
 function [] -> [x] |
  (y :: rest) as l -> if x < y then x :: l 
   else y :: (insert x rest);;

let rec insertion_sort = 
 function [] -> [] | x :: rest -> insert x (insertion_sort rest);;
\end{verbatim}
より
\begin{verbatim}
(define insert
  (lambda (y)
    (lambda (l)
      (cond
        ((null? l) (cons y '()))
        (else (cond
                ((< y (car l)) (cons y l))
                (else (cons (car l) ((insert y) (cdr l))))))))))
     
(define insertion_sort
  (lambda (l)
    (cond
     ((null? l) '())
     (else ((insert (car l)) (insertion_sort (cdr l)))))))
\end{verbatim}
\begin{verbatim}

\end{verbatim}

となる。実行してみると
\begin{verbatim}
> (insertion_sort '(1 3 5 2 4))
(1 2 3 4 5)
> (insertion_sort '(3 5 67 1 34))
(1 3 5 34 67)
\end{verbatim}

となったので大丈夫そうだ。

\begin{verbatim}
(define insert_op
  (lambda (op x l)
    (cond
      ((null? l) (cons x '()))
      (else 
        (cond
          ((op x (car l)) (cons x l))
          (else (cons (car l) (insert_op op x (cdr l)))))))))

(define i_s_op
  (lambda (op l)
    (cond
      ((null? l) '())
      (else (insert_op op (car l) (i_s_op op (cdr l)))))))
      
> (insert_op < 7 '(1 3 5 8))
(1 3 5 7 8)
> (i_s_op < '(1 3 5 2 4))
(1 2 3 4 5)
> (i_s_op > '(1 3 5 2 4))
(5 4 3 2 1)

\end{verbatim}
となったので実装できた。
ただし、これはopに何が入っても良くなっているので、注意。

%OcamlからSchemeに書き換えるときは、きちんとその通りにやらないとエラーが出る。
%(define insert
%  (lambda (x l)
%    (cond
%     ((null? l) '(x))
%     ((< x (car l)) (cons x  l))
%     (else (cons (car l) (insert x (cdr l)))))))
%ではうまくいかなかった。
%さらに、'(y)では駄目で、cons y '()としないとエラーが起こった

Ocamlでやってみる。
\begin{verbatim}
# let rec insert_op op (x : float) l = 
 match l with [] -> [x] | (y :: rest) as l -> 
  if (op x y) then x :: l else y :: (insert_op op x rest);;
val insert_op : (float -> float -> bool) -> float -> float list 
 -> float list = <fun>
  
# insert_op (fun x y -> if x < y then true else false) 2. [3.;5.;1.];;
- : float list = [2.; 3.; 5.; 1.]
\end{verbatim}
insertは実装できた。ただ、引数が関数のため指定が長くなってしまう。

\begin{verbatim}
# let rec i_s_op op = 
   function [] -> [] | x :: rest -> insert_op op x (i_s_op op rest);;
val i_s_op : (float -> float -> bool) -> float list -> float list = <fun>
# i_s_op (fun x y -> if x < y then true else false) [1.;3.;5.;2.;4.];;
- : float list = [1.; 2.; 3.; 4.; 5.]
\end{verbatim}
多分、出来た。

\section*{感想}
思った事、Schemeは上部で定義を確認しながらできるところは良い。
Schemeだと書き易いものも、Ocamlだと書き易いものも、両方ある。
\begin{thebibliography}{1}%{}内に参考文献の総数を書く
\bibitem{1}\verb|http://www.altum.jp/math/exp2a/prac/12.html|\\
直積を解くときに役立った。

\bibitem{2}\verb|http://www.sampou.org/scheme/sicp/answer/sicp.2.2.html|\\
部分集合はここでは使わなかったが、勉強になった。

\bibitem{3}\verb|http://www.sampou.org/scheme/sicp/mailingList/msg00880.html|\\
\bibitem{4}\verb|http://www.sampou.org/scheme/sicp/mailingList/msg00045.html|\\
畳み込みは難しかったので、大いに役立った。
\end{thebibliography}

\end{document}
