Posts

PureScriptで配列のシャッフルをしたい。型はこんな感じ。乱数は副作用を伴うため、返り値の型はEffectで包まれる。 1 shuffle :: forall a. Array a -> Effect (Array a) アルゴリズムはFisher-Yates ShuffleのModern Algorithmの項の2つ目を利用する。これをさまざまな方法で作成したところ、Functor, Applicative, Monadなどに関連する事項だったり、STモナドの使い方、FFIの使い方だったりが学べたので、備忘のために書く。 準備 適当なディレクトリでプロジェクトを作成する。今回使うパッケージをインストールする。 $ spago init $ spago install arrays $ spago install random $ spago install foldable-traversable 方法1: 素直(?)な書き方 ここでは、src/Shuffle.pursに記述する。 天下り的ではあるが、これから使う関数、型をimportしておく。 1 2 3 4 5 6 7 8 9 10 module Shuffle where import Prelude import Effect (Effect) import Data.Array (range, (!!), updateAt, length) import Data.Traversable (for) import Effect.Random (randomInt) import Data.Maybe (maybe) import Data.Foldable (foldr) まずは、「どの添字ととの添字の値を交換するか」という情報をもったデータExchangeIndexと、それを作成する関数exchangeIndiciesを作成する。 1 2 3 4 5 6 7 8 9 10 type ExchangeIndex = { i :: Int , j :: Int } exchangeIndicies :: Int -> Effect (Array ExchangeIndex) exchangeIndicies n = for (range 0 (n - 2)) \i -> do j <- randomInt i (n - 1) pure { i, j } 次に、ExchangeIndexの情報を元に配列を交換する関数exchangeを作成。配列の添字が不正だった場合(配列外参照を起こしそうなとき)は!!演算子がNothingを返すため、一連の計算はMaybeに包まれる。今回は簡単のため、交換に失敗したら元の配列をそのまま返すような実装にする。 ...

purescript-generics-repパッケージを使ってGenericなSerializer型クラスを作った。以下はそのメモ。 準備 プロジェクトを作成。 $ spago init Arrayを使うので、パッケージをインストールしてsrc/Main.pursにimport文を書き込んでいく。 本記事の本命であるgenerics-rep入れる。 $ spago install arrays $ spago install generics-rep 1 import Data.Array ((:)) REPLで色々実験するので、あらかじめ起動しておく。 $ spago repl > import Main 以降はsrc/Main.pursに色々書き足していく。REPLで:r(もしくは:reload)とコマンドを打てばモジュールが再読み込みされるので、src/Main.pursを書き換える度にこのコマンドを打つと良い。 Serializer そもそもSerializerとは何か。ここでは単に「データをビット列に変換するもの」程度の意味で捉えれば良い。 厳密にはJSONなどの階層を持つデータを，文字列などの平坦なデータに変換するという意味合いとしてシリアライズ(直列化)という言葉を使う。実際、本記事では最終的に木構造をシリアライズする。 まずビットは次のように定義する。 1 2 3 4 5 data Bit = O | I instance showBit :: Show Bit where show O = "O" show I = "I" Serializer型クラスを以下のように定義する。 1 2 class Serializer a where serialize :: a -> Array Bit 試しに適当な型をつくり、それをSerializer型クラスのインスタンスにしてみる。 1 2 3 4 5 6 data Person = Alice | Bob | Carol instance serializerUser :: Serializer Person where serialize Alice = [ I ] serialize Bob = [ O, I ] serialize Carol = [ O, O, I ] 余談。今回はデシリアライザは実装しないので、シリアライズしたデータを同じ形に戻せるかは考えない。このあたりは情報理論の授業で「一意復号化可能性」などをやった気がするけど、忘れてしまった。 REPLで実験してみる。 > serialize Alice [I] > serialize Bob [O,I] > serialize Carol [O,O,I] Tree型をSerializer型クラスのインスタンスにする(素朴な方法) 2分木のデータ構造であるTree型を作る。 ...

