もうすぐ社会人になるよ

入社日が近づいてきました。自己紹介の言葉とか考えておかなきゃ。気が重い……。

しばらくは会社が忙しくてブログを更新することは出来ないかも。

OCamlのお勉強 その8 〜リストの練習問題〜

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

今回は、本に記載されている練習問題を解いていきます。

練習問題 5.2 次の関数を定義しなさい。

5.5 練習問題，p106-107

以下に与えられた9つの関数を定義していきます。

正の整数nから1までの降順リストを生成する関数downto1。

# let downto1 n =
    let rec downto1' i l =
      if i > n then l
      else downto1' (i + 1) (i :: l) in
    downto1' 0 [];;
val downto1 : int -> int list = <fun>
# downto1 5;;
- : int list = [5; 4; 3; 2; 1; 0]

このくらいならすぐに書けました。一応、末尾再帰にしてあります。今後も練習のため末尾再帰可能なものについてはなるべく末尾再帰で書いていきます。

与えられた正の整数のローマ数字表現（文字列）を求める関数roman（I = 1，V = 5，X = 10，L = 50，C = 100，D = 500，M = 1000です）。

# let roman dict n =
    let rec roman' dict n s =
      let rec find f l =
        match l with
        | (a', b) :: rest -> if f a' then (a', b) else find f rest in
      match n with
      | 0 -> s
      | _ -> let (i, r) = find (fun x -> n >= x) dict in　roman' dict (n - i) (s ^ r) in
    roman' dict n "";;
(* 警告を省略 *)
val roman : (int * string) list -> int -> string = <fun>

find関数はfが真となる要素をリストlの中から見つける関数ですが、要素が見つからない場合については定義してありません。そのため、find関数のマッチ式が網羅的でないという警告が出ています。今は例外処理のやり方がわからないので無視しておきます。以下は実行結果です。

# let romans = [(1000, "M"); (500, "D"); (100, "C");
                     (50, "L"); (10, "X"); (5, "V"); (1, "I")];;
(* romansの表示を省略 *)
# roman romans 1984;;
- : string = "MDCCCCLXXXIIII"
# let romans = [(1000, "M"); (900, "CM"); (500, "D");
                (400, "CD"); (100, "C"); (90, "XC");
                (50, "L"); (40, "XL"); (10, "X");
                (9, "IX"); (5, "V"); (4, "IV"); (1, "I")];;
(* romansの表示を省略 *)
# roman romans 1984;;
- : string = "MCMLXXXIV"

辞書を入れ替えることでより正確な表記を行います。

与えられたリストのリストに対し、（内側のリストの）要素の総数を返す関数nested_length。

予め、与えられたリストの長さを返す関数lengthを定義しておきます。

# let length l =
    let rec length' l n =
      match l with
      | [] -> n
      | _ :: rest -> length' rest (n + 1) in
    length' l 0;;
val length : 'a list -> int = <fun>

続いてnested_lengthを定義します。

# let nested_length ll =
    let rec nested_length' ll n =
      match ll with
      | [] -> n
      | l :: rest -> nested_length' rest (n + length l) in
    nested_length' ll 0;;
val nested_length : 'a list list -> int = <fun>
# nested_length [[1; 2; 3]; [4; 5]; [6]; [7; 8; 9; 10]];;
- : int = 10

確かに計算できています。

今回はここまで。次回もリストの練習問題をいくつか解いていきます。

OCamlのお勉強 その7 〜リスト〜

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

リストを作成できる。リストは再帰的なデータ構造である。

• 空リスト [] はリスト
• リスト l の先頭に要素 e を加えた e :: l はリスト

# [0; 1; 2; 3];;
- : int list = [0; 1; 2; 3]
# [];;
- : 'a list = []
# 3 :: [];;
- : int list = [3]
# 2 :: 3 :: [];;
- : int list = [2; 3]
# 1 :: 2 :: 3 :: [];;
- : int list = [1; 2; 3]
# 0 :: 1 :: 2 :: 3 :: [];;
- : int list = [0; 1; 2; 3]

リストのリストなども作れます。ただし、リストの各要素は同じ型でなければなりません。

パターンマッチングによりリストの先頭要素と後に続くリストそれぞれに変数を束縛できる。match式でパターンによる分岐を記述できる。

