問題 https://atcoder.jp/contests/abc167/tasks/abc167_c 解法 解法としては各本を買う/買わないで全探索するとO(M2^N)で解けます。 C_n A_n_mは型としては[(Int, [Int])]になります。各要素の(Int, [Int])は単位元を(0, 要素が0の無限リスト)、演算をfstは足す、sndはzipして各要素を足すとするとモノイドになりそうですし問題を解くのに使えそうです。このようになる(Int, [Int])のnewtypeは(Sum Int, Ap ZipList (Sum Int))になります。ApはApplicative fとMonoid aからMonoid (f a)を作るnewtypeです。ZipListはpureをrepeat x、liftA2をzipして関数適用というApplicative実装を持つListのnewtypeなのでApと組み合わせると欲しいMonoidが得られます。 ところでnewtypeの変換にはcoerceという関数が便利です。安全に変換できる

pick関数 lodashなどにはオブジェクトと抽出するプロパティ名の配列を受け取り、指定されたプロパティのみを含むオブジェクトを返すpick関数が存在します。以下のような関数です。 // { a: 1, c: 3 } pick({ a: 1, b: 2, c: 3 }, ["a", "c"]) 今回はこの関数に安全な型定義をすることを考えていきます。 単純な型定義とその問題点 まず思いつくのは以下のような型定義だと思います。 declare function pick<A, K extends keyof A>(obj: A, keys: K[]): Pick<A, K>; // ex1: { a: number } const ex1 = pick({ a: 1, b: 2, c: 3 }, ["a"]); // ex2: { a: number, b: number } const ex2 = pick({ a: 1, b: 2, c: 3 }, ["a", "b"]); // ex3: {} const ex3 = p