プログラミングの初歩で作りそうなじゃんけんゲームを作る。ただし、PureScriptで作る。 方針 Jankenというモジュールを作る グー・チョキ・パーをHandとして定義する じゃんけんの勝負の結果をJudgementとして定義する コンピュータが出す手はランダムに出したいので、ランダムな手を出す関数randomを作っておく 入力は文字列にしたいので、文字列から手に変換する関数fromStringを作っておく 入出力はMainに書く。Node.ReadLineモジュールの力で入力を受け付ける。 準備 適当なプロジェクトディレクトリを作っておいて、 $ spago init /src/Main.pursと/src/Janken.pursを作っておく。 /src/Main.pursはとりあえず以下のようにしておく。 1 2 3 4 5 6 7 8 9 10 module Main where import Prelude import Effect (Effect) import Effect.Console (log) main :: Effect Unit main = do log "Hello" 次のコマンドでHelloが出力されることを確認する。 $ spago run Jankenモジュールの定義 この節では/src/Janken.pursを編集していく。 1 2 3 module Janken where import Prelude Handの定義 じゃんけんの手を表す型Handを定義する。 1 data Hand = Rock | Scissors | Paper 余談。これは公式ではタグ付き共用体と呼ばれているもの。Haskellでは代数的データ型と呼ばれているが、正直名前はどうでもいい。データをこのように表現すれば、「データはこの値しかとりえない」という制限が得られる。制限があれば、プログラムのバグも減らせる。たとえば、「グーを0、チョキを1、パーを2」として表現すると、万が一それ以外の値が来た場合に困る。上のようなHandの定義では、「それ以外の値」が入る余地すら与えない。…この話は、Elm Guideの受け売り。 Judgementの定義 同じようにして、じゃんけんの勝敗を表す型Judgementを定義する。 1 Judgement = WinLeft | WinRight | Draw なぜWinとかLoseではないのかというと、これはjudge関数の都合である。Judgeは、2つの手を引数にとり、その勝負結果を返す。WinやLoseだと、どっちが勝ちでどっちが負けか分からない。なので、「judgeの左側の引数が勝ったらWinLeft、右側が勝ったらWinRight、引き分けならDraw」と定義している。 ...

備忘録。基本的にはMacのTerminalでやることを想定。Macをインストールしたての状態を仮定する。 homebrewを使って、TeXLiveとSkimをインストールする。latexmkの設定をした後、vimにdein.vimを入れて、それを用いてvimtexを入れるところまでやる。おまけでvimrcの他の設定や、colorschemeの設定もやる。 注意 なるべくコマンドを載せるようにするが、それを実行しても上手くいかない場合は、公式サイトなどを参照すること。この記事が古くなっていて、打つべきコマンドが変わっている可能性がある。 homebrewのインストール homebrewをインストールしておくと、いろいろなソフトがbrew (cack) install ...だけでインストールできる。便利なので入れる。 homebrewの公式サイトのインストールを参照。 念のため、Terminalを再起動しておく。 TeXLive(MacTeX)のインストール TeXLiveの説明についてはWikiを参照。TeX関連のあらゆるパッケージやソフトの詰め合わせ。そのMac版がMacTeX。 MacTeXやそのインストール方法については、Wikiを参照。homebrewをインストールしたので、次のコマンドでインストールできる。以下はmactex-no-guiとしているが、もしguiアプリも入れたい場合はmactexとする。どんなguiアプリが入るのかについてはWikiを参照。 かなり巨大なファイル群のため、インストールにかなり時間がかかった気がする。 $ brew cask install mactex-no-gui $ sudo tlmgr update --self --all $ sudo tlmgr paper a4 念のため、Terminalを再起動しておく。 Skimのインストール SkimとはPDFビュワーの一種で、PDFの自動リロードを行ってくれる。こちらもhomebrewでインストールできる。 $ brew cask install Skim 起動して、環境設定を開く。「同期」タブに移動して、「ファイルの変更をチェック」と「自動的にリロードする」にチェックを入れておく。 latexmkの設定 後でインストールするVimのプラグイン(vimtex)がlatexmkを利用するので、設定しておく。 こちらのページは、latexmkについて分かりやすく説明してくれているので見ておくと良い。 ~/.latexmkrcを作成し、内容を以下のようにする。これは上の参考サイトの引用。 1 2 3 4 5 6 7 8 9 10 11 #!/usr/bin/env perl $latex = 'platex -synctex=1 -halt-on-error'; $latex_silent = 'platex -synctex=1 -halt-on-error -interaction=batchmode'; $bibtex = 'pbibtex'; $biber = 'biber --bblencoding=utf8 -u -U --output_safechars'; $dvipdf = 'dvipdfmx %O -o %D %S'; $makeindex = 'mendex %O -o %D %S'; $max_repeat = 5; $pdf_mode = 3; $pvc_view_file_via_temporary = 0; $pdf_previewer = "open -ga /Applications/Skim.app"; Vimのインストール 恐らく標準で入っていると思われる。もし入っていなかったら以下のコマンドでインストールする。 ...