# let rec project f l =
    match l with
    | [] -> []
    | x :: rest -> f x :: project f rest;;
val project : ('a -> 'b) -> 'a list -> 'b list = <fun>
# project string_of_int [0; 1; 2; 3; 4];;
- : string list = ["0"; "1"; "2"; "3"; "4"]
# project (fun x -> x * x) [0; 1; 2; 3; 4];;
- : int list = [0; 1; 4; 9; 16]

project関数は与えられた関数fに基づいてリストの射影を求める関数です。通常、mapやselectなどと名付けられることが多いです（実際、OCamlにはmap関数があります）。リストに対する高階関数の基本ですね。

リストの各要素に対して処理をするような関数はほとんど上記のように「空リストの場合は何かを返して終了、そうでない場合は残りのリストに対して再帰」という形になります。

match式を組み込んだ匿名関数をfunction構文で定義できる。

# let rec project f = function
    | [] -> []
    | x :: rest -> f x :: project f rest;;
val project : ('a -> 'b) -> 'a list -> 'b list = <fun>

function構文を使うことでmatch with式より少しだけ書くのが楽になります。

今回はここまで。次回はリストの練習問題をいくつか解いていきます。

PowerShellですごいテクニックを発見した！

最近はPowerShellを常に起動していて、コマンドプロンプトを使わずにPowerShellから色々作業するようにしている（Pythonなどの対話環境もPowerShellから起動している）のですが、そのようななかで個人的にこれはすごいと思えるテクニックを発見しました。

それはたったひとつのコマンド、

PS > powershell

です。「PowerShell内でPowerShellを起動する」。何が嬉しいかというと、スクリプトなりを実行してPowerShellが強制終了した場合に内側のPowerShellが強制終了するだけで外側のPowerShellは生き残るという点です。エラーメッセージも残せます。これで自分でもどうかなと思うような実験的なスクリプトの実行も怖くありません。これはすごい！ 画期的！

あー、でもこれ、シェル使いの方には常識だったりするんでしょうか。そうだったら恥ずかしい……。

追記（2008年03月22日）

2chのスレッド「Windows PowerShell （正式版リリース）1.0」の592番目のレスにすでに同様のテクニックが書かれているというコメントをいただきました。けっこうすごい発見だと思ったのですが、やはりというかなんというか、先駆者がおられました。

ただ、こういったコメントをいただくということは「シェル内シェル」はあまり一般的ではないようにも見受けられますね。その点については安心しました。

OCamlのお勉強 その6 〜多相と型推論、コンビネータ〜

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

型推論によって型が確定されない引数を持つ関数は多相的関数となる。

# let add x y = x + y;;
val add : int -> int -> int = <fun>
# let k x y = x;;
val k : 'a -> 'b -> 'a = <fun>

関数addはint型の値x、yを受け取ってint型の値を返す関数となっているのに対し、関数kは何らかの型'a、'bの値x、yを受け取って'a型の値を返す関数となっています。addについてはx + yという式からx、yはint型だと推論できますが、kについてはx、yの具体的な型は決めようがありません。こういった関数を多相的関数というそうです。C#で近い機能というとジェネリクスですね。

この本では、ケーススタディとしてコンビネータに触れています（アカデミックですね！）。最近Yコンビネータで話題のあれです。先ほどの関数kは、基本となる2つのコンビネータのうちの1つで、Kコンビネータと呼びます。もうひとつはSコンビネータです。

# let s x y z = x z (y z);;
val s : ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>

Kは定数関数を返す関数で、Sは置換演算子（なんでこう呼ぶのかはわかりません）です。Kについては、「定数関数を返す」ということをそのまま表現すると

# (* xを受け取り、どんな引数だろうと常にxを返す関数を返す *)
  let k x = fun y -> x;;
val k : 'a -> 'b -> 'a = <fun>

とも書けますね。SとKの組み合わせで様々な関数を構築できます。S、Kの組み合わせの単純な例としてIコンビネータがあります。

# s k k 19;;
- : int = 19
# s k k "hello";;
- : string = "hello"

Iコンビネータは与えられた引数をそのまま返す恒等関数です。なぜこのような動作するのでしょうか。擬似コードで関数適用の流れを追ってみます。

s x y = fun z -> x z (y z)        (* sの書き直し *)
s k k = fun z -> k z (k z)        (* x、yをkで置き換え *)
      = fun z -> k z (fun a -> z) 
      = fun z -> z                (* k x y = xより *)

