FSharpでmatch式をつかった直積の書き方

JavaやC#の場合、二重のfor文を実行すれば、x,yの直積が完成します。F#でもリストの内包表記で、二重のforにより直積が作れます。関係代数について調べていた時に、stackoverflowにmatch式を使った直積の書き方を見つけました。

関係代数やリレーショナルデータベースは、集合と関係してくるので、数学の集合論や関数型プログラミングで写像とかで学んだ知識がそのまま使えるのはうれしいです。

http://www.cs.reitaku-u.ac.jp/infosci/rdb/rdb02.html

関係代数

ラムダ計算、チャーチ数をF#で試したときのURL集

関数型言語fのラムダ計算で引き算ができません の記事を書いたときに多くのラムダ計算の資料にお世話になりました。また試すときに忘れそうなので、URLを残しておきます。

関数型プログラミング言語F#初心者向けURL集

関数型プログラミング言語F#を学んでいくうちにいろんなサイトを見つけたので整理すると同時に公開して情報共有します。

関数型の考え方が分かるサイト

F# for fun and profit は英語のサイトなので大変ですが、Learning  F# で関数型で考える心得や、やっていいこと悪いことなどを説明しています。また、Thinking functionally は他の入門サイトと異なり、集合、写像、関数の簡単な説明から始まります。英語ですが関数型プログラミング言語でこの土台が分かるとHaskellやStandardMLなどの基礎部分は同じものとして理解することができます。英語を読むのは本当に大変ですが、このサイトはお勧めです。

文法を学習するために便利なサイト

普通リファレンスは厳密で難しい場合が多いですが、マイクロソフト公式のF# 言語リファレンス は、説明とともに、すぐ動かせる小さなサンプルが豊富にあります。なので、適当な入門サイトでおおよその文法を学んだあとは、このリファレンスを観るのが効率が良いです。

かずきのBlog@hatena さんのサイトで、以下のURLに、F#の文法の記事が25個ぐらいあります。

 

 

興味深い資料

プログラミングで同値関係が分かる!

数学の「関係と集合」まで進んだら、同値関係(Equivalence relation)の説明で、反射律、対称律、推移律、反対称律が出てきました。教科書の言い回しは難しくて何言っているのか分からなかったのですが、プログラミングで考えれば簡単なことでした。関係演算子の機能チェックをするルールを律と言っているだけでした。

プログラミングで使う演算子のおさらい

私たちは普段何気なく使っていますが、演算子はいくつかグループに分けられます。それでイコール記号や大なり小なりは関係演算子と言います。

算術演算子 + - * / %など

関係演算子 == != < <= > >=

論理演算子 && || !

関数型言語の演算子を見てみる

F#のような関数型プログラミング言語では、算術演算子、関係演算子、論理演算子は、どれも関数として使えます。1 + 1のような加算演算子は、中置記法で使いますが、()を使うと前置記法にできます。この前置記法は、プログラミングで私たちが良く作る関数と同じ順番です。関数名、第一引数、第二引数となっています。

JavaScriptの場合は、add関数を作ってx + yをその中に書けば、算術演算子+を別名のadd関数として作れます。

関数型言語の場合は、先ほどの前置記法があるので、add関数で包むという感じではなく、別名を用意する感じです。以下のようになります。

 

ここでひとつ分かることがあります。私たちはプログラミングで演算子を使っていますが、関数で演算子を包んであげれば、関数として使えて、add(x,y)のように、名前を前に持って来ることができます。

等号の関数を作ってみる

JavaScriptの場合は、==で、値が同じかどうかを比較するので、この演算子をeq関数で包めば等号の関数が作れます。

F#の場合は、=が値が同じかどうかを比較します。かなり省略した表記なので、なれないと見づらいです。

ここまでで、add関数、eq関数を作ってみました。これらは+演算子や=演算子と同じように使えます。

K演算子を作ってみる

謎のK演算子を作ってみます。といっても、以下のようにプログラミング言語に演算子Kを追加することはできません。

ですが、add関数やeq関数と同様に、K関数を作って演算子に見立てることはできます。K演算子の中身はなんでもいいのですが、「3で割ったときのあまりが等しい」という演算子にしてみます。

JavaScriptだと以下のような感じです。

F#だと

K関数(K演算子)を作ってみました。ここで問題ですが、K関数(K演算子)は、どのような機能を持っているのでしょうか、=演算子と同じ機能を持っているのでしょうか、それとも>演算子と同じ機能でしょうか、>=と同じ機能でしょうか。

