【blog.hellorusk.net に移行しました】

旧・技術メモ(blog.hellorusk.net に移行しました)

Fast inverse square root

高速に  \dfrac{1}{\sqrt{x}} の近似値を計算するアルゴリズム。 Quake III Arena というビデオゲームのCGプログラムがきっかけで誕生したらしい。
めっちゃ単純で、与えられた x(32bit浮動小数点とする)に対して

  1. 浮動小数点 x を対応する 32bit のビット列 i にする。
  2. i = 0x5f3759df - ( i >> 1 );
  3. i を浮動小数点に戻す。

たったこれだけで、  \dfrac{1}{\sqrt{x}} の良い近似が得られる。

ビデオゲームにあった元のソースコードは以下のような感じらしい1

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
// y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

// 1st iteration の部分はニュートン法で精度を上げている部分なので、実質的にはその上の3行が本体ということになる。what the fuck?


仕組み

英語版 Wikipedia にちゃんと書いてあるけれど、日本語で分かりやすいものがなかったので、自分で書く。


32bit 浮動小数は、1bitの符号部 s , 8bitの指数部 e , 23bitの仮数部 m に対して、

x = (-1)s * 2e - 127 * 1.m

という形をしている。
例えば、x = 5 のとき、s = 0, e = 10000001 (=129), m = 01000000000000000000000 。
例外は、+0, -0, +INF, -INF, NaN, 非正規化数で、今は考えないことにする。また、平方根なのだから x > 0 で考える。


いま、

 x = 2^{e_x} (1 + m_x)

という数を 32bit のビット列に直すことを考える。ただし、 m_x 0 \leq m_x \lt 1 を満たし、かつ2進数表現。 例えば、 x=5 のとき  e_x = 2, m_x = 0.01
ここで、両辺2が底の対数を取ってみると、

 \log_2 {x} = e_x + \log_2 {(1 + m_x)}

さらに、 \log_2 {(1 + m_x)} m_x の線形に近似することを考える( m_x は 0から1 の範囲で小さいので)。

 \log_2 {(1 + m_x)} \approx m_x + \sigma

 \sigma は 0.0430357 がもっともあてはまりがいいらしい。これを使えば、

 \log_2 {x} \approx e_x + m_x + \sigma

となる。さて、元の  x に戻ると、 x の 32bit ビット列  I_x の指す値は

 I_x = L(e_x + B + m_x) = L(e_x + m_x + \sigma + B - \sigma) \approx L \log_2 {x} + L (B - \sigma)

と書ける。ただし、  L=2^{23}, B=127 とおいた。

同値変形して、

 \log_2 x \approx \dfrac{I_x}{L} - (B - \sigma)

となる。

求める  \dfrac{1}{\sqrt{x}} (=y) について、やはり log を考えると、

 \log_2 y = - \dfrac{1}{2} \log_2 x = - \dfrac{1}{2} \left(\dfrac{I_x}{L} - (B - \sigma)\right)

一方、 \dfrac{1}{\sqrt{x}} の 32bit ビット列を  I_y とすれば、  \log_2 y \approx \dfrac{I_y}{L} - (B - \sigma) なので、

 - \dfrac{1}{2} \left(\dfrac{I_x}{L} - (B - \sigma)\right) = \dfrac{I_y}{L} - (B - \sigma)

という関係式があることがわかった。これを同値変形して、

 I_y = \dfrac{3}{2} L(B - \sigma) - \dfrac{1}{2} I_x

マジックナンバー 0x5f3759df の正体は  \dfrac{3}{2} L(B - \sigma) のbit列(の16進数表現)2 だった。



アカデミアではない世界からこういう画期的なアルゴリズムが生まれるのは面白い。マジックナンバーというのもなんか神秘的だし。

FPUで平方根を実装したものの、よい初期値が与えられないためニュートン法を3回も繰り返すことになっており、時間がかかっていたが、これを使うと回数を減らせるかなあと期待している。

Cには参照渡しがない

booth.pm

プログラミング言語神経衰弱、というものをバイト先の先輩の家でやる機会があり、とても盛り上がった。言語は16種類くらいあって、一目で分かるもの(BrainfxxkやWhiteSpaceなど)もあれば、なかなか区別しづらいものもあった。その中で、

int add(int a, int& b) {
  return a + b; 
}

これが C ではなく C++ だよね、というのが一目では分からなかった。C には「ポインタ渡し」はあるが、「参照渡し」はない。初歩的な内容なのかもしれないけれど、私はいまいち分かっていなかったので、ちょっとまとめる。


まず、Cについて。ある型 T に対して常に型 T* を作ることができる。Cはきちんとした型推論はないはずなので、この型はただ単に何bitかをひとつの単位として仕切りを作っているという以上の情報はないけれども、とにかく、この型 T*T のアドレスが入る。これがポインタと呼ばれるものだ。

int x = 10;
int* p = &x;
*p = 42;

このように使う。& を変数の前に付けることで、その変数のアドレスを取ることができる。だから p にはアドレスが格納されている。逆に、そのアドレスに格納されている変数を * を付けて取り出すことができる。*p = 42; と書けば、格納されている x42 に書き換わる。
ふつうの高級言語はポインタが隠蔽されているので、例を挙げるのが難しいが、OCaml の参照はこれに非常に似ている。OCaml は基本的には変数がimmutableなのだけれども、その例外として参照がある。

# let x = ref 5;;
val x : int ref = {contents = 5}
# !x;;
- : int = 5
# x := 10;;
- : unit = ()
# !x;;
- : int = 10

ref は変数を格納しているアドレスを取るので C の & と対応しているし、dereference の !x*x と対応している。

さて、ポインタ渡しの話に進む。ポインタ渡しは、名前渡しとは異なり、関数を呼び出した側の変数も書き換わるので、それが用途に適っている場合はポインタ渡しを使う。そもそも文字列 char* のように実態がポインタのものは当然ポインタ渡しをしなければならない。
最近、大学の某実験でアセンブラを書く必要に迫られたが、以下のような int reg(char* reg) というポインタ渡しの関数を書いたりしていた。これは x29 のようにアセンブラに書かれているレジスタを5bitのバイナリの10進数表記 11101 にしたいのでこのようなものを書いている。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int reg(char* reg) {
  int n = atoi(++reg);
  int binary = 0;
  int base = 1;
  
  while (n > 0) {
    binary += (n % 2) * base;
    n /= 2;
    base *= 10;
  }

  return binary;
}