確かにs k kは恒等関数となっています。コンビネータに関する練習問題も解いてみました。

恒等関数を、s k kで表現したように、関数fun x y -> yをコンビネータsとkを関数適用のみで（funやletによる関数定義を使わずに）組み合わせた形で表現しなさい。

4.4 練習問題，p83

# k (s k k);;
- : '_a -> '_b -> '_b = <fun>
# k (s k k) 0 1;;
- : int = 1
# k (s k k) 0 "later";;
- : string = "later"

合っていそうです。先ほどのように関数適用の流れを追ってみます。

k (s k k) = k (fun y -> y)
          = fun x -> (fun y -> y)
          = fun x y -> y

確かにfun x y -> yとなっています。

今回はここまで。次回はリストについてです。

Jim DunlopのUltexピックを買ったよ

Jim DunlopのUltexピック、0.73mmと1.0mmを買いました。サイのマークがトレードマークです。ふだんはTerry Gouldの黒いピック（0.8mm。鳥のマーク）かJim Dunlopの黒いTortexピック（0.73mm。カメのマークのやつです）を使用しているのですが、ちょっと目先を変えてみようということで買ってみました。ClaytonのUltexピックとどちらにしようかで迷ったのですが、エッジの処理が滑らかなJim Dunlop製を選びました。

音に関しては、UltexはTerry GouldやTortexに比べて高音が良く出ているように感じました。驚いたのは、Terry GouldやTortexに比べると明らかにつるつるすべすべした表面なのに、実際に演奏するとなぜか一番滑りにくいという点です。手に吸い付く感触。

なかなか良い感触なのでしばらく使ってみようと思います。

OCamlのお勉強 その5 〜カリー化、高階関数、匿名関数〜

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

カリー化によって引数を2つ以上とる関数を表現できる。また、カリー化によって表現された関数は引数の部分適用ができる。

# let concat_string s1 s2 = s1 ^ " " ^ s2;;
val concat_string : string -> string -> string = <fun>
# concat_string "Hello" "World!";;
- : string = "Hello World!"
# let greet = concat_string "Hello";;
val greet : string -> string = <fun>
# greet "John.";;
- : string = "Hello John."
# greet "Anne.";;
- : string = "Hello Anne."

文字列を2つ受け取る関数concat_stringに1つだけ文字列を与えると、文字列を1つ受け取る関数を返しています。concat_stringの型に注目すると、

string -> string -> string

になっています。これは

(* stringを受け取ってstring -> stringを返す型 *)
string -> (string -> string)

と読めます。実際、greetの型は

string -> string

になっています。これを部分適用というそうです。前回、末尾再帰関数を書くために2引数の関数を何の気なしに定義していましたが、これはカリー化を使用した表現だったようです。

高階関数を定義できる。

# let rec aggregate_n f s n =
    if n = 0 then s
    else f (aggregate_n f s (n - 1)) n;;
val aggregate_n : ('a -> int -> 'a) -> 'a -> int -> 'a = <fun>
# let add a b = a + b;;
val add : int -> int -> int = <fun>
# aggregate_n add 0 10;;
- : int = 55

aggregate_nは1からnまでの数について、初期値をsとして関数fで集約していく関数です。fは「どのように集約していくか」を決める関数となります。fにsumを渡せば1からnまでの数を足すことになります。

C#では似た機能としてデリゲートがありますね。こちらの場合、カリー化と組み合わせることでいろいろできそうです。

匿名関数を作成できる。匿名関数はfun (引数リスト) -> (式)と書く。

# let multiply = fun x y -> x * y;;
val multiply : int -> int -> int = <fun>
# aggregate_n multiply 1 10;;
- : int = 3628800
# aggregate_n (fun s n -> s + n) 0 10;;
- : int = 55
# aggregate_n (fun s n -> s * n) 1 10;;
- : int = 3628800

これはC#（〜2.0）でいうところの匿名デリゲートのようなものですね。匿名関数もまた1つの値なので、変数を匿名関数に束縛することができるというのも面白いです。上記のコード例では変数multiplyを匿名関数に束縛しています。いったん束縛してしまえば、あとは通常の関数名として使用できます。

今回はここまで。次回は多相と型推論についてです。