この性質チェックをするのが、数学でいう、反射律、対称律、推移律、反対称律です。何々律というのは実際にはもっとたくさんありますが、教科書では必要な部分しか説明していません。

それで、反射律、対称律、推移律の3つをパスできれば、同値関係つまり、プログラミングの==記号と同じですという事ができます。もしK関数(K演算子)が、同値関係なら、==演算子としても使えるという事になります。

また順序関係もあり、こちらは、反射律、推移律、反対称律、全順序律を満たす必要があります。もしK関数(K演算子)が、順序関係なら、大小の比較にも使えるという事になります。

書きかけのソースコード

正しくない部分があると思いますが、ひとまず雰囲気だけでも分かると思いますので、書きかけのソースコードも載せておきます。

 

 まとめ

数学の問題を解くのではなく、どうにかしてプログラミングの問題にしてしまえば続けられるのが分かってきました。

参考資料

 

F#のVisualStudio2015の開発環境を用意しよう

関数型プログラミング言語F#は、Visual Studio Community 2015をインストールして、F#のプロジェクトが作れるようにVisual F#ツールを有効化して、拡張機能のVisual F# Power Toolをインストールするだけです。

Visual F#ツールとは

Visual F#ツールはマイクロソフト公式のF#プロジェクト作成機能です。

Visual Studio Community 2015では、何も変更せずにそのままインストールをすると、C++、Python、F#などは新規プロジェクトが作れない状態になっています。そのため以下の方法で設定が可能です。

  1. インストール時にVisual F#ツールを有効化
  2. 必要になったときにVisual Studio の[新しいプロジェクト]ダイアログから有効化
  3. コントロールパネルからVisual Studio Community 2015のインストーラーを起動して、有効化

Visual Studio Community 2015インストール時にVisual F#ツールを設定

Visual Studio Community 2015をインストールと同時にVisual F#をインストールする場合は、インストール時に、カスタムを選択すると以下の表示になるので、[Visual F#]にチェックを入れるとF#の開発ツールがインストールされます。

03
Visual Studio インストール時にF#をインストールする方法

このダイアログは、[コントロール パネル\プログラム\プログラムと機能]からMicrosoft Visual Studio Community 2015 …をクリックすることで表示することができます。「プログラムと機能」ダイアログは、ソフトウェアのアンインストール時によく使いますが、大きなソフトウェアの場合設定変更にも使います。

後から、Visual F#をインストール

