OCamlのお勉強 その4 〜再帰関数〜

「プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~」を読んでの勉強記録です。

再帰関数の定義ではletの後にrecを付ける。コメントは(**)で囲む。

# let rec sum n = (* 1からnまでの合計 *)
    if n = 0 then 0
    else n + sum (n - 1);;
val sum : int -> int = <fun>
# sum 10;;
- : int = 55
# let rec fib n = (* n項目のフィボナッチ数を求める *)
  if n = 1 || n = 2 then 1 else fib (n - 1) + fib (n - 2);;
val fib : int -> int = <fun>
# fib 7;;
- : int = 13

関数内で変数や関数を定義できる。

# let fib n = (* 改良版fib *)
    let rec fib' n =
      if n = 1 then (1, 0)
      else let (y, x) = fib' (n - 1) in (y + x, y) in
    let (a, _) = fib' n in
    a;;
val fib : int -> int = <fun>

再帰させる場合はrecが必要というのが変わっています。もともとlet定義は左辺の変数を右辺では使えないので、再帰的に使えるようにするためにrecで明示するというのは筋が通っている気がします。

末尾再帰の最適化により、末尾呼び出しのみの関数は一定量以上のスタックを消費しない。

# let rec tail_sum1 n a = (* 末尾再帰sumその1。nから1までaに足しこむ *)
    if n = 0 then a
    else tail_sum1 (n - 1) (a + n);;
val sum : int -> int -> int = <fun>
# let tail_sum2 n = (* 末尾再帰sumその2。1からnまでaに足しこむ *)
    let rec tail_sum2' i a =
      if i > n then a
      else tail_sum2' (i + 1) (a + i) in
    tail_sum2' 1 0;;
val tail_sum2 : int -> int = <fun> 
# sum 1000000;;
Stack overflow during evaluation (looping recursion?).
# tail_sum1 1000000 0;;
- : int = -363189984
# tail_sum2 1000000;;
- : int = -363189984

sumではスタックオーバフローの例外が出ていますが、2つのtail_sumはしっかり計算しています（ただし、数字が大きくなりすぎて整数オーバーフローが起きています）。また、tail_sum2'では外側のtail_sum2の引数であるnを自身の引数であるiとの比較で使用している点にも注意が必要です。

通常の再帰関数を末尾再帰にするポイントは答えの途中経過を関数の引数にすることです。sumでは再帰的なsumの結果とその時点でのnを加算するために、再帰呼び出し時のコンテキストをスタックに格納します。一方、tail_sumでは引数aとしてそれまでの結果を渡しているので再帰呼び出しの結果とその時点でのnとの計算をしないで済みます。このためスタックに呼び出し前の状態を保存しておく必要が無くなります。これが末尾再帰の最適化というものらしいです。今まで名前だけは聞いてきましたが、やっとどういうものか理解できました。

今回はここまで。次回はカリー化、高階関数、匿名関数についてです。

OCamlのお勉強 その3 〜組〜

「プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~」を読んでの勉強記録です。

組は値を並べたものである。(値1, 値2, ... , 値n)。各値の型は独立。組もまた値なので入れ子に出来る。

# ("John", 20);;
- : string * int = ("John", 20)
# let rect = ((3, 5), (8, 10));;
val rect : (int * int) * (int * int) = ((3, 5), (8, 10))

パターンマッチングにより組の各値に変数を束縛できる。値が必要ない場合はワイルドカードパターン（_）を使用する。

# let (name, age) = ("John", 20);;
val name : string = "John"
val age : int = 20
# let (position, (width, height)) = ((3, 5), (8, 10));;
val position : int * int = (3, 5)
val width : int = 8
val height : int = 10
# let (_, y) = position;;
val y : int = 5

組からの値の取り出し方が独特です。Pythonの経験からインデックスによるアクセスの方が楽に感じますが、それだと構造があいまいになって推論しにくそうですね。パターンマッチングだと必ず値に名前がつくというのも良いと思います。

組を引数に取る関数や組を返す関数を作成可能。