int main() {
  printf("%d\n", reg("x29")); // 11101 

  return 0;
}

なぜこれで上手くいくかというと、char* reg にはx29の先頭文字 x のアドレスが格納されていて、これをchar型においてインクリメントすると一個先の 2 が格納されているアドレスに増えるので ++reg29 を意味するようになり、atoi で文字列を数値に変えるので後はお察しの通りである。


次に、C++の参照渡しの話をする。まず、参照型 T& の話をしなければならない。参照型は、先ほどの変数のアドレスを取り出す演算子 & とは全く別物であることに留意する必要がある。

int n = 2;
int& v = n;

この v が参照である。ポインタと似ているようだが、

  • 初期化時にどの変数を指しているかを決める必要がある
  • 別のアドレスを後から指すことはできない

という部分が決定的に異なる。ポインタと比べて指し示す先がガチガチに固まっているので、nv という別名を付けていると考えたほうが良さそうだ。

参照においては、ポインタにおける &* のような記号を使わなくてもいいというメリットがある。つまり、Cでは

void hoge(int* a) { // ポインタ渡し
  *a = 2; // アドレスに格納されている中身を変える
}

int main() {
  int n;
  hoge(&n); // アドレスを引数とする
}

みたいだったのが、C++では

void hoge(int& a) { // 参照渡し
  a = 2;
}

int main() {
  int n;
  hoge(n);
}

というようにすっきり書ける。

また、この参照型を引数として渡す参照渡しは、ポインタ渡しと比べて、NULLポインタを入れられてしまう危険が無いというメリットがある。確かに、上で書いたレジスタを機械語に変換する関数も、本当はNULLチェックを行わねばならない。そういえばCで二分探索木を書いたときNULLチェックが大変だった記憶がある。

なお、上で書いたレジスタを機械語に変換するプログラムは C++ でも実行できるが、当然、充実した C++ の std::string を使うべきだろう。

qiita.com

Last.fm で不要なアルバムの scrobble を削除する方法

Last.fm では scrobble (楽曲を聴いた記録一つひとつの単位) を操作するための API が公開されておらず、もし登録してほしくない履歴が誤って登録されても、クライアントサイドで削除ボタンをポチポチ押すしか方法がない。
ただ、それでも一応ある程度自動化できるので、それを説明する。

例として、誤って TOEIC の問題集のCDを登録してしまい、これを削除したいものとする。

f:id:HelloRusk:20190905132227p:plain

赤で囲った部分のように、アーティスト名が "Educational Testing Service" となっているものが TOEIC のCDである。
この画面にログイン済みの状態でいるなら、以下のスクリプトデベロッパーツールに打ち込めばよい。

var nodeList = document.querySelectorAll('.chartlist-artist > a')
nodeList.forEach((n, i) => {
    if (n.innerText === "Educational Testing Service") {
        var button = document.querySelectorAll('[data-ajax-form-sets-state="deleted"]')[i]
        if (button) { 
            button.click()
            location.reload()
        }
    }
});

Last.fm の UI はちょくちょく変わるので、将来的には使えないかもしれないことに注意。

さらに、毎回ログインしてこの画面に移動するのも実際面倒なので、puppeteer を使って全てを自動化する。

const puppeteer = require('puppeteer');

(async () => {
  const userId = "XXXXXXX" // ユーザー名
  const password = "YYYYYYYYYY" // パスワード

  const browser = await puppeteer.launch();
  const page = await browser.newPage();
  await page.goto('https://secure.last.fm/ja/login');

  await page.type('input[name="username"]', userId);
  await page.type('input[name="password"]', password);
  await page.click('button[name="submit"]');

  await page.goto(`https://www.last.fm/ja/user/${userId}`);

  await page.evaluate(() => {
    const nodeList = document.querySelectorAll('.chartlist-artist > a')
    nodeList.forEach((n, i) => {
      if (n.innerText === "Educational Testing Service") {
        const button = document.querySelectorAll('[data-ajax-form-sets-state="deleted"]')[i]
        if (button) {
          button.click()
          location.reload()
        }
      }
    });
  });

  await browser.close();
})();

これを実行すればよい。
puppeteer の API にある jquery 風なセレクタの書き方で書いても良いけど、デベロッパーツールに打ち込む内容が既知なら、全て evaluate の中に書いてしまったほうが早いように見える。puppeteer、一年前くらいに比べて随分日本語の記事が増えましたね。

Go で Web サイト監視ツールを作るときのメモ

最近 Web サイトのコンテンツ更新を自動で検知したいという欲が発生したので、監視ツールを作成しました。
そこで初めて Go を使ったのですが、ライブラリが充実しており、並行処理が書きやすく、使いやすかったです。今後また Go で何か作りたい時のためにメモ書きを残しておきます。

作ったもの

github.com

含まれる要素としては、

  • PostgreSQL で既に検知しているコンテンツの情報を保存
  • goquery で t7s.jp の色々なページをスクレイピング、新しいコンテンツが含まれていないかチェック
  • go-githubGitHub API を操作し、新しいコンテンツがあったらその名前で Issue を立てる
  • Heroku で定期実行

PostgreSQL

Heroku のアドオンとして入れます。

$ heroku addons:create heroku-postgresql:hobby-dev

そうしたら

$ heroku config
DATABASE_URL: ZZZZZZZZZZZZZZZZ

というように DATABASE_URL が取れます。ローカルで試すときはこの URL を使うといいです。本番では os.Getenv("DATABASE_URL") とします。
あらかじめテーブルを作成するのはコマンドラインでできます。

$ heroku pg:psql

でデータベースに接続して SQL を打てます。これは普通に history が残っていて昔の SQL とかもさかのぼれるのは意外と便利です。
今回は CREATE TABLE issues (title TEXT); したものとします。すなわち、title という列だけを持つ issues というテーブルを作り、これにコンテンツ情報を一行ずつ入れていきます。

Go でデータベースに接続するときは

db, err := sql.Open("postgres", os.Getenv("DATABASE_URL"))
if err != nil {
    panic(err)
}
defer db.Close()

でできます。
defer は関数終了時まで実行されないという go 特有のシンタックスで、初めて defer を知ったときは何のために必要なのかよくわかりませんでしたが、今回ようやくメリットが分かりました。

db, err := sql.Open("postgres", os.Getenv("DATABASE_URL"))

// クソ長い処理

db.Close()

という状況で close を忘れそうになるのを防止できます。Pythonwith に似たものを感じますが、defer はインデントが下がらないのでさらに良いですね。