備忘のために。数値解析関連の話はほとんど学んだことがないため、何か間違いがあるかも。 Eular法 以下、例に出そうとしている微分方程式が運動方程式なので、文字の使い方を力学っぽくしている(位置、速度、時間を $x, v, t$ みたいな気持ちで書いている)。 導出(1階) まず次の常微分方程式がある。 \[ \frac{dx}{dt} = f(t, x) \] 上の式を以下のように近似する。$h$を十分小さくすれば、微分の定義より上の式に近づく。 \[ \begin{aligned} \frac{x(t + h) - x(t)}{h} \simeq f(t, x) \\ \Rightarrow x(t + h) \simeq x(t) + f(t, x)h \end{aligned} \] これが、$x(t)$の更新式となっている。つまり、ある時刻$t_0$における値$x_0 = x(t_0)$を決めておけば、 \[ \begin{aligned} & t_k := t_{k-1} + h\\ \end{aligned} \] とおいて、 \[ \begin{aligned} & x(t_1) := x(t_0) + f(t_0, x_0)h \\ & x(t_2) := x(t_1) + f(t_1, x_1)h \\ & x(t_3) := x(t_2) + f(t_2, x_2)h \\ & … \end{aligned} \] ...

Stateモナドがわからない状態から、ギリギリ分かる状態になった。 Stateモナドを学習した流れ 結局、具体例を通して学習した。個人的には、いきなりモナドの定義から学習するよりも、たくさんの例を見たり、実際に例を作ってみたりした方が覚えられた。抽象的な概念を理解するためには具体的な概念に触れるべきだ、ということを改めて認識した。 以下は、自分が行った学習の流れ。Haskell IOモナド 超入門は学習のうえで参考になった。とくに、>>=を漏斗の形に見立てる比喩のおかげで、モナドと関数の組み合わせのイメージがクリアになった。 Maybeモナド、Listモナドの使い方を理解する。 IOモナドの使い方を理解する。 いくつかのモナドについて、do構文を>>=に書き換えてみる。 Stateモナドの使い方を理解する。 Stateモナドを自作する。 この記事ではStateモナドを自作することをテーマとしているため、ある程度Stateモナドに慣れた人でないとわかりづらいかもしれない。 Stateの定義 まずはStateを自作する。Stateは、状態 -> (計算結果,次の状態)という関数を内部に持っている。この関数のことを、この記事では「内部関数」「状態付き計算」などと表現する。 1 newtype State s a = State (s -> (a, s)) これは本来のStateの定義とは異なることに注意。本来は、StateはStateTを使って実装されている。上のように定義してしまうと、モナド変換子としての機能が利用できない。ただ、そこまで考えると面倒なので、今回はStateを単なる関数のラッパーとして定義した。 型引数の順番と内部関数が返すタプルの順番が逆なのが微妙に気持ち悪い。これはあくまで推測でしかないが、 あくまで状態付きの計算なので、重要なのは計算の結果。なので返り値は(a, s)と計算結果を先に書いている。 型引数の順番がs aなのは、Monadにするときに不都合を生じないため。 なのだと思う。 余談 Stateモナドがよくわかっていない時は、Stateのことを「状態を持つ型」と勘違いしていた。正しくは、「状態付き計算を持つ型」。Stateは状態を持っているわけでなく、あくまで、「状態を引数にとり、計算結果と次の状態を返す関数」を持っている。なので、初期状態は内部関数の引数として、自分で投入する。 runStateの定義 レコード構文を使って、runStateを定義する。runStateは、Stateから中身の関数を取り出す関数。 1 newtype State s a = State { runState :: s -> (a, s) } 試す 上の定義を踏まえて、次のようにプログラムを書いてみる。以下は、状態を[Int]とする状態付き計算。 addX doubleAll sumUpはそれぞれ、単純な内部関数を持つStateである。一方で、calc0はこれらの関数を組み合わせた、新たなStateであることに注目。一連の状態付き計算を一つにまとめて、新たな状態付き計算を作っている。 calc0において、初期状態をs、次の状態をs0、その次の状態をs1、…と置いている。計算結果を返すのはsumUpだけで、他の関数は単に状態を変更するだけ。なので計算結果は()となっている。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 addX :: Int -> State [Int] () addX x = State $ \s -> ((), x:s) doubleAll :: State [Int] () doubleAll = State $ \s -> ((), map (* 2) s) sumUp :: State [Int] Int sumUp = State $ \s -> (sum s, s) calc0 :: State [Int] Int calc0 = State $ \s -> let (_, s0) = runState (addX 1) s (_, s1) = runState (addX 2) s0 (a2, s2) = runState sumUp s1 (_, s3) = runState (addX a2) s2 (_, s4) = runState doubleAll s3 in runState sumUp s4 main = do print $ runState calc0 [] 実行結果は以下のようになる。 ...