# let sum_and_diff (x, y) = (x + y, x - y);;
val sum_and_diff : int * int -> int * int = <fun>

3.4.3 組を用いた関数，p43

練習問題も解いてみました。

任意の整数x、yに対し、f (sum_and_diff (x, y))が(x, y)を返すような関数f。

3.4.4 練習問題，p44

# let f (x, y) = ((x + y) / 2, (x - y) / 2);;
val f : int * int -> int * int = <fun>
# f (sum_and_diff (10, 15));;
- : int * int = (10, 15)

このくらいなら簡単に解けます。今後も練習問題のうちいくつか取り上げて解いていく予定です。

今回はここまで。次回は再帰関数についてです。

OCamlのお勉強 その2 〜関数〜

「プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~」を読んでの勉強記録です。

関数もletで定義できる。let (関数名) (引数) = (式)。型はOCamlコンパイラによって型推論されるため明示する必要はない。

# let square x = x * x;;
val square : int -> int = <fun>
# square 10;;
- : int = 100

与えられたxを2乗した値を返す関数squareを定義しています。コンパイラからの応答は「squareはint -> int型の関数」となっています。*からxはintであり、評価結果もまたintであると推論しているようです。

if式により条件分岐が可能。条件式はbool型の値（trueまたはfalse）を返す式であり、thenのあとの式とelseのあとの式は同じ型の値を返さなければならない。

# let x = 10;;
val x : int = 10
# if x < 5 then "less than 5" else "more equal than 5";;
- : string = "more equal than 5"
# let s = "hello";;
val s : string = "hello"
# if s = "hello" then "equal" else "not equal";;
- : string = "equal"

if式は式なので必ず値を返さなければなりません。つまり、else節が不可欠ということです。OCamlは式中心というのはこういうところにも表れています。比較演算子は他の言語とほぼ同じです。文字列も比較できます。ただ、同値の比較に=を使うのは珍しいかもしれません。変数束縛はletを伴うので、定義と比較で=を混同しないで済むためだと思われます。

let式により局所的な定義を与えることができる。let (局所変数の束縛) in (式) 。局所変数は(式)でのみ使用でき、let式全体の値は(式)の値。

# let circumference r =
    let pi = 3.14159 in
    2.0 *. pi *. r;;
val circumference : float -> float = <fun>
# circumference 1.0;;
- : float = 6.28318

let定義内、let式内でlet式を使用できる。同名の局所変数はより近いものが使用される。また、let定義、let式ともにandで2つ以上の変数を同時に束縛できる。

# let x = let x = 3 and y = 5 in let x = x * 2 in x + y;;
val x : int = 11

独特の記法に最初は戸惑いました。特に、let式が入れ子になると慣れていない身ではかなり読みにくく感じます。考え方としては、「y = (xを使った式) ただし x = ... とする」というものに近いかもしれません。局所変数の名前がかぶった場合の判断基準は他の言語と大差ありませんね。

今回はここまで。次回は組についてです。

OCamlのお勉強 その1 〜式、値、型〜

「プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~」を読んでの勉強記録です。

OCamlでは式が中心。式を評価すると値が得られる。値は何らかの型を持つ。OCamlでは、式を評価する前に型の整合性をチェック（型付け、型検査）する。

Ocamlには、基本的な型として整数型（int）、実数型（float）、文字型（char）、文字列型（string）がある。

# -3 * (1 - 6 / 2) mod 4;;
- : int = 2
# 2.5 *. 3.0 +. (10.0 -. 1.5) /. 2.0;;
- : float = 11.75
# 'c';;
- : char = 'c'
# "Hello World!";;
- : string = "Hello World!"
# "Hello" ^ " OCaml " ^ "World!";;
- : string = "Hello OCaml World!"

文字列は文字のリストというわけではなく、独立した型が与えられているようです。整数と実数で使う演算子が違うこと、文字列の連結には^を使うことが特徴的です。

letキーワードを使うことで変数を値に束縛することができる。