テーブルの中身を Go の配列にするのは

row, err := db.Query("SELECT title FROM issues")
if err != nil {
    panic(err)
}

var issueTitles []string
var issueTitle string
for row.Next() {
    err := row.Scan(&issueTitle)
    if err != nil {
        panic(err)
    }
    issueTitles = append(issueTitles, issueTitle)
}

こんな感じで書けます。Next() で行ごとのイテレータScan() で Go のデータに落とし込み、です。今回は ORM ライブラリを使うまでもないですが、ORM を使いたいときは別にライブラリを入れるのを検討した方が良さそうです。ライブラリの選定記事↓

qiita.com

スクレイピング

goquery でおkです。

qiita.com

GitHub API

G社が提供している go-github が網羅的です。

developer.github.com

godoc.org

とにかくこの godoc とニラメッコしていればよく、godoc を誤読しないようにしましょう(これが言いたかっただけ)。

あらかじめ GitHubaccess_token を Heroku の環境変数として登録しておきます。

heroku config:set GITHUB_TOKEN=YYYYYYYYYYYYYYYYY

まず OAuth 認証は

token := os.Getenv("GITHUB_TOKEN")
ts := oauth2.StaticTokenSource(
    &oauth2.Token{AccessToken: token},
)
tc := oauth2.NewClient(oauth2.NoContext, ts)
client := github.NewClient(tc)