以下のコードを見てください。 type HogeUnion = 1 | 2; function printHogeUnion(x: HogeUnion) { console.log(x); } HogeUnion型、つまり1 | 2であるxを受け取って出力するだけの単純な関数printHogeUnionを定義しています。何も問題がないコードです。 もしTSの型の健全性が壊されてxに1 | 2以外の値が入ってきた時にすぐ気付けるようにランタイム型チェックを行いたくなったとしましょう。例えばprintHogeUnion(0 as any)を実行すると0を出力するのではなく例外を投げるといった具合です。この時unreachable関数を定義し、printHogeUnionにランタイム型チェックのコードを追加して以下のようになります。 function unreachable(): never { throw new Error("unreachable"); } function printHogeUnion(x: HogeUni

はじめに RustでWebAssemblyインタプリタを作ったのでその実装の話や、wasmの仕様についての記事です。 HListを使ったジェネリックプログラミングの話や、最後の方には「自作言語 on 自作wasmインタプリタ on 自作wasmインタプリタ」みたいな話も出てきます。 分かりにくい所や間違っている所は指摘してくださると助かります。 リポジトリ https://github.com/kgtkr/wasm-rs 作った成果物のリポジトリです。まだpublishはしていませんがクレートになっています。 cargoのexample実行に対応しているのでそれを見ればだいたい分かると思います。 今回はadc-2019-12-22というタグがついたコミットのソースを元に解説していきます。 https://github.com/kgtkr/wasm-rs/tree/adc-2019-12-22 仕様書 この記事では仕様書を読みながら順番に実装を解説していきます。 https://webassembly.github.io/spec/

Rustにはcatch_unwindという関数がありpanicをキャッチすることが出来ます。 Rustのパニック機構 - 簡潔なQ しかしここから得られるエラー情報がかなり少ないです。キャッチして得られるResultのError型はBox<dyn Any>みたいな型ですが、これがほとんどStringまたは&strとなっており(今の所他の型を見ていませんが詳しい方教えて下さい)、確認した所スタックトレース情報やパニックが発生したソースの位置情報は入っていませんでした。例えば以下のコードはpanic testと出力します。 if let Err(e) = panic::catch_unwind(move || { panic!("panic test"); }) { println!("{}", any_to_string(&*e)); } fn any_to_string(any: &dyn std::any::Any) -> String { if let Some(s) = any.downcast_ref::<S

資料 31回だったのに32回と勘違いしててURLが32になっていますが気にしないでください。ライブデモ多いので多分LT資料だけじゃよく分かりません。 https://gitpitch.com/kgtkr/slide-student-lt-32 LT動画 内容 自己紹介wasmに関する説明 watについて(watコード読みながら解説した)wasm(バイナリ)について(wasmバイナリ読みながら解説した) rustでwasmインタプリタ作った話 デコーダーエンコーダースタックマシン 自作言語 on 自作インタプリタ(ライブデモ)自作言語 on 自作インタプリタ on 自作インタプリタ(ライブデモ) 補足資料とか 成果物: https://github.com/kgtkr/wasm-rswasm仕様書: https://webassembly.github.io/spec/core/index.html自作言語などについて(去年のアドカレ) WebAssemblyでメモリアロケータを実装WebAssemblyでGCを実装するWebAssemblyに

はじめに WebAssemblyにはbrという命令があります。 この命令はbr <label>という形になっており、<label>が示す制御構造に対して何らかの動作をします。 例えばブロックに対して使えばブロックを抜け、ループの中で使えばcontinueのような振る舞いをします。 wasmのループについてはκeenさんのWebAssemblyのloopはまりどころという記事を見てみて下さい。 なぜこのように制御構造によってブロックを抜ける働きをしたり、continueの働きをしたりするか仕様書を読んでいたところ理由が分かり面白いと思ったので記事にしました。 br命令 基本的にはbr 数値という形の命令です。この数値は相対的な値となっておりbr命令を囲っているすぐ外側の制御構造に対してなにかするときはbr 0と、その外側であればbr 1と...いうふうに指定します。 また、watでは制御構造に$labelをつけることでbr $labelと書けばbr命令がどの深さに関係なくその制御構造に対して命令を実行することができます。 例 関数に対して

初めに この記事は型安全な型定義とそれが可能な実装に関する考察であり利用者側にとっての使いやすさなどは考慮していません。ここに型安全ではない例としてあげた、もしくそれと同じような定義となっているライブラリも型推論に頼っていれば基本的に安全な事と、使いやすさを考えると仕方ない部分があることは理解しておりそのようなライブラリに対する批判でもありません。 曖昧な知識で考えた自分用メモのようなものなので間違っている所がある可能性は高いですし参考にはしないで下さい。間違ってる所があればTwitterなどで指摘してくださると嬉しいです。 オブジェクトのキーの集合の値表現 以下のような関数定義があるとする。 function f<T extends object, K extends keyof T>(obj: T, keys: Keys<K>): Result<T, K>; この時型コンストラクタResultの性質によって場合分けし、Keys、つまりオブジェクトのキー集合の安全な受け取り型を考える。 またobj: Tとkeys: Keys<K>を

TL;DR import { isT, isNotT, defineIsT } from "safe-type-predicate"; // isA: (x: "a" | "b") => x is "a" const isA = defineIsT((x: "a" | "b") => x === "a" ? isT(x) : isNotT() ); GitHub safe-type-predicate type predicate and its dangers TypeScript has a feature called type predicate. This is by coding the return value of a function that takes an appropriate type of value x and returns boolean as x is T. If true is returned, x is of type T, false This is a function that

TL;DR import { isT, isNotT, defineIsT } from "safe-type-predicate"; // isA: (x: "a" | "b") => x is "a" const isA = defineIsT((x: "a" | "b") => x === "a" ? isT(x) : isNotT() ); GitHub safe-type-predicate type predicateとその問題点 TypeScriptにはtype predicateという機能が存在する。 これは適当な型の値xを受け取りbooleanを返す関数の戻り値をx is Tと書くことで､trueを返せばxがT型､falseを返せばそうでないことを表す機能である。 これによってユーザー定義関数で型ガードを行うことを可能にしている。 例えばunknown型、つまり任意の型を受け取りその値がstring型であるかを返す関数は次のようになる。 function isString(x: unknown): x is