webpackを利用してp5.jsの開発環境を作り、ボールが弾むプログラムを作成する。 使用するパッケージのバージョン 1 2 3 4 webpack@5.15.0 webpack-cli@4.3.1 webpack-dev-server@3.11.2 p5@1.2.0 動機 ふとしたきっかけで久々にp5.jsを触りたくなった。 昔使っていたときは、p5.jsのファイルをダウンロードしてscriptタグに直接指定することで書いていた。しかし最近、Vue.jsのガイドを読んでいてwebpackの存在を知った。名前は知っていたのだが、具体的に何をするためのものなのかはよく分かっていなかったので調べた。 webpackとは 以下、個人的に調べた限りの理解を書く。 Conceptによれば、webpackとは"module bundler"の一種。bundleという意味から、「複数のモジュールを一つに束ねるツール」だと予想できる。JSのプログラムを、モジュールとして複数の単位に分割して開発する。それを一つのファイルにまとめ上げてくれるのがwebpack。 例えばp5.jsで、ボールが弾むだけのプログラムを書こう、と思った場合、 ボールを管理するモジュールをBall.jsに書く スケッチを管理するモジュールをsketch.jsに書く メインの処理をindex.jsに書く みたいにモジュールを分けられる。 ただし、モジュールを扱うための機能であるimport/export文はES2015の仕様で標準採用され、多くのブラウザで実装されている。じゃあwebpackの他の強みは何かというと、おそらく「JS以外のファイルもまとめてくれる点」だと思う。例えばcssやsassのファイルもJSに埋め込むことができる。TypeScriptやJSXのファイルもwebpackでまとめられる。ただしwebpackの核の機能はあくまでJSのモジュールをまとめることなので、JS以外のファイルはloaderと呼ばれる変換器を通しておく必要がある。とはいえ、「このファイルはこのloaderに通してね」というのをあらかじめ設定ファイルに書いておけば、少ないコマンドで変換からbundleまでやってくれるので、便利である。 今回はp5.jsの開発環境づくりのためにwebpackを用意するのだが、JSのモジュールしか扱うつもりはない。なのでwebpackの恩恵は少ないかもしれない。しかし練習として使ってみる。 webpackの導入と動作確認 まず適当にプロジェクト用のディレクトリを作る。npmでプロジェクトを初期化する。 $ mkdir p5-sandbox $ cd p5-sandbox $ npm init -y 以下、このプロジェクトのルートディレクトリを/で表す。 webpack本体を入れる。webpackをコマンドラインから実行するためにはwebpack-cliが必要なので、それも入れる。個人で使う分にはどうでもよいと思うが、これらは開発のみに利用されるパッケージなので、--save-devをつけておく。 $ npm install webpack webpack-cli --save-dev ディレクトリの作成 今回は次のようにする。 ソースコードは/src/index.jsに書く。 bundle後のファイルは/public/js/bundle.jsとして出力されるようにする。 あらかじめディレクトリを作成しておく。 $ mkdir src $ mkdir -p public/js index.jsの作成 /src/index.jsを作成。動作確認のため適当に書く。 1 console.log("Hello, World"); webpackの設定 /webpack.config.jsを作成する。 1 2 3 4 5 6 7 8 9 10 const path = require('path'); module.exports = { mode: 'development', entry: './src/index.js', output: { filename: 'bundle.js', path: path.resolve(__dirname, 'public/js') } } 説明 module.exportsの中に色々設定項目を書いていく。基本的なことはConfigurationに載っている。 ...