でできます。Context というのがよく分かりませんが(https://blog.golang.org/context に書いてあるっぽい?)今回の用途では明らかに不要なので NoContext でよい気がします。
今回は Issue 作成の API を使いました。

opt := &github.IssueRequest{
    Title: github.String(title),
    Body:  github.String(link),
}

_, _, err := client.Issues.Create(oauth2.NoContext, "t7s-2034", "info", opt)
if err != nil {
    panic(err)
}

これで、t7s-2034 というアカウントの info というリポジトリに、title 変数の文字列をタイトル、link 変数の文字列を本体のコメントとして、 Issue を新規作成できます。

並行処理

Web ページをスクレイピングして、その情報をもとに GitHub API を操作するというのは、時間のかかる行為です。複数のページで順番にそれをやっていると大変です。なので、これを並行処理できるとうれしいです。
Go の並行処理はめちゃくちゃ学ぶことがありそうで、全然何もわかっていないですが、とりあえず今回の用途としては sync.WaitGroup を使うとよさそうでした。

qiita.com

今回は、ニュースページをスクレイピングして、新しい情報があったら Issue を立てる関数 checkNews() を用意しました。また別にCD発売ページをスクレイピングする checkCD()、他にも checkRelease()checkUnit() を作ってみました。これらを並行して走らせるのは

var wg sync.WaitGroup
wg.Add(4)
go checkNews(client, db, issueTitles, &wg)
go checkRelease(client, db, issueTitles, &wg)
go checkCD(client, db, issueTitles, &wg)
go checkUnit(client, db, issueTitles, &wg)
wg.Wait()

という感じでできます。
Node.js で近いのは Promise.all でしょうか。
これはかなりC言語とかでやるようなシステムプログラミングっぽいです。やってることは、まず wg というカウンターを用意していて、最初にカウンターに4を入れます。それぞれのスクレイピング関数の最後に wg.Done() を書いておきます。これはカウンターを1減らす関数です。あとは、wg.Wait() という、カウンターが0になるまで待つ関数を置くだけです。
なお、今回は使いませんでしたが、もし結果を checkNews(), checkRelease()... の順を保ったまま取り出したいときは Go の Channel とかを使うことになるはずです、多分。

qiita.com


初めて今回のツールを動かしたとき(すなわち、データベースに何も情報がなく、スクレイピングしたコンテンツが全て新しい情報で、その結果毎回 Issue を立てることになる)は、実行画面は、こんな感じでした。

f:id:HelloRusk:20190831022111p:plain

それぞれの関数が並行して動いた結果、Issue 作成もバラバラにできていることが分かります。

Heroku でのデプロイ

意外とよくわからなかったのがデプロイの仕方でした。npm で普通にできるようなことが、go ではできません。

qiita.com

govendor というのを使ってみましたが、本当に良いツールなのかはよくわかりません。
Go Modules というのが今後デファクト・スタンダードになっていくとすると、この辺りは変わるかもしれません。

Rust 製のシェル Nu Shell の設計理念

github.com

www.jonathanturner.org

Rust で書かれたという nushell がはてブで話題になっていたので, 自分もちょっと試していた.
実用で使うにはまだ色々難があるけど, 結構おもしろい.
これから試す人に対する注意点としては, 現状では rustc の中でも直近の nightly でしか動かない. 依存パッケージも非常に多く, 単に機能を試すだけならリリースからバイナリを落とすのが賢明である. ちなみに, rust-toolchain ファイルを置いてバージョンを固定した方がいいのでは〜という issue を立てている rust-toolchain が含まれるようになった.


さて, nushell においては Philosophy(理念) が重要視されているようで, README にも Philosophy が長々と書かれているし, philosophy.md というのをわざわざ別に置いていたりする.
確かに, 既に世の中には zsh やら fish やら xonsh やら便利なシェルがある中で, なぜわざわざ新しいシェルを作る気持ちになったのかを汲み取る上で, この「理念」とやらは重要なのかもしれない. 詳しくは各種ドキュメントで確認するべきだが, 大きく分けて2つあるように見える.

1. あらゆるデータを共通のフォーマットに落とし込み, 少ないコマンドで多様な操作を実現する

README の例にあるように, ls コマンドも ps コマンドも, 出力はテーブルになる. それだけではない. open コマンドで CSVJSON, TOML などのデータファイルを開くと, やはり自動でテーブルに直して表示してくれる.
このように出力が共通のフォーマットに落としこまれることによって, 全く同一のコマンドで操作できるようになるため, (特に初めてシェルを扱うような)ユーザーにとってコマンドの学習コストは格段に下がる.
ちなみに, この機能はWindowsPowerShell から着想を得たそうだ.

考えてみるといいだろう, ls コマンドにも ps コマンドにもそれぞれ大量にオプションがあり, その使い方を把握するためには, 頑張って man ページとニラメッコするか, ググるかしかなかったことを.
nushell が登場したことによって, lsディレクトリだけ表示するときには ls | where type == "Directory" , ps で CPU を使用しているプロセスだけ表示するときには ps | where cpu > 0 と, 同一のやり方を使えばよくなった. そして同じように CSVJSON の中身も表示できるのである.


個人的には, git log あたりも同じようにテーブル表示されたらな〜と思う.

2. スクリーンはいつも一つ 〜 shell から shells へ

作業をしていると端末(スクリーン)が1つでは足りなくなるのは日常茶飯事だろう. 私も tmux を使っている.
nushell はそのような従来の慣習に異を唱える. 端末を複数用意するのではない, 一つの端末で複数のシェルを使えるようにすべきだ, と.
plural shells の世界への移行は簡単だ. enter [path] で新しいシェルが用意される. shells でシェルの一覧を表示したり, n (next), p (previous) で前後のシェルに移動できる.


...とまあ, やや革命的(?)に書いたが, 実際には端末は複数あったほうがいいだろう, 当然...
もし一つの端末で全てを済ませるとして, nushell ユーザーは時間のかかる(端末をしばらく操作できなくなる)プロセスは毎回バックグラウンド実行させないといけないことになってしまうが, それはいいのだろうか.
ちなみに, バックグラウンド実行に対応する bash の記号 & には, nushell はまだ対応していなかった. 大学の面倒なシェル実装の課題が思い起こされる

そもそも, 複数のシェルを用意するというのは, 実態としてはどのように子プロセス生成をしているのだろうか. ゾンビプロセスを防止する仕組みとかはうまく働いているのだろうか. このあたりは有識者がより詳細な解説を日本語で書いてくれることを望みたい.

Mozilla Observatory を試した

observatory.mozilla.org

Netlify でホスティングしている自分のサイト https://hellorusk.net をよりセキュアにしてみようと考えた. もちろん, 静的サイトなのでプライバシーに関わる情報を持っているわけではないし, GitHubソースコードを上げてしまってすらいるのだけど, あくまで勉強用ということで...

f:id:HelloRusk:20190820172443p:plain:w400

初期評価は D だった.

f:id:HelloRusk:20190820172604p:plain

減点法の採点がなされている.

既にクリアしていた項目

Cross-origin Resource Sharing

Access-Control-Allow-Origin というHTTPヘッダがあり, CDN で JS/CSS を提供したり, API を提供したりする場合には付いている.

$ curl -i "https://fonts.googleapis.com/css?family=Noto+Sans+JP:300"
HTTP/2 200
content-type: text/css; charset=utf-8
access-control-allow-origin: *
(略)

逆に言えば, そのような特殊なケース以外は Cross-origin Resource Sharing(オリジン間ソース共有)をするべきではないので, Access-Control-Allow-Origin は付けないでよい.

http-strict-transport-security (HSTS), Redirection

HTTP でアクセスしても HTTPS にリダイレクトさせていること.
hellorusk.net の場合は Netlifyが自動でやってくれている.

改善した項目

X-Frame-Options

クリックジャッキングという攻撃手法がある. 普通のサイトをクリックしているつもりが, 攻撃者のサイトをクリックさせることになってしまう.

ja.wikipedia.org

これを防止するために X-Frame-Options: DENY を付ける.

X-Content-Type-Options

ブラウザによっては(特にIE), ファイルの種別を判定するために, 悪意のあるファイルであっても検査して読み込んでしまう(sniffing)ようなことがあるようで, これを防止するために(すなわち書かれている Content-Type に従ってファイルの種別を判定するために)X-Content-Type-Options: nosniff としておく.

X-XSS-Protection

XSS をブラウザが検知した時に, ブラウザにページのローディングをやめさせるような機能.
X-XSS-Protection: 1; mode=block で有効化する.
この X-XSS-Protection は, 後述する Content Security Policy がしっかり設定されていてインラインの script 等を防止できていれば, いらない機能ではあるのだが, 実際 Content Security Policy を厳密に設定するのは難しい場合もあったりするので, これを設定するのは第一段階としては有効なようだ.

改善できなかった項目

Content Security Policy

Content Security Policy は, サイトのリソースはどこから読み込まれるべきか, を指示するもの. うまく設定できればインラインの JS の読み込みを阻止できるので, XSS に対する最大級の予防策となる.
Google の記事がとても分かりやすい.

developers.google.com

説明は上に譲るとして, 私の場合はどうだったかを書いておく.
まず, 上の記事の最後にある「ユースケース 3: SSL のみ」を実践してみた.

ユースケース 3: SSL のみ
結婚指輪のディスカッション フォーラムの管理者が、すべてのリソースを安全なチャンネルからのみ読み込めるようにしたいと考えていますが、あまり多くのコードを記述したくありません。インライン スクリプトとインライン スタイルが多数使われているサードパーティ フォーラム ソフトウェアの大量のコードを書き直すことは、管理者の能力を超えています。 効果的なポリシーは次のとおりです。
Content-Security-Policy: default-src https:; script-src https: 'unsafe-inline'; style-src https: 'unsafe-inline'
default-src で https: が指定されていますが、スクリプトとスタイルのディレクティブは、その参照元を自動的に継承することはありません。 各ディレクティブは、特定のタイプのリソースでデフォルト値を完全に上書きします。

本当は unsafe-inline は付けるべきではない. Mozilla Observatory の減点対象だ. とはいえ, 私の場合, インラインのスクリプトは無いと困るのである.
実際, unsafe-inline を外して Content-Security-Policy-Report-Only を使ってみた. これはポリシーを実際に適用することなく違反を調べることができるので, ポリシーが厳しすぎることによってサイトが down してしまう危険が無く, ポリシーを試すのによい. すると,

f:id:HelloRusk:20190820181931p:plain

怒られが多数発生してしまった. hellorusk.net は Next.js という JS フレームワークで構築しているので当然ではある.

確かに, やむをえずインラインスクリプトを使う場合の方法もある.

qiita.com

一つはスクリプト自体のハッシュを生成して, それをヘッダに含めるという方法である(上の画像の a hash (...) is required. の部分だ). ただ自分の場合, JS が webpack によってめちゃくちゃ Code Splitting されてしまっていて, 数が膨大になってしまっている. 一体何個のハッシュをヘッダに含めることになるのやら. それに, 中のコードをちょっと書き直しただけでそのハッシュが全部変わってしまうのも怖い. よって却下.
もう一つは, インラインスクリプトnonce-[ハッシュ値] という属性を付けるという方法である. webpack にもそのための設定項目がある(Content Security Policies). が, ハッシュ値は予測できないものでなければならず(そうでなければ unsafe-inline を付けているのと変わらない), 静的サイトにおいてはハッシュ値を動的に変更していくことなど不可能なので, 却下.

以上より, Content Security Policy の項目をクリアすることは諦めた.

Subresource Integrity

Subresource Integrity(サブリソース完全性)は, CDN から取得したリソースが改ざんされていないかをブラウザがチェックする機能である.

developer.mozilla.org

script タグなどに integrity 属性で指定したハッシュ値を入れることでチェックできる.
これは行けそうだったのだが, 思いがけない問題に直面してしまった. 私は自分のサイトに Google Analytics を入れていて, そのために gtag.js というのを CDN から読み込ませているのだが, 配信側が CORS を https ではなく http で設定していたのである.

$ curl -i -s https://www.googletagmanager.com/gtag/js | head -n 3
HTTP/2 200
content-type: application/javascript; charset=UTF-8
access-control-allow-origin: http://www.googletagmanager.com

この通り, http である.
これはよくない. gtag.js を https のリンクで読み込ませてしまうと, この CORS のポリシーで弾かれてしまうし, かといって http で読み込ませてしまうと https の中に http が混在していることになり, 別の怒られが発生してしまう.

f:id:HelloRusk:20190820185243p:plain
Netlify での怒られ

f:id:HelloRusk:20190820185418p:plain
Mozilla での怒られ

以上より, Subresource Integrity の項目をクリアすることは諦めた.




中途半端な部分も多かったけれど, 最終的には B まで評価が上がった.

f:id:HelloRusk:20190820185541p:plain:w400

f:id:HelloRusk:20190820185654p:plain

冒頭でも述べたように, 趣味の静的サイトでこのようなことを行う意味は全く無いのだけど, 色々勉強になったのでよかった.

Scrapbox API のラッパーを書いてみた

よく使わせてもらっている Scrapbox が, 実は API を提供していることを昨日知った.

scrapbox.io

前から一度APIラッパーというものを書いてみたいなと思っていて, Mastodon とか Last.fm とかやろうとして規模の大きさに挫折していたけど, この Scrapbox API はまだ準備段階という感じなので, 書けそうだと思って書いてみた.

github.com

pypi.org

PyPI にパッケージを登録する手間が本当に大変だった. npm の手軽さに比べると本当にあり得ないくらい大変でした...
ちなみに, 作成の上では SoundCloud が公式で出している API Wrapper (https://github.com/soundcloud/soundcloud-python )を参考に書いていた. SoundCloud API Wrapper では, 認証情報などを保持し適宜リクエストを送る Client と, そのリクエストの内部実装を提供する Request, そしてリクエストの結果を適宜良い形にフォーマットする Resource と, 綺麗に役割が分担されている.
Scrapbox API はまだ GET するしかやることがないので, ここまできちんと用意しなくてもいいけれど, 将来的には書き込みAPIも用意される可能性があるから, 今の段階で構成をしっかり整えた方がよいだろう.

すごい if let たのしく使おう

最近, Rust で Cコンパイラを書き始めました.

github.com

コンパイラといっても, これはまだ四則演算と値の比較ができる程度です.
今はそんなに手をつけられなさそうですが, 夏休みになったら一気に進捗を高めたいです.

ところで, このコンパイラを書くにあたって, if let 構文というのを生まれて初めて取り入れました. これ, とても便利だと思ったので, Rust で if let がどのように使われているのかを RFC を読んだりしてちょっと調べてみました.


if let

まず, if let はどういう時に使えると嬉しいのでしょうか.
Rust ではOption型(値が無いことも含めて値として扱う型)やResult型(例外を含めた結果を扱う型, Promise に似ている)などが当たり前のように登場します. 自分で使いこなせれば便利ですし, 自分では使いたくなくても既定のメソッドの返り値の型が Option や Result になっていることが非常に頻繁にあります.
一つ例を考えてみましょう.
char 型のある文字が n 進数の数値を表している場合(すなわちn=10なら '0'から'9' のいずれかの場合), その文字を u32 型(unsigned な 32bit 整数)に変換するメソッド .to_digit(n) というものがありますが(コンパイラで文字から数値を読み取る時に便利ですね!), これは Option 型を返します. というのも, '0'から'9' のどれでもない場合, 変換すべき数が無いからです.
この .to_digit(n) を使って, 『文字を読み取って, もし数であれば加え, そうでなければ何もしない』という処理を書きたいとします. 普通にパターンマッチを使うとこんな感じです.

match c.to_digit(10) {
  Some(n) => {
    hoge += n;
  }
  None => {}
}      

ここで気をつけなければいけないのは, None => {} の部分は省略できないということです. パターンが尽くされていない場合, コンパイルエラーになってしまうからです.
一方, if let を使うと...

if let Some(n) = c.to_digit(10) {
  hoge += n;
}

これだけです. すごい!!!!!!!

  • ネストが一段浅くなって見やすい
  • None の場合の記述が不要な時, 書かなくていい

というメリットが分かるかと思います. たったこれだけ?と思うかもしれませんが, パターンマッチが二重にネストしたコードとかを試しに書いてみるとこの簡潔さがすぐに気に入るかと思います.
この if let は Swift がおそらく発祥であり, RFC にもそのような旨が書かれています.

rust-lang.github.io

書かれていることとしては,

  • パターンマッチにおける None => {}_ => {} のような, 「興味の無いパターンに対しては何もしない」という部分を, if let では省略できる
  • elseif let を繋げて, else if let とすることもできる(その場合, else の後でパターンマッチを行うのと同じ効果が得られる)
  • if let の後で else if を連ねると, else 側に対応する型のパターンマッチにおいてガードを付けるのと同じ効果が得られる
  • 全てのパターンマッチを if let で代替できるかどうかは不明


while let

さて, if let の亜種として while let が登場します. while let は, パターンマッチをループで回し, もし特定の型になった時だけ break する, みたいな処理を綺麗に書けるシンタックスで, これも Swift 発祥のようです.

rust-lang.github.io

これは自分ではまだ使ったことが無いので, 公式ドキュメントにある良い例を借ります.

// `Option<i32>`の`optional`を作成
let mut optional = Some(0);

// 変数の照合を繰り返し行う。
loop {
  match optional {
    // もし`optional`のデストラクトに成功した場合、値に応じて処理を分岐
    Some(i) => {
      if i > 9 {
        println!("Greater than 9, quit!");
        optional = None;
      } else {
        println!("`i` is `{:?}`. Try again.", i);
        optional = Some(i + 1);
      }
      // ^ 3つものインデントが必要。
    },
    // デストラクトに失敗した場合、ループを脱出
    _ => { break; }
    // どうしてこんな行を書く必要が?もっと良い方法があるはずです!
  }
}

optional という変数が Some(1), Some(2) とインクリメントされて, Some(10) になったら次は None になってループが終了するという例ですが, 確かにコメントにある通り _ => { break; } というのはなんか見てて気持ち悪いんですよね. 何かしら while の条件の部分を設定して, while で書けるようにしたい. そういうモチベーションから, while let が生み出されました.

fn main() {
  // `Option<i32>`の`optional`を作成
  let mut optional = Some(0);

  // これは次のように読める。「`let`が`optional`を`Some(i)`にデストラクトしている間は
  // ブロック内(`{}`)を評価せよ。さもなくば`break`せよ。」
  while let Some(i) = optional {
    if i > 9 {
      println!("Greater than 9, quit!");
      optional = None;
    } else {
      println!("`i` is `{:?}`. Try again.", i);
      optional = Some(i + 1);
    }
    // ^ インデントが少なく、デストラクト失敗時の処理を追加で書く必要がない。
  }
  // ^ `if let`の場合は`else`/`else if`句が一つ余分にあったが、
  // `while let`では必要が無い。
}}

if let ほど使用機会は無いかもしれませんが, こちらも書けると気持ち良さそうです.


if let や while let で複式パターンが可能になった(RFC2175)

パターンマッチの長所の一つとして

enum Foo {
  A,
  B,
  C,
  D,
}

fn bar(x: Foo) {
  match x {
    Foo::A | Foo::B => println!("AまたはB"),
    _ => {}
  }
}

この Foo::A | Foo::B のように, 複数のパターンを並べることができる点があります. 普通に if で条件節を並べるよりも簡素ですね.
このような, 複数の型を並べる記法が, if letwhile let にもサポートされるようになりました.

rust-lang.github.io

よって, 先ほどの例は

fn bar(x: Foo) {
  if let Foo::A | Foo::B = x {
    println!("AまたはB");
  }
}

このように書けます.


パターンマッチのガードとして if let が使えるようになるかもしれない(マッチガード)(RFC2294)

2019年6月時点でまだ実装されていない機能です

ガードというのは, パターンマッチの中でさらに制約を絞る時に使うもので, 例えば

match x {
  0 => println!("zero"),
  1 => println!("one"),
  n if is_prime(n) => println!("prime number {}", n),
  n => println!("composite number {}", n)
}

if is_prime(n) に当たるものがそうですが, ここに通常の if だけでなく if let も入れられるようになります.

rust-lang.github.io

この RFC の中に登場する例自体がかなり複雑で, 玄人向け機能という感じが...w
一つ紹介すると

match ui.wait_event() {
  KeyPress(mod_, key, datum) if let Some(action) = intercept(mod_, key) => act(action, datum),
  ev => accept!(ev),
}

ui.wait_event() というのが, あるイベントが発生するのを待つメソッドで, イベントが発生する前にキーの入力を検知した場合の型 KeyPress と, 予定通りのイベントの型 ev でパターンマッチが行われています. そして, KeyPress の場合, intercept(mod_, key) というメソッドで中断して, その間にもしなにか action があればそれを行うという仕組みです. つまり, ガード if let Some(action) = intercept(mod_, key) の部分は全く別のパターンマッチを表現しているという, これが「マッチガード」です.
この例のように, ユーザーインターフェース系の処理は人間がどう操作するかで色々パターンが分岐してしまうので, そういう処理を(あえて) Rust で書きたい人は, こういうシンタックスがあるとありがたそうです.


if let や while let を && で複数連鎖できるようになるかもしれない(RFC2497)

2019年6月時点でまだ実装されていない機能です

これはかなり画期的です.

rust-lang.github.io

例えば, これまで

if let A(x) = foo() {
  if let B(y) = bar() {
    computation_with(x, y)
  }
}

と書かざるを得なかったのが,

if let A(x) = foo()
  && let B(y) = bar()
{
  computation_with(x, y)
}

と書けるようになり, ネストを下げることができます.
いやいや, 従来の記法でも

if let (A(x), B(y)) = (foo(), bar()) {
  computation_with(x, y)
}

こう書けばネスト地獄にならないやん, と思われるかもしれません. でも, これは, 前の2つの例とは明らかに意味が違うのです.
前2つは, foo()A 型であるかを判定し, もしそうでなければその後の処理を打ち切ります. 一方で, 最後の例では, foo()A 型であるかと bar()B 型であるかを同時に判断します. もし foo()A 型でないにもかかわらず bar() が異様に重い処理だった場合, パフォーマンスの差は明らかですよね.


このような if let ... && ... 構文ですが, RFC の文章が非常に長くなっていることからも分かる通り, 導入にあたって議論は紛糾したようです. とりわけ, if let ... && ... を許すなら if let ... || ... はどうなのか? 他の演算子は入れられるのか? と, さらなる論点に繋がっていってしまう部分が問題として取り上げられています.
個人的には, この RFC の中においても, そもそも発祥の Swift ではif letの連鎖はどう書けるのか, というのが再び取り上げられているのが面白いな〜と思いました.



if let, while let は先進的なシンタックスであるだけに, 今後もさらなる機能拡張が起こるかもしれません. 楽しみですね.

線形計画ソルバー PuLP で強双対性・相補性の確認

線形計画問題はなんとなくエクセルとかで解くイメージがあったけれど, Python にもちゃんとライブラリがあった

github.com

ちょっと使いたくなったので触ってみます
線形計画問題において,

  •  \min c^{T} x \ \ s.t. \ \ A x = b, x \geq 0 (主問題)
  •  \max b^{T} y \ \ s.t. \ \ A^{T} y \leq c(双対問題)

のそれぞれの実行可能な最適解を x_t, y_t とすると, 強双対定理より  c^{T} x_t = b^{T} y_t が, 相補性定理より  (c - A^{T} y_t) \cdot x_t = 0 が成り立つ. これを PuLP で確認しましょう

from pulp import *

def solve_primal_problem(A, b, c, m, n):
    prob = LpProblem("primal problem", LpMinimize)

    x = []
    for i in range(n):
        x.append(LpVariable("x{}".format(i), 0))

    prob += lpDot(c, x) # objective score

    for i in range(m):
        prob += lpDot(A[i], x) == b[i]

    prob.solve()
    return [x[i].varValue for i in range(n)]

def solve_dual_problem(A_T, b, c, m, n):
    prob = LpProblem("dual problem", LpMaximize)

    y = []
    for i in range(m):
        y.append(LpVariable("y{}".format(i)))

    prob += lpDot(b, y) # objective score

    for i in range(n):
        prob += lpDot(A_T[i], y) <= c[i]

    prob.solve()
    return [y[i].varValue for i in range(m)]


# 転置行列を求めるやつ
# まあ numpy にあるメソッドを使えばいいんだけどこのためだけに numpy を import するのもあれなので
def transpose(A, m, n):
    newA = [[0 for i in range(m)] for j in range(n)]
    for i in range(n):
        for j in range(m):
            newA[i][j] = A[j][i]
    return newA

上から順に主問題の最適解を求める関数, 双対問題の最適解を求める関数で, まあコードを見れば使い方がなんとなく分かると思います

# Example

m = 2
n = 4
A = [[2, 1, -1, 0],
     [1, 3, 0, -1]]
A_T = transpose(A, m, n)
b = [3, 4]
c = [1, 2, 0, 0]

x_t = solve_primal_problem(A, b, c, m, n)
print(x_t)
y_t = solve_dual_problem(A_T, b, c, m, n)
print(y_t)

# 強双対性
print(lpDot(c, x_t))
print(lpDot(b, y_t))
# が一致するはず

# 相補性
z_t = [c[i] - lpDot(A_T[i], y_t).value() for i in range(n)]
print(lpDot(x_t, z_t))
# が0になるはず

実行すると順に

[1.0, 1.0, 0.0, 0.0]
[0.2, 0.6]
3.0
3.0
2.220446049250313e-16

で, 強双対性の方はバッチリ2つのスコアが合っていて, 相補性の方は本当はぴったり0になってほしいがまあ浮動小数点なので無理ですよね, という感じ


もう少し複雑な例でやると,

# Example2

m = 3
n = 6
A = [[4, 6, 3, 1, 0, 0],
     [2, 3, 6, 0, 1, 0],
     [3, 1, 0, 0, 0, 1]]
A_T = transpose(A, m, n)
b = [24, 24, 12]
c = [-1, -12, -10, 0, 0, 0]

x_t = solve_primal_problem(A, b, c, m, n)
print(x_t)
y_t = solve_dual_problem(A_T, b, c, m, n)
print(y_t)

# 強双対性
print(lpDot(c, x_t))
print(lpDot(b, y_t))
# が一致するはず

# 相補性
z_t = [c[i] - lpDot(A_T[i], y_t).value() for i in range(n)]
print(lpDot(x_t, z_t))
# が0になるはず

実行すると順に

[0.0, 2.6666667, 2.6666667, 0.0, 0.0, 9.3333333]
[-1.5555556, -0.88888889, 0.0]
-58.666667399999994
-58.666667759999996
1.0933333474607257e-06

OCaml で8クイーンを解く

電車の中で

7つの言語 7つの世界

7つの言語 7つの世界

を読んでいて, Prolog数独や8クイーンを解いているのを見て, そういえば8クイーンという問題があったなというのを思い出して, そういえば OCaml で書けるなというのに気づいてさっき確認した


Nクイーン問題というのは, N * N の大きさのチェス盤に N 個のクイーンを, どの2つも互いに相手を取られないような位置に置く, という問題で, 昔 id:sifi_border に教えてもらいました. N = 8 のときは解が92通りある

こういうパズルっぽい問題でブルートフォースしたいときは, リストモナドを使って非決定性計算を表現するとカッコよく求めることができます. カッコいいだけであって, アルゴリズムが優れているわけでは全然ない...


では書きます
まず縦横に同じ列に駒があったらアウトなので, (1, a), (2, b) ... (8, h) に駒がある(a, ..., h は1から8をちょうど1回ずつ使う)としてよい
この 8! 通りを全部試します

type 'a m = 'a list
let (>>=) x f = List.concat (List.map f x)
let return x = [x]
let guard b = if b then return () else []

リストモナドと guard. guard は制約を設定するために使う

let numbers = [1; 2; 3; 4; 5; 6; 7; 8]

let rec remove l n = 
  match l with
  | []           -> []
  | x :: xs      -> if x = n then xs else x :: (remove xs n)

候補の数のリストと, 候補を減らすための関数

let not_diagonal (p, q) (r, s) =
  if ((p - r) = (q - s)) || ((p - r) = (s - q)) then
    false
  else
    true

let rec not_diagonal_all l (r, s) =
  match l with
    | []             -> true
    | (p, q) :: rest ->
      if not_diagonal (p, q) (r, s) then
        not_diagonal_all rest (r,s)
      else
        false

対角線上に 2 つの駒が無い場合 true を返すような関数

let find =
  numbers  >>= (fun a ->
  let numbers2 = remove numbers a in
  numbers2 >>= (fun b ->
  (guard (not_diagonal_all [(1, a)] (2, b))) >>= (fun _ ->
  let numbers3 = remove numbers2 b in
  numbers3 >>= (fun c ->
  (guard (not_diagonal_all [(1, a); (2, b)] (3, c))) >>= (fun _ ->
  let numbers4 = remove numbers3 c in
  numbers4 >>= (fun d ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c)] (4, d))) >>= (fun _ ->
  let numbers5 = remove numbers4 d in
  numbers5 >>= (fun e ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d)] (5, e))) >>= (fun _ ->
  let numbers6 = remove numbers5 e in
  numbers6 >>= (fun f ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d); (5, e)] (6, f))) >>= (fun _ ->
  let numbers7 = remove numbers6 f in
  numbers7 >>= (fun g ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d); (5, e); (6, f)] (7, g))) >>= (fun _ ->
  let numbers8 = remove numbers7 g in
  numbers8 >>= (fun h ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d); (5, e); (6, f); (7, g)] (8, h))) >>= (fun _ ->
    return ((1, a), (2, b), (3, c), (4, d), (5, e), (6, f), (7, g), (8, h)))))))))))))))))

