きくらげ観察日記

好きなことを、適当に。

ブログをGithub Pagesに移転しました

タイトルの通り。

genkami.github.io

人生で4回目のブログ移転です。

ローカルで記事を編集できる + Disqus使えばコメント欄もつけることができる + ブログじゃないので全く関係ないページも作れるというのに惹かれて移転してしまいました。
このブログの記事も少しずつ向こうに移行していく予定です。

Gaucheでセッターを定義する

Gaucheではデータ構造の特定の値を変更するのに、

(set! (~ vector i) 10)

とか

(set! (cdr pair) ())

とかできてしまうのが不思議だったので、方法を調べてみました。

まずは例として、以下のようなクラスを作ってみます。

(define-class <temperature> ()
  ([celsius :init-keyword :celsius]))

(define (celsius->temperature c)
  (make <temperature> :celsius c))

(define (fahrenheit->temperature k)
  (make <temperature> :celsius (k->c k)))

(define (celsius temp)
  (~ temp 'celsius))

(define (fahrenheit temp)
  (c->k (~ temp 'celsius)))



;; helper functions
(define (k->c k)
  (* 5/9 (- k 32)))

(define (c->k c)
  (+ 32 (* 9/5 c)))

これは単位に関係なく温度を扱うことのできるクラスです。

(define t (celsius->temperature 32))
(fahrenheit t) ; => 448/5

(define t1 (fahrenheit->temperature 50))
(celsius t1) ; => 10

このクラスにセッターを定義してみましょう。まずは原型から。

(define (set-celsius! temp c)
  (set! (~ temp 'celsius) c))
(define (set-fahrenheit! temp k)
  (set! (~ temp 'celsius) (k->c k)))

これでも充分ですが、どうせなら組み込み型と同じように

(set! (celsius temp) 10)

のようにできたらかっこいいですよね。

これを行うためのメソッドがsetterです。

https://practical-scheme.net/gauche/man/gauche-refj/Dai-Ru-.html

リファレンスだと少々わかりにくいような気がするのですが、setterメソッドを定義してやればset!等で使えるようになるようです。

(define-method (setter celsius) ((t <temperature>) c)
  (set-celsius! t c))
(define-method (setter fahrenheit) ((t <temperature>) k)
  (set-fahrenheit! t k))

(set! (celsius t) 10)
(fahrenheit t) ; => 50
(set! (fahrenheit t) 32)
(celsius t) ; => 0

ちなみに、

(define-method (setter celsius) (...) ...)

は特にsetter用の特殊構文などではなく、一般に

(define ((f x) y z ...) ...)

のような書き方は

(define (f x) (lambda (y z ...) ...))

シンタックスシュガーとなっています。

また、総称関数refとそのsetterを定義すると、万能アクセサ~を使った

(set! (~ hoge x) y)

というような記法が使えるようになります。

楽天で買い物した時に出るメルマガ購読のチェックボックスを自動で外す

嫌がらせとしか思えない

// ==UserScript==
// @name        fuckin rakuten checkbox
// @namespace   cloudear8
// @description uncheck them all
// @include     https://basket.step.rakuten.co.jp/*
// @version     1
// @grant       none
// ==/UserScript==

var inputs = document.getElementsByTagName("input");

for (var i = 0; i < inputs.length; i++) {
  if (inputs[i].attributes["type"].value == "checkbox") {
    inputs[i].checked = false;
  }
}

Greasemonkey用です。

楽天は3ヶ月に1回コンタクトを買うのにしか使っていませんが、勝手にメルマガ購読させようとしてくるだけで一気に使う気が失せてきます。

PFDSを読む: Binomial Heap

Binomial Heapとは、Binomial Treeというデータ構造を使って作られるヒープです。

ここで、Binomial Treeとは、以下のようなデータ構造です。

  • rankが0であるBinomial Treeは、ただ1つのノードからなるシングルトン
  • r > 0 について、rankがrであるBinomial Treeはr個の子を持ち、それらのrankはそれぞれ0, 1, ..., r - 1

この時、rankがrのBinomial Treeは、ちょうど2^r個の子を持つことになります。

証明:
rankがrのBinomial Treeの要素数a_rとすると、
a_0 = 1
a_r = 1 + \Sigma_{k = 0}^{r - 1}a_k
したがって、
a_{r+1} - a_r = (1 + \Sigma_{k = 0}^{r}a_k) - (1 + \Sigma_{k = 0}^{r - 1}a_k)
= a_r
\therefore a_{r+1} = 2a_r
よって、a_{r} = 2^{r}a_0 = 2^r

この性質は、実際にツリーを見てみるとわかりやすいと思います。

f:id:cloudear8:20170507113403p:plain

Binomial Heapは、同じrankを持たないBinomial Treeのリストとして定義されます。rank rのBinomial Treeの要素数2^r個ですから、二進数と同じ原理で、任意個の要素を持つBinomial Heapを作ることができます。
実際、nを2進数で表した時に\Sigma_{k=0}^{m}d_k2^k (d_k \in \{0, 1\})と表せた場合、d_k = 1となるようなkをrankに持つBinomial Treeがそれぞれ1つずつあれば、それらのツリーの要素数の合計はnに等しくなるはずです。

ちなみに、Binomial Heapの操作自体も二進数のアナロジーのようになっています。

また、この時Binomial Heapが持つBinomial Treeの個数はlog_2(n + 1)個程度となります。

さらに、Binomimal Heapは、リスト内の各Binomial Treeについて、一般的なヒープが持つ性質、すなわち、その根の部分がツリーの中での最小値であるという制約も持ちます。
この制約によって、最小値の検索はヒープの各要素の根を見るだけで済むようになるので、O(logn)の計算量で済むことになります。


それでは、Binomial Heapを実装していきましょう。
最初に完成形のコードを載せておいて、後から個別に解説していきます。

module type ORDERED =
  sig
    type t

    val eq : t -> t -> bool
    val lt : t -> t -> bool
    val leq : t -> t -> bool
  end

module type HEAP =
  sig
    type t
    type elt

    val empty : unit -> t
    val is_empty : t -> bool

    val insert : elt -> t -> t
    val merge : t -> t -> t

    val find_min : t -> elt (* raises Empty if heap is empty *)
    val delete_min : t -> t (* raises Empty if heap is empty *)
  end

module BinomialHeap (Elt : ORDERED) : HEAP with type elt = Elt.t =
  struct
    type elt = Elt.t
    type tree = Node of int * elt * tree list
    type t = tree list

    let link (Node (r, x1, c1) as t1) (Node (_, x2, c2) as t2) =
      if Elt.leq x1 x2 then Node (r + 1, x1, t2 :: c1)
      else Node (r + 1, x2, t1 :: c2)

    let rank (Node (r, _, _)) = r

    let root (Node (_, x, _)) = x

    let empty () = []

    let is_empty = function
      | [] -> true
      | _ -> false

    let rec insert_tree t heap = match heap with
      | [] -> [t]
      | t' :: ts' ->
         if rank t < rank t' then t :: heap
         else insert_tree (link t t') ts'

    let insert x h = insert_tree (Node (0, x, [])) h

    let rec merge ts1 ts2 = match ts1, ts2 with
      | _, [] -> ts1
      | [], _ -> ts2
      | t1 :: ts1', t2 :: ts2' ->
         if rank t1 < rank t2 then t1 :: merge ts1' ts2
         else if rank t2 < rank t1 then t2 :: merge ts1 ts2'
         else insert_tree (link t1 t2) (merge ts1' ts2')

    let rec remove_min_tree : t -> tree * t = function
      | [] -> raise (Failure "remove_min_trees")
      | t :: [] -> (t, [])
      | t :: ts ->
         let (t', ts') = remove_min_tree ts
         in if Elt.leq (root t) (root t') then (t, ts)
            else (t', t :: ts')

    let find_min ts =
      let (t, _) = remove_min_tree ts
      in root t

    let delete_min ts =
      let (Node (_, _, ts1), ts2) = remove_min_tree ts
      in merge (List.rev ts1) ts2
  end

まずはBinomialHeap.tree型です。

    type tree = Node of int * elt * tree list

例によってrankをメモしてあります。
これを利用してヒープ本体であるBinomialTree.t型を定義します。

    type t = tree list

注意しなければならないのは、Binomial Heapは要素のツリーのrankが昇順になっているのに対して、Binomial Treeの子のrankは降順になっているということです。
これは両者の操作方法がそれぞれ違うためです。
Binomial Heapは2進数のアナロジーのような操作を行うため、rankが昇順に、Binomial Treeは子の左端に自分と同じrankのものをくっつけるという動作が頻発するため、降順になっています。

次はこれらに対する操作を定義していきます。まずはlink関数。

    let link (Node (r, x1, c1) as t1) (Node (_, x2, c2) as t2) =
      if Elt.leq x1 x2 then Node (r + 1, x1, t2 :: c1)
      else Node (r + 1, x2, t1 :: c2)

これは2進数でいう半加算器のようなものです。rank rのBinomial Treeを2個合成し、rank (r + 1)のBinomial Treeを生成します。

次にinsert_treeを見てみましょう。

    let rec insert_tree t heap = match heap with
      | [] -> [t]
      | t' :: ts' ->
         if rank t < rank t' then t :: heap
         else insert_tree (link t t') ts'

これは2進のインクリメンタのようなものです。heapの"最下位ビット"にツリーを1つ加え、"繰り上がり"が生じれば"上の桁"にも同じ処理をしていきます。

これを各ビットに適用させることによって、2つのヒープをマージすることができます。

    let rec merge ts1 ts2 = match ts1, ts2 with
      | _, [] -> ts1
      | [], _ -> ts2
      | t1 :: ts1', t2 :: ts2' ->
         if rank t1 < rank t2 then t1 :: merge ts1' ts2
         else if rank t2 < rank t1 then t2 :: merge ts1 ts2'
         else insert_tree (link t1 t2) (merge ts1' ts2')

次にfind_min, delete_minですが、これらを実装するために補助関数delete_min_treeを定義します。

    let rec remove_min_tree : t -> tree * t = function
      | [] -> raise (Failure "remove_min_trees")
      | t :: [] -> (t, [])
      | t :: ts ->
         let (t', ts') = remove_min_tree ts
         in if Elt.leq (root t) (root t') then (t, ts)
            else (t', t :: ts')

各Binomial Treeは根が最小値になっているので、remove_min_treeの返り値の左の値の根が最小値となります。
これを利用してfind_min, delete_minを定義します。

    let find_min ts =
      let (t, _) = remove_min_tree ts
      in root t

    let delete_min ts =
      let (Node (_, _, ts1), ts2) = remove_min_tree ts
      in merge (List.rev ts1) ts2

delete_minの中でts1をrevしているのは、Binomial Treeの子のrankの並びとBinomial Heapの要素のrankの並びが逆順になっているためです。

【重要】MacBookを手に入れたら真っ先にインストールするべき最強アプリn選

いい加減研究室で貰ったMacBookの環境設定をしたくなってきたので、とりあえず必要と思われるものとその入手先をメモっておきます。
完全に自分用メモ。

日本語入力しようとしたら勝手に変換される謎機能

邪魔なので消します。
f:id:cloudear8:20170508130909p:plain
ここのライブ変換のチェックをはずせばOK

スペルチェック無効化

環境設定→キーボード→ユーザー辞書にあるいらなそうなチェックを消す

Dvorak, SKK

最近使わなくなったので省略。

git

たしか最初から入ってた……はず。
homebrewに入ってるやつを入れるとbash-completionが増えます。

Homebrew

これがないと始まりません。
brew.sh
ここに書いてある通りにインストールします。

$ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

Emacs

github.com
日本語環境だとこのEmacsが一番いいらしいです。面倒なので思考停止してインストールしました。

$ brew tap railwaycat/emacsmacport
$ brew install emacs-mac

最後に

$ brew linkapps

とかいうコマンドが必要。よく知らんけどたぶん.appをApplications以下にリンク貼ってよしなにしてくれるやつだと思う。

さらに、デフォルトで入っている古いEmacsを間違えて起動しないように、PATHの通っている適当なところに以下のスクリプトemacsという名前で置いておく。

#!/bin/sh

/usr/local/opt/emacs-mac/Emacs.app/Contents/MacOS/Emacs "$@"

Haskell関連

stackはbrewにあります。

$ brew install haskell-stack

ghc-modとかはそもそも使ってないので略。あとで検討するかも。

OCaml関連

homebrewから入ります。utopも忘れずに。

$ brew install ocaml opam
$ opam init
$ spam install utop

Python関連

pyenv入れたらとりあえず勝ち。
デフォルトで入ってるやつは2.7とかいうゴミなのでなかったことにしましょう。

$ brew install pyenv
$ pyenv install 3.x.x
$ pyenv global 3.x.x

環境変数の設定とかは割愛。

node.js関連

homebrewにある

Elm関連

npmから入れる(cabalではない)

Coq関連

homebrewにある
proofgeneralは自分でmake
proofgeneral.github.io
だいたい公式サイトの通りにすればいける。

Docker

docs.docker.com
公式でバイナリが用意されています。Linux版の時は全くお目にかかることのなかった可愛らしいクジラのアイコンがついてお得。
docker-composeとかも全部勝手に入ってくれるっぽいです。

Evernote, Slack

App Storeにある

githubにssh接続できない

githubのアカウントを作りなおしたついでにssh-keygenし直したら、何故かgithubに繋がらなくなってしまいました。

$ git push -u origin master
Warning: Permanently added the RSA host key for IP address '192.30.253.112' to the list of known hosts.
sign_and_send_pubkey: signing failed: agent refused operation
Permission denied (publickey).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

解決策

ssh-addすると治りました。

$ ssh-add

ssh-addする前にssh-add -l -E md5してみてもちゃんと鍵が登録されていたような気がするのですが、まあとりあえず動いたので保留ということで。

PFDSを読む: Weight-biased Leftist Heap

inkar-us-i.hatenablog.com

こちらの記事でLeftist Heapの紹介をしましたが、今回はその亜種であるWeight-biased Leftist Heapを紹介します。
このデータ構造はほとんどLeftist Heapと同様ですが、rankのかわりに要素数が左に偏るようになります。すなわち、

  1. 根の部分が常に最小値となる
  2. 全てのノードについて、その左側の子の要素数は、右側の子の要素数以上である

以下が実装になります。ここで、HEAP, ORDEREDは上の記事と同様のものです。

(* Weight-biased leftist heap  *)
module WBLHeap (Elt : ORDERED)
       : HEAP with type elt = Elt.t =
  struct
    type elt = Elt.t
    type t =
      | E
      | T of int * elt * t * t

    let size = function
      | E -> 0
      | T (s, _, _, _) -> s

    let make_t x a b =
      if size a >= size b then T (1 + size a + size b, x, a, b)
      else T (1 + size a + size b, x, b, a)

    let empty () = E

    let is_empty = function
      | E -> true
      | _ -> false

    let rec merge h1 h2 = match h1, h2 with
      | _, E -> h1
      | E, _ -> h2
      | T (_, x1, a1, b1), T (_, x2, a2, b2) ->
         if Elt.lt x1 x2
         then make_t x1 a1 (merge b1 h2)
         else make_t x2 a2 (merge h1 b2)

    let insert x h = merge (T (1, x, E, E)) h

    let find_min = function
      | T (_, x, _, _) -> x
      | E -> raise Empty

    let delete_min = function
      | T (_, _, a, b) -> merge a b
      | E -> raise Empty

    let rec from_list xs =
      let rec iter res xs = match xs with
        | a :: b :: xs -> iter (merge a b :: res) xs
        | a :: [] -> a :: res
        | [] -> res in
      let rec from_list' xs = match iter [] xs with
        | [] -> raise Empty
        | h :: [] -> h
        | xs' -> from_list' xs'
      in from_list' (List.rev_map (fun x -> T (1, x, E, E)) xs)
  end

Purely Functional Data Structures

Purely Functional Data Structures

純粋関数型データ構造

純粋関数型データ構造