Unix系のコマンド(od、grep)だけを使って、zipファイルの中身をのぞく。 zip形式の参考サイト zipの仕様書はZIP File Format Specificationで確認できる。ページ内検索をかけながら必要なところをつまんでいく、という読み方が良さそう。 日本語ならWikipediaがある。こちらは図が書かれているし日本語なので分かりやすい。 zipファイルの用意 まずはzipファイルを用意する。 foo.txtとbar.txtを用意する。 $ echo "Hello, World." > foo.txt $ echo "Good Bye." > bar.txt これらをzipコマンドでまとめる。 $ zip tmp.zip foo.txt bar.txt バイナリ形式で出力 zipファイルはテキストとして表示できるものではなく、バイナリとして表示しないとあまり意味を掴めない。バイナリ表示ができるテキストエディタを使ってもよいが、ここではodコマンドを用いる。 $ od -Ax -tx1z tmp.zip 引数の意味は以下の通り。man odでも確認できる。 -A: アドレスの基数(Address-radix)。出力時、最も左の値がファイル先頭から何バイト目なのかを表示する。続けてxと書くと、16進数(hex)で出力する。 -t: データの出力形式(おそらくtypeの略)。 続けてx1と書くと、1バイト区切りの16進数で出力する。 続けてzと書くと、右側にテキストでの表示を添える。ただし表示されるのはASCIIコードで認識される文字のみ。 結果は以下のようになる。 000000 50 4b 03 04 0a 00 00 00 00 00 28 70 64 50 4b 82 >PK........(pdPK.< 000010 70 33 0e 00 00 00 0e 00 00 00 07 00 1c 00 66 6f >p3............fo< 000020 6f 2e 74 78 74 55 54 09 00 03 1b 36 5f 5e 1b 36 >o.txtUT....6_^.6< 000030 5f 5e 75 78 0b 00 01 04 e8 03 00 00 04 e8 03 00 >_^ux............< 000040 00 48 65 6c 6c 6f 2c 20 57 6f 72 6c 64 2e 0a 50 >.Hello, World..P< 000050 4b 03 04 0a 00 00 00 00 00 2b 70 64 50 cb e8 62 >K........+pdP..b< 000060 fc 0a 00 00 00 0a 00 00 00 07 00 1c 00 62 61 72 >.............bar< 000070 2e 74 78 74 55 54 09 00 03 21 36 5f 5e 21 36 5f >.txtUT...!6_^!6_< 000080 5e 75 78 0b 00 01 04 e8 03 00 00 04 e8 03 00 00 >^ux.............< 000090 47 6f 6f 64 20 42 79 65 2e 0a 50 4b 01 02 1e 03 >Good Bye..PK....< 0000a0 0a 00 00 00 00 00 28 70 64 50 4b 82 70 33 0e 00 >......(pdPK.p3..< 0000b0 00 00 0e 00 00 00 07 00 18 00 00 00 00 00 01 00 >................< 0000c0 00 00 a4 81 00 00 00 00 66 6f 6f 2e 74 78 74 55 >........foo.txtU< 0000d0 54 05 00 03 1b 36 5f 5e 75 78 0b 00 01 04 e8 03 >T....6_^ux......< 0000e0 00 00 04 e8 03 00 00 50 4b 01 02 1e 03 0a 00 00 >.......PK.......< 0000f0 00 00 00 2b 70 64 50 cb e8 62 fc 0a 00 00 00 0a >...+pdP..b......< 000100 00 00 00 07 00 18 00 00 00 00 00 01 00 00 00 a4 >................< 000110 81 4f 00 00 00 62 61 72 2e 74 78 74 55 54 05 00 >.O...bar.txtUT..< 000120 03 21 36 5f 5e 75 78 0b 00 01 04 e8 03 00 00 04 >.!6_^ux.........< 000130 e8 03 00 00 50 4b 05 06 00 00 00 00 02 00 02 00 >....PK..........< 000140 9a 00 00 00 9a 00 00 00 00 00 >..........< 00014a シグネチャ zipファイルは以下のような要素を持つ。 ...

前回はBrowsertやSvgなどの標準的なパッケージを利用してドラッグ機能を実現した。今回はelm-draggableというパッケージを使ってドラッグ機能を実現してみる。 準備 Elmのプロジェクトを作成して、src/Main.elmとsrc/Circle.elmを作成。 Circle.elm 前回と同じなのでコードだけ載せる。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 module Circle exposing (..) type alias Id = Int type alias Circle = { id : Id , x : Float , y : Float , r : Float } type alias Circles = { all : List Circle , nextId : Id } empty : Circles empty = { all = [] , nextId = 0 } type alias CircleNoId = { x : Float , y : Float , r : Float } add : CircleNoId -> Circles -> Circles add c circles = let circle = { id = circles.nextId , x = c.x , y = c.y , r = c.r } in { circles | all = circle :: circles.all , nextId = circles.nextId + 1 } fromList : List CircleNoId -> Circles fromList list = { all = List.indexedMap (\i c -> { id = i, x = c.x, y = c.y, r = c.r }) list , nextId = List.length list } toList : Circles -> List Circle toList circles = circles.all update : Id -> (Circle -> Circle) -> Circles -> Circles update id f circles = let new = List.foldr (\c acc -> if c.id == id then f c :: acc else c :: acc ) [] circles.all in { circles | all = new } Main.elm Circlesを描画するところまで書く。 ...

ElmでSVGの要素をドラッグ移動したいと思った。ドラッグ操作を実現するパッケージにelm-draggableがある。今回は勉強として、それに頼らず実装することを試みる。elm-draggableを用いた方法については次回やる。 初期状態 詳細は省略するが、Elmプロジェクトを作成してelm/svgとelm/jsonをインストールしておく。 src/Main.elmは以下のようにしておく。elm reactorで動くことを確認する。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 module Main exposing (..) import Browser import Browser.Events as BE import Html exposing (..) import Html.Attributes exposing (..) import Json.Decode as JD import Svg as S exposing (Svg) import Svg.Attributes as SA import Svg.Events as SE main = Browser.element { init = init , update = update , view = view , subscriptions = subscriptions } type alias Model = {} type Msg = Dummy init : () -> ( Model, Cmd Msg ) init _ = ( {}, Cmd.none ) update : Msg -> Model -> ( Model, Cmd Msg ) update msg model = ( model, Cmd.none ) view : Model -> Html Msg view model = div [] [] subscriptions : Model -> Sub Msg subscriptions model = Sub.none 目標 SVGの領域に円が複数存在する 円をドラッグ移動できるようにしたい。 円のドラッグ中はその色を橙色にし、それ以外のときは白にする 方針 ドラッグ処理については次の処理で実現することになる。 ...