これで計算おしまい. このfindというのが答えが格納されたリストになっています
以上を 8queen.ml として, インタプリタを起動

# #use "8queen.ml";;
type 'a m = 'a list
val ( >>= ) : 'a list -> ('a -> 'b list) -> 'b list = <fun>
val return : 'a -> 'a list = <fun>
val guard : bool -> unit list = <fun>
val numbers : int list = [1; 2; 3; 4; 5; 6; 7; 8]
val remove : 'a list -> 'a -> 'a list = <fun>
val not_diagonal : int * int -> int * int -> bool = <fun>
val not_diagonal_all : (int * int) list -> int * int -> bool = <fun>
val find :
  ((int * int) * (int * int) * (int * int) * (int * int) * (int * int) *
   (int * int) * (int * int) * (int * int))
  list =
  [((1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4));
   ((1, 1), (2, 6), (3, 8), (4, 3), (5, 7), (6, 4), (7, 2), (8, 5));
   ((1, 1), (2, 7), (3, 4), (4, 6), (5, 8), (6, 2), (7, 5), (8, 3));
   ((1, 1), (2, 7), (3, 5), (4, 8), (5, 2), (6, 4), (7, 6), (8, 3));
   ((1, 2), (2, 4), (3, 6), (4, 8), (5, 3), (6, 1), (7, 7), (8, 5));
   ((1, 2), (2, 5), (3, 7), (4, 1), (5, 3), (6, 8), (7, 6), (8, 4));
   ((1, 2), (2, 5), (3, 7), (4, 4), (5, 1), (6, 8), (7, 6), (8, 3));
   ((1, 2), (2, 6), (3, 1), (4, 7), (5, 4), (6, 8), (7, 3), (8, 5));
   ((1, 2), (2, 6), (3, 8), (4, 3), (5, 1), (6, 4), (7, 7), (8, 5));
   ((1, 2), (2, 7), (3, 3), (4, 6), (5, 8), (6, 5), (7, 1), (8, 4));
   ((1, 2), (2, 7), (3, 5), (4, 8), (5, 1), (6, 4), (7, 6), (8, 3));
   ((1, 2), (2, 8), (3, 6), (4, 1), (5, 3), (6, 5), (7, 7), (8, ...)); ...]