# let pi = 3.14;;
val pi : float = 3.14
# let r = 3.0;;
val r : float = 3.
# let area = r *. r *. pi;;
val area : float = 28.26
# let pi = 3.0;;
val pi : float = 3.
# let area' = r *. r *. pi;;
val area' : float = 27.

letによる変数束縛は見た目としては他の言語における変数宣言とそう変わりません。しかし、あくまで束縛であって代入ではないそうです。また、変数名に'を使えるという点も珍しいですね。

今回はここまで。次回から関数について学んでいきます。

OCamlのお勉強 その0 〜準備〜

「プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~」を読んでの勉強記録です。

まずは環境の構築ということで、The Caml LanguageのDownloadからWindows向けのインストーラをダウンロードしてインストールしました。Windows向けにはMinGWベースとVisual C++ベースの2つがあったので、Microsoftの方をインストールしました。readmeファイルによるとVisual C++ベースのほうはバイトコードインタプリタの速度がMinGWベースのものに比べて70%ほどだったり、コンパイル時にCコードとリンクさせるにはVisual C++のコンパイラが必要だったりするようです。インストール自体は簡単で、実行ファイルへのパスも通しておいてくれます。

この本では、対話式コンパイラを使ってコード例を示しています。対話式コンパイラはocaml.exeです。対話式コンパイラでは

# 1 + 2;;
- : int = 3

のように#のあとに続けてプログラムを入力します。;;が区切りとなり、そこまでのプログラムが評価されてプロンプトに表示されます。

今回はここまで。次回からOCamlプログラミングに入ります。

OCaml始めました

関数型言語のひとつ、OCamlの勉強を始めました。入門用の書籍が2冊ありましたが、より説明が丁寧だと感じた「プログラミング in OCaml」を購入しました。

	プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~ 販売元 : Amazon.co.jp 本 価格 : ￥
>>Seesaa ショッピングで買う

やっぱり、新しい言語の習得は楽しいですね。OCamlの勉強過程についてはブログに書いていきたいと思います。

ギター用ストラップ Neotech SLIMLINE GUITAR STRAP を買ったよ

ギター用のストラップを新調しました。Neotech社のSLIMLINE GUITAR STRAPというストラップです。Neotechというメーカーは聞いたことが無かったのですが、カメラ用のストラップで有名なOP/TECHというメーカーのdivision（どう訳せば良いのかわかりません。分社？）で、いろいろな楽器メーカーにストラップのOEM供給をしているそうです。

細めなのですが、肩に当たる部分に低反発素材を採用しているため肩に負担がかかりません。ふんわりしたフィット感も良いです。

また、Slimlockというロック機構を搭載していて、突然ギターから外れたりすることもありません。ロック機能付きのストラップというと、DiMarzioのクリップロックストラップが有名ですが、クリップロックではストラップピンを外してネジで直接ギターに取り付けるという作業が必要になるのに対して、Slimlockはストラップピンはそのままで、簡単に装着可能です。

見た目の貧弱さのわりに値が張る（確か4800円ぐらい）ことから購入を少し躊躇したのですが、実際使ってみるとかなり良いものでした。機能を重視する方におすすめのストラップです。

2008年の目標

学生生活最後の大詰めとして論文作成、発表準備に追われているうちにもう2008年も1ヶ月終わってしまいました。

ブログもめっきりご無沙汰です。まあ、プログラミングについてつらつら書くためのブログなので量についてはあまり重視していないのですが、もっと質の高い記事を書いていきたいとは常々考えています。

「質の高い記事」というと漠然としているので、一つ明確な目標を立てました。僕はプログラミング、特にC#やPowerShellなど.NET関係に興味があります。で、僕の知っている限りで国内の.NET界隈で一番とんがった方といえばnsharp（＝名無しさん♯？）さんだと思っているので、nsharpさんにコメントもらえるような記事を書いてみたい、というのが今年の目標です。

という訳で、今年はLINQ to Object、ラムダ式、関数型言語あたりをキーワードに学んでいきたいと思います。