すでに、Visual Studio Community 2015をインストールしている場合は、[ファイル]->[新規作成]->[プロジェクト]で、[新しいプロジェクト]ダイアログを表示し、[Visual F# ツールをインストール]を選択して[OK]ボタンでインストールできます。

04
Visual Studio インストール後にF#をインストールする方法

Visual F# Power Tools のインストール

Power ToolsはF# Software Foundationが配布している拡張機能で、11万もダウンロードされているように皆が使っている便利な機能です。この拡張機能で、エディターのハイライト、インデント整形、FSLinterなどが追加されます。F#やHaskellはオブジェクト指向言語とかなり書き方が異なるので、この拡張機能で、保存時に整形するのを強く推奨します。

導入は簡単で画像のように、[ツール]->[拡張機能と更新プログラム]を選択して、ダイアログを表示して、右上の入力欄に”FSharp”など検索文字を入力して、Visual F# Power Toolsをダウンロード・インストールしてください。

05

06

よく使う機能は以下の二つです

  • Ctrl + R, Ctrl + R リネーム
  • Ctrl  + K, Ctrl + D ソースコード整形

とりあえずHelloworld

プロジェクトの新規作成

[ファイル]->[新規作成]->[プロジェクト]から、新しいプロジェクトダイアログを表示して、プロジェクトを新規作成しましょう。今回はFSharpHelloworldにしました。

001

F# Interactiveの表示

F# InteractiveはCtrl + Alt + Fキーで表示できます。メニューの[表示(V)]->[その他のウィンドウ]からも可能です。

[F# Interactive]タブをドラッグ&ドロップしてエディターの左に表示してみました。

002

基本キーを覚えましょう

以下が基本のキーです。これができるとマウスを使わずに、エディターとコンソールを移動できます。

F7キー コードに移動

Ctrl + Alt + Fキー F# Interactiveへ移動、または表示

Ctrl + Alt + Rキー F# Interactiveリセット

Alt + Enterキー カーソル行または選択範囲を、F# Interactiveで実行

Alt + wの後に2キーで、エディターとF# Interactiveの移動

 

Hello world

F# Interactiveで、printfn “hello world”;;と打ち込んでみましょう。F# Interactiveで処理を確定する場合はセミコロンふたつ;;です。これはOcamlからの名残で、OCamlユーザーも使いやすいようにこのままにしているようです。他の言語だと、エンターキーのみやセミコロンで確定するので間違えないようにしましょう。

a01

Alt+Enterキーで、エディター上のコードをF# Interactiveで実行できます。以下の例では、printfn “aaa”を書いて、カーソルを同じ行にして、Alt+Enterキーで、F# Interactiveで実行してます。

a02

ちょっと基本キーでF# Interactiveとエディターを行ったり来たりしたり、両方で実行を繰り返して、基本キーを身に着けてください。

C#やJavaはデバッガーでブレイクポイントを立てますが、F#では小さな関数を作って即試してみる事を繰り返してプログラムを大きくしていきます。このチュートリアルレベルでは、関数型の考え方を学ぶためデバッガーを使ってはいけません。

 

まとめ

今回は、開発環境を用意してHelloworldをやってみました。Visual Studioのインストールだけなので簡単だったはずです。

F#ではfold_left、fold_rightではなくList.fold、List.foldBack?

F#入門 fsharpintro.netのfoldの記事を見ると、Let.fold_leftとList.fold_rightになっていますが、マイクロソフトのAPIリファレンスを見るとList.foldとList.foldBackになっています。調べてみると機能は同じですが関数型言語によっていろいろ呼び方が違うようです。foldについては中身を実装していないので、もう一度ちゃんと勉強してみます。

手始めに、map関数などを書いてみる

OcamlとF#は、map関数などの実装方法がたくさんサンプルとしてあるので、何回も繰り返し書くことで学習できます。sum関数、map関数、reverse関数が簡単なのでまずはこれらから覚えるのがよさそうです。

https://en.wikibooks.org/wiki/F_Sharp_Programming/Lists

map関数

map関数は、List.mapがあっても気づいたときに何回も書いていたので、すぐ書けるようになりました。

リバース関数

 

fold関数、foldl

実装が難しそうと想像していたのですが、実際に書いて頭の中でステップ実行してみると全然難しくありませんでした。人が書いた記事を読むのでなく、自分で書いて、自分の頭の中でステップ実行するとよいようです。

ソースコードを書いて、上記のコメントのように書きながら1行ずつ脳内実行してみるとmap関数やreverse関数の知識で問題なく理解できます。

foldBack関数、foldr

https://en.wikibooks.org/wiki/F_Sharp_Programming/Lists を参考にして自分の分かりやすい変数名で書いてみて、コメントで書きながら脳内実行。

ひとまず、じぶんで実装して処理を追えるようになったのでいい感じです。次は使い分けを調べてみようと思います。

http://stackoverflow.com/questions/9055837/difference-between-fold-and-reduce

 

F#で末尾再帰

関数型プログラミング言語ではfor文などでループをしない代わりに、関数内で自分をさらに呼び出す再帰呼び出し(recursive call リカーシブ・コール)をします。例えば以下のように合計を求めるsum関数では、関数の中にsum (n-1)のように自分自身を呼び出します。関数を呼び出すと、戻り値で戻ってくる場所と引数を保持するためにスタックが用意されます。関数が繰り返し呼ばれるとスタックがどんどん増えていくので、数万回呼び出すとStackoverflowが発生します。

普通の再帰関数

F# Interactiveでsum関数を呼び出すと、以下のようにStackOverflow例外が発生します。これは書いたプログラムに問題があるので、例外処理(try)で補足することはできません。

これを回避するには、末尾再帰(tail call)を行います。

末尾再帰(tail call)

これをやると、アセンブラではcallではなく、jumpになるので、命令型プログラミング言語のfor文と同じで、どんどんスタックを消費するという事がなくなります。

書き方のコツは、あまり難しく考えずに、また下手に難しい問題を書こうとせずに、思い出したときにsum関数と末尾再帰版のsum関数を書いてみるとよいです。私はすぐ忘れるので、気づいたときに何回も書いていたら書けるようになりました。

 

 

 

艦隊これくしょんの艦娘をソートできるWebアプリを作ってみる

せっかくF#でWebスクレイピングをしてCSVデータを作成したので、それをSQLiteにデータ登録して、ロリポップで表示してみました。とりあえず、SQLiteなのでマルチカラムソートに対応してみようと思います。

艦隊これくしょん おてがる艦娘ソート(開発中)

001
表示できた!

 

FSharpでWebスクレイピング

wikia.comの艦これのデータを取得してみました。昨日のソースコードだとCSVに形式にできましたが、カラムのずれがありました。wikia.comのHTMLでは日本語名と英語名を分けて書かずに改行を使って書いていたり、イギリス艦はカタカナ表記がないので、泥臭く調整する必要があります。

001

 

SQLite3に取り込んでみる。

CSVファイルが正しいかどうかはデータベースで取り込んでみるのが手っ取り早いのでsqlite3にインポートしてみます。

sqlite3のコンソールを初めて使ったのですが入門情報が豊富なので問題ありませんでした。sqlite3のzipを回答したらsqlite3.exeがあるので、powershellから適当なファイル名(kancolle.db)でデータベースのコンソールに入ります。あとはデフォルトの区切り文字が(|)なので、.separator , でカンマに変更して、つくったcsvファイルを流し込みます。

002
DBBrowser for SQLiteで確認できた!

まとめ

インターネットのHTMLファイルから、データを取得してCSVファイルを作成し、データベースに格納するところまでできました。wikiなどのデータは手入力も多いため規則性がない場合は泥臭いところをしなければいけない場合も多いです。

関数型言語を道具として使う

今回は、PythonやBashで出来ることをF#でやってみました。文法を勉強しているときは全く感じなかったのですが、実際に実用的なアプリを作ってみると、C#の.NETのコードをそのままぶち込めたりして、思った以上にUnityやC#で学んだ知識をそのまま使っていけるのが分かりました。逆に.NETのAPIで、F#のインタフェースを用意していないのに驚きました。

F# Interactiveを使う開発は、Bash/Sed/Awkなどでやる泥臭いテキスト作業やコンソールでの開発と同じスタイルで、C#やJavaと同等の開発スタイルを想像していたのでこれも大きな発見でした。

次回はせっかくなので、作ったCSVまたはSqliteのデータをPHPかJavaでインターネット上に公開しようと思います。

 

FSharpでWebスクレイピング

最近、関数型プログラミング言語のF#を使っていますが、せっかくなのでWebスクレイピングをしてみました。F#Dataは、HTML CSS Selectorsも実装中なので、これが使えれば簡単にデータが取得できそうです。今回は、HTMLParserを使ってみました。

今回の目標は、艦隊コレクションのデータをテーブルとして作成して、複数のカラムでソートできるようなWebアプリを作ってみようと思います。本当はバックエンドをF#にしたいのですが、予算などの関係でPHPかJavaScriptのみです。データはひとまずkancolle.wikia.comからF#でデータを取得してみます。

とりあえずできたソースコード

Visual Studio 2015のNuGetでFSharp.Dataをインストールして、参照設定を右クリックして[Generate References for F# Interactive]をクリックすると、Scripts/load-project-debug.fsxファイルが作成され、これを#loadディレクティブでロードすれば、プロジェクトの参照設定をすべて読み込むことができます。

 

今回、コンソールでWebスクレイピングによりHTMLを取得して、CSVに加工するツールを作成してみました。実装はすこし関数型を意識するため、副作用のあるコードは MySideEffectsモジュールに詰め込むようにしました。

大半のアプリは、副作用だらけ

副作用のあるコードは MySideEffectsモジュールに詰め込むように意識して、はじめて分かったのですが、私たちが普段使ったり開発するソフトウェアは思った以上に副作用が多いです。ゲームや携帯アプリ、Webアプリなどはユーザー操作やデータ入出力が大半なので、副作用のかたまりです。

今回のプログラムを書き、F#Dataのソースコードを少しみたりしていて感じたのですが、F#は.NETのAPIがC#と同様使えるので、関数型プログラミング言語としてはHaskellなどにくらべてかなり緩いのかもしれません。プログやメディアの記事では、関数型言語といえば、参照透過性!副作用!モナド!とよく言われますが、.NETAPIとパイプライン演算子使いやすいし、F# InteractiveにAlt+Enterで流し込める手軽さがあるので、もう少し気楽に関数型言語を使ってもいいのかもしれません。