# List.length find;;
- : int = 92


念のため N = 10 でチェック. Wikipedia によると 724 通りあります

10queen.ml

type 'a m = 'a list
let (>>=) x f = List.concat (List.map f x)
let return x = [x]
let guard b = if b then return () else []

let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

let rec remove l n = 
  match l with
  | []           -> []
  | x :: xs      -> if x = n then xs else x :: (remove xs n)

(* 対角線上に2駒が無いかどうかの判定 *)
let not_diagonal (p, q) (r, s) =
  if ((p - r) = (q - s)) || ((p - r) = (s - q)) then
    false
  else
    true

let rec not_diagonal_all l (r, s) =
  match l with
    | []             -> true
    | (p, q) :: rest ->
      if not_diagonal (p, q) (r, s) then
        not_diagonal_all rest (r,s)
      else
        false

let find =
  numbers  >>= (fun a ->
  let numbers2 = remove numbers a in
  numbers2 >>= (fun b ->
  (guard (not_diagonal_all [(1, a)] (2, b))) >>= (fun _ ->
  let numbers3 = remove numbers2 b in
  numbers3 >>= (fun c ->
  (guard (not_diagonal_all [(1, a); (2, b)] (3, c))) >>= (fun _ ->
  let numbers4 = remove numbers3 c in
  numbers4 >>= (fun d ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c)] (4, d))) >>= (fun _ ->
  let numbers5 = remove numbers4 d in
  numbers5 >>= (fun e ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d)] (5, e))) >>= (fun _ ->
  let numbers6 = remove numbers5 e in
  numbers6 >>= (fun f ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d); (5, e)] (6, f))) >>= (fun _ ->
  let numbers7 = remove numbers6 f in
  numbers7 >>= (fun g ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d); (5, e); (6, f)] (7, g))) >>= (fun _ ->
  let numbers8 = remove numbers7 g in
  numbers8 >>= (fun h ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d); (5, e); (6, f); (7, g)] (8, h))) >>= (fun _ ->
  let numbers9 = remove numbers8 h in
  numbers9 >>= (fun i ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d); (5, e); (6, f); (7, g); (8, h)] (9, i))) >>= (fun _ ->
  let numbers10 = remove numbers9 i in
  numbers10 >>= (fun j ->
  (guard (not_diagonal_all [(1, a); (2, b); (3, c); (4, d); (5, e); (6, f); (7, g); (8, h); (9, i)] (10, j))) >>= (fun _ ->
    return ((1, a), (2, b), (3, c), (4, d), (5, e), (6, f), (7, g), (8, h), (9, i), (10, j)))))))))))))))))))))


# #use "10queen.ml";;
type 'a m = 'a list
val ( >>= ) : 'a list -> ('a -> 'b list) -> 'b list = <fun>
val return : 'a -> 'a list = <fun>
val guard : bool -> unit list = <fun>
val numbers : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
val remove : 'a list -> 'a -> 'a list = <fun>
val not_diagonal : int * int -> int * int -> bool = <fun>
val not_diagonal_all : (int * int) list -> int * int -> bool = <fun>
val find :
  ((int * int) * (int * int) * (int * int) * (int * int) * (int * int) *
   (int * int) * (int * int) * (int * int) * (int * int) * (int * int))
  list =
  [((1, 1), (2, 3), (3, 6), (4, 8), (5, 10), (6, 5), (7, 9), (8, 2), 
    (9, 4), (10, 7));
   ((1, 1), (2, 3), (3, 6), (4, 9), (5, 7), (6, 10), (7, 4), (8, 2), 
    (9, 5), (10, 8));
   ((1, 1), (2, 3), (3, 6), (4, 9), (5, 7), (6, 10), (7, 4), (8, 2), 
    (9, 8), (10, 5));
   ((1, 1), (2, 3), (3, 9), (4, 7), (5, 10), (6, 4), (7, 2), (8, 5), 
    (9, 8), (10, 6));
   ((1, 1), (2, 4), (3, 6), (4, 9), (5, 3), (6, 10), (7, 8), (8, 2), 
    (9, 5), (10, 7));
   ((1, 1), (2, 4), (3, 7), (4, 10), (5, 2), (6, 9), (7, 5), (8, 3), 
    (9, 8), (10, 6));
   ((1, 1), (2, 4), (3, 7), (4, 10), (5, 3), (6, 9), (7, 2), (8, 5), 
    (9, 8), (10, 6));
   ((1, 1), (2, 4), (3, 7), (4, 10), (5, 6), (6, 9), (7, 2), (8, 5), 
    (9, 3), (10, 8));
   ((1, 1), (2, 4), (3, 7), (4, 10), (5, 8), (6, 2), (7, 5), (8, 3), 
    (9, 6), (10, 9));
   ((1, 1), (2, 4), (3, 7), (4, 10), (5, 8), (6, 3), (...), ...); ...]
# List.length find;;
- : int = 724