yn2011's blog

技術メモ

総和の剰余(mod) を計算したい

C - Sum of product of pairs で躓いたのでメモ。

総和の剰余(mod)

整数 a1, a2, a3 ... の 総和の剰余(mod) を計算したい。

(a1 + a2 + a3 ... ) % m

このとき、上の計算は以下と同値である。

(a1 % m + a2 % m + a3 % m ... ) % m

これを剰余演算の分配法則と同一性から示す。

剰余演算の分配法則から以下が成り立つ。

(a1 + a2) % m = (a1 % m + a2 % m) % m

すると、以下のように変形できる。

(a1 + a2 + a3 ... ) % m
= (a1 % m + (a2 + a3 ... ) % m ) % m
= (a1 % m + (a2 % m + (a3 + a4...) % m) % m) % m
...
= (a1 % m + a2 %m + ...) % m % m ...

また、剰余演算の同一性から以下が成り立つ。

a % m = (a % m) % m

したがって、

 (a1 % m + a2 %m + ...) % m % m ...
= (a1 % m + a2 %m + ...) % m

と変形できる。

なので、総和の剰余を求める場合は、剰余の総和を取って最後に剰余を取ってもいいし

int sum = 0;
for(int i = 0; i < n; i++) {
  sum += a[i] % m;
}
sum %= m;

変形前の式から見ると、加算する度に剰余を取ってもいい(オーバーフローを防げるので安全)

int sum = 0;
for(int i = 0; i < n; i++) {
  sum += a[i] % m;
  sum %= m;
}

(+-*)の演算をする度に剰余を取ると思っておいて良さそう。除算は逆元が絡むのでまた別の話。

参考

TypeScript の演算子を整理する

TypeScript (というか最近のJavaScript)って、よく分からない演算子多くないですか? なんか色々な箇所で! とか ? とか見るので意味が分からないと結構ストレスになります。

自分があんまりキャッチアップしてないのが悪いんですが、馴染みがない/薄い演算子について使い方と登場の背景を整理した自分用のメモ。

Nullish Coalescing (??)

TypeScript 3.7~ で利用可能

こういうやつ

let x = foo ?? bar();

要はこれのシンタックスシュガー

let x = foo !== null && foo !== undefined ? foo : bar();

なぜ必要か

JavaScript を書いてフロントエンドの開発をすると上のような書き方を頻繁にするから。特にレガシーなフロントエンドのコードベースに少し手を入れる時なんかは、どの変数がいつ null や undefined になるか予想がつかない場合も多く、とにかく安全側に倒したかったりする。(例外が発生すると処理が止まるので)

ちなみに、単に x = foo || bar() と書くと、foo が 0 だったり空文字だったりすると false になって bar() が評価されるので困る。JavaScript 初心者が絶対に1度はハマる罠。?? だと NaN は回避されないみたいですが。

Optional Chaining(?)

TypeScript 3.7~ で利用可能

こういつやつ

let x = foo?.bar;

要はこれのシンタックスシュガー

let x = foo === null || foo === undefined ? undefined : foo.bar;

なぜ必要か

let x = foo && foo.bar とか書きたくないから。これもレガシー系フロントエンドの改修でありがちで、オブジェクトのプロパティと値がまったく予想できないので、こう書くしか無いパターンが多かった。とても助かる。がそもそも使わなくても良いのが望ましいとは思う。

Optional parameter (?)

こういうやつ

function foo(bar?: string) {
    ...
}

? を付けると string | undefined 型に推論される。これは厳密に演算子という区分なのかは分からないけど、まあそんな感じのものだと思ってる。

なぜ必要か

JavaScript の関数の引数は全て省略可能だが、引数が与えられない可能性があるのか、ないのかは区別できた方が嬉しい。そしてそうしないと型定義できない。

rest parameters (...)

こういうやつ

function foo (bar: string, ...baz: string[]) {
    ...
}

引数を無限に受け取ることを宣言できる。spread operators とはまた別だと思う。

なぜ必要か

無限に引数を受け取ること自体は従来からできて、 関数内から arguments で参照可能だった。ただし引数の宣言からはそれが読み取れなかったので分かりやすくなった。そしてそうしないと型定義できない。

Non-null assertion operator (!)

TypeScript 2.0~ で利用可能

こういうやつ

function foo(f?: Foo) {
    let bar = f!.bar; 
}

要はこれのシンタックスシュガー

let bar = (f as Foo).bar; 

なぜ必要か

外部のライブラリの型定義上 foo | undefined みたいに定義されているが、自分の実装上は絶対に undefined にならないから何とかしたいみたいなときに使うことが多い気がする。(自分が定義した型でこれが頻出するならそもそも型定義を見直した方がいいんじゃないか)

Short-Circuiting Assignment Operators (&&=, ||=, ??=)

TypeScript 4.0~ で利用可能

こういうやつ

a &&= b;
a ||= b;
a ??= b;

要はこれのシンタックスシュガー

a = a && b;
a = a || b;
a = a ?? b;

ちなみに、JavaScript に馴染みがなかったり、しばらく別の言語を書いていたりすると、「え? a && b とか a || b って bool 型しか返さないのでは?」となるかもしれない。 JavaScript の場合はそんなことはなく、短絡評価をして

  • a && b :a が false なら a を返す
  • a || b :a が true なら a を返す

という仕様になっている。この true か false かというのは、bool 型を期待しているわけではなく、JavaScript 流の解釈で、0, "", NaN, undefined, null ... 等は false でそれ以外が true みたいな感じに評価されるだけ。

非 bool 型の a, b で if(a && b) のように書くと、(if 文の条件式なので)返値が bool 型に変換されるのでそれっぽく振る舞っているだけという感じ。

なぜ必要か

正直、自分はあんまりこういうコードが必要になったことはない。まず、変数に対する再代入をすることがあまりない。JavaScript が一部継承している関数型プログラミングパラダイム的にも推奨してないと思う。

一方、競プロの問題を解く時は手続き的にサッと書きたいので、sum+=a とか sum /= a とかは頻繁に使う。でも a &&= b はあっても使うことないと思う。

あと、a ||= b するなら大抵は a ??= b の方が適切じゃないかと思う。上でも書いたけど、0 とか 空文字を false として扱って欲しいケースの方が少ない気がするので...

(a + b - 1) / b で a / b の切り上げを計算する

整数 a, b に対して、 a / b の切り上げを計算したい場合 (a + b - 1) / b するという小技が競技プログラミングではよく使われる。 なぜこれで切り上げが計算できるのか、良い感じの説明が検索しても出てこなかったので自分なりの理解を書いておく。

以下 / は一時的に分数の記号として、 b = 3 , a を 3から1ずつ増加させていく場合を考える。

3/3 = 1

4/3 = 1+1/3

5/3 = 1+2/3

6/3 = 2

7/3 = 2 + 1/3

...以下略

となるので、1 - 1 / b (b=3 の場合は 2/3) を加算して小数点以下を切り捨てれば切り上げと同じになる。

切り上げすべき場合は必ず商が繰り上がる。

切り上げすべきでない場合(上記の 3/3 , 6/3 のケース)は商が繰り上がらない。

よって、floor(a/b + (1-1/b))をすればよく、今度は / を切り捨て除算の記号として式変形すると (a+b-1)/b で同値と言える。したがってa / b の切り上げを計算したい場合 (a + b - 1) / b で計算できる。

ceil が使える言語ならそれでもいいんじゃないか?と思われるが、a, b の値によっては浮動小数点計算の誤差が発生する可能性があるので、この方法が安全らしい。なるほど。

まあ (a+b-1)/b の方がシンプルだし賢いやり方感がある。

TypeScript の共用体型は or ではないのかについて考えた

TypeScript の共用体型(Union Types)は or ではない を読み、確かによく分からん挙動だなーと思って色々調べたり考えたりしたことを書いておく。

最初に書いておくと、結論はよく分かってない。

まず、共用体型はタグ無し共用体型とタグ付き共用体型(Discriminated Unions)の2つに分けることができる。ので分けて考える。タグ付き共用体型が何を指すのかは後述する。

タグ無し共用体型

最初に、タグ無し共用体型について考える。

形状A, B に対して、A | BA & B で定義される型の性質

そもそもの性質の整理。何かベン図を使った説明をすることが多いみたいだけど、形状*1を表す型の場合はベン図ではうまく説明できない気がしている。

  • A | B は 少なくとも、A, B のいずれかの型を満たすようなプロパティを持つ(Aを満たすなら部分的にBのプロパティを持つことは許容される)

  • A & B は A, B のプロパティを全て持つ形状(A, B を満たしながら他のプロパティを持つことは許容されない)

ここで、A | BPartial(A & B)、つまり A, B のプロパティを全て持つが、省略も可能な形状と同値なのか?と思ったが、それは違う。A | B は、

  • A,B のプロパティを部分的に持ち、A, B のいずれも満たさない場合は不可
  • プロパティを持たない形状 {} は代入不可
type A = {
  a: string;
};

type B = {
  b: number;
};

type C = A | B;

const ab : C = {} // error 

A | B = A ∪ Bという理解は正しいのか

ベン図で理解しようとすると、A | B = A ∪ B 、つまり、AかBかAとB両方を満たす集合なんじゃないかと考えたくなる。

集合A を形状Aに割り当て可能な型とみるか、形状Aが持つプロパティの集合と見るかで違ってきそう。

前者で考えると、A を満たしながら B のプロパティを一部持つ形状は、A に割当不可能だし、A, B, A&B のどれにも割当不可能なので、A ∪ B に含まれないということになってしまう。「共用体型が or でない」ように思える。

後者で考えると、型を満たすかは関係なくて、単にプロパティの集合なので A ∪ B になる。すると共用体型が or であるように思える。

結局 A | B とは何なのか

少なくとも、A, B のいずれかの型を満たすプロパティを持つ形状としか言えないような。A, B のいずれかの型を実際に満たすわけでなくて、(余計なプロパティがなければ)少なくとも A, B のいずれかを満たすようなプロパティを持つ形状というだけなことが大事なのかも。

同じことを、単一の形状として、オブジェクトリテラル表記で形状の型として定義することはできない気がしている。

ちなみに type-fest というライブラリに、RequireAtLeastOne という型定義があり、見た感じ形状をA | Bすることで得られる性質を利用しているみたいだった。この型ユーティリティは1つの形状から特定のプロパティの集合を選択していずれかを必須にできるので、もっと汎用性が高い感じ。

例えば、RequireAtLeastOne<A, "a" | "b"> すると a, b のどちらかを必須にできる。

型定義の理解の仕方はこの記事 が役に立った。

タグ付き共用体型

次にタグ付き共用体型について考える。そもそもタグ付き共用体型とは何かというと、こういうやつ。

type A = {
  type: 'a'
  a: string
};

type B = {
  type: 'b'
  b: number
};

type C = A | B;

タグは、同じプロパティで定義され、値は共用体型の中で一意である必要がある。

この場合は、単純で、A | B は必ず A, B のいずれかになる。両方を満たしたり、片方を満たしながら片方のプロパティを持つことはできない。ベン図でいうと、A ∪ B から A ∩ Bを除いた集合で、形状以外の型の共用体型はこうなるはず。

なので、上の例でいうとこういうのはエラーになる。A を満たしているが、他の型のプロパティを部分的に持つことは許されない。

type C = A | B;

const c :C = {type: 'a', a: "hoge", b: 1} // error

タグ付きの場合は A | B に対する TypeScript の型推論も単純になる。(例えば a.type == 'a' で分岐させれば以降は 型が A に定まる)

ちなみに、タグを重複させるとタグ無し共用体型みたいに部分的にプロパティを持つことが可能になる。というか多分タグ無し共用体型と同じ型定義になる気がする。

type A = {
  type: 'a'
  a: string
};

type B = {
  type: 'a'
  b1: number
  b2: number
};

type C = A | B;

const c :C = {type: 'a', a: "hoge", b1: 1} // ok

*1:形状は、書籍プログラミングTypeScript で使われている用語で、オブジェクトリテラル表記で宣言される型のこと。TypeScript のオブジェクト型の他、クラスインスタンスも含まれる。多分最終的に JavaScript のオブジェクト型に変換されるものは全て含まれる

そもそも reflection とは何なのか

Go 言語を勉強していて reflection って何なんだろ、となったので調べた内容を書いておく。

そもそも reflection とは何なのか

wikipediaによると

情報工学においてリフレクション (reflection) とは、プログラムの実行過程でプログラム自身の構造を読み取ったり書き換えたりする技術のことを指す。

よく分からない。以下では reflection の概念について書いていく。(Go 言語の reflection パッケージ固有の話ではない)

自己書き換えコード

プログラムの実行過程でプログラム自身の構造を読み書きするというのはどういうことか。1つの例として自己書き換えコードがある。

プログラムはプロセッサが処理可能な機械語に変換されて動作する。例えば C言語の場合だと以下のような変換になる。

C言語 -> アセンブリ言語 -> 機械語

より変換の下流に位置している、アセンブリ言語機械語のコードの内容をプログラムから書き換えることができれば、プログラム(ソースコード)に記述された処理とは見かけ上異なる処理*1を実行させることができる。そのようなプログラムを自己書き換えコードと呼ぶ(らしい)

例えば、C言語アセンブリ言語で書かれたプログラムで命令が格納されているメモリを直接操作すると、その前にプログラム内で書かれた命令は意味をなさなくなる。具体例としては、自己書き換えコード(self-modifying code) 等を参照。

自己書き換えをしたいモチベーションとしては色々あるみたいで自分は低レイヤーな部分に明るくないのであまり理解できていない。とりあえず wikipedia には色々載っていた。

Brian Cantwell Smith は、このアセンブリ言語の自己書き換えコードの発想(メタプログラミング)を高級言語にも導入しようとした。これが reflection という概念の元になっているらしい。(Procedural reflection in programming languages がその論文っぽい。読んではない。)

reflection はメタプログラミング

上述のような背景があるので、メタプログラミングをしたいから reflection がある、と考えても良さそう。

メタプログラミング

ところでメタプログラミングとは何か。定義は色々ありそうだが、メタなプログラミング、プログラムをプログラムする(ある言語がある言語を読み書きする)というイメージで良いっぽい。

例えば eval に渡す文字列を組み立てるプログラムは、まさにプログラムをプログラムが書いているのでメタプログラミングの1つになると思う。 また、SQL の組み立てもそうだし、TypeScript も JavaScriptメタプログラミングになると思う。

先程の自己書き換えコードがメタプログラミングに含まれるかは微妙かもしれない(C言語アセンブリ言語(機械語)を読み書きしていると言えるのかもしれない)

reflection を実装し、プログラム自身の構造を読み書きしたい背景として、このメタプログラミング(特に、操作する言語と読み書き対象の言語が一致している場合)に役立つからというものがあると思う。 自分は reflection の概念を Go 言語で初めて知ったが、他の多くの言語にも実装されている。例えば JavaJavaScript にもある。

なぜメタプログラミングしたいのか

じゃあなぜメタプログラミングしたいのか。特に、操作する言語と読み書き対象の言語が一致しているメタプログラミングは何が目的なのか。

TypeScript 等、別の言語を生成するならまだしも、なぜ同じ言語を取り扱うメタプログラミングが必要とされるのか。

実行時にしか分からない情報を取得したい・その情報を使った処理を行いたい

例えば、Go の場合は以下がある。

  • interface 型の変数の値の型*2
  • 構造体タグ (タグ名や値は任意の値を設定でき、構文がおかしい場合は実行時エラーになる)
  • json 等の外部データ (を Go の型システムの世界に変換したい)

また、ジェネリックに近いことも reflect パッケージを使えば実現できる(コード例はWho needs generics? Use ... instead!の 5. Use reflection を参照)

ジェネリックのためにreflect パッケージを使うとそれなりに面倒な感じにはなるっぽいが、元々の言語仕様にないことを実現できてしまうのはメタプログラミングの力だと思う。

Go 言語の reflection について

色々と reflection の概念について書いてきた。実際の Go の reflect パッケージの取り扱い方については以下の資料が役に立ちそうなのでリンク。

その他参考

*1:プログラムは記述された通りにしか動かないのであくまで見かけ上

*2:一応 reflect を使わなくてもtype assertion で特定の型かどうかの判定はできる

Go の型システム周りについてのメモ

Go の型システムについて、今理解していることを書く。もしかしたら間違っているかもしれない。

Go の型システム

  • 型同士に階層がない(サブタイプ・スーパタイプのような関係がない)
    • 型は名前によって区別される。階層がないので、ある型が要求された場合にその型のサブタイプが許容されるようなことはない。
    • ただし、例外としてinterface 型の解決は形状(実装するメソッド)が一致していれば許容
  • 型は named type と unnamed type に分けられる

型の割当可能性

同一の型同士の割当は以下のルールに従う。

同一の型とは、以下を満たす型を指す。

  • named type 同士は名前が一致している(したがって型の実体が一致している)
  • unnamed type と named type は型の実体が一致している
    • unnamed type 同士も同様

以下の表では、同一の型同士であっても割当不可な場合について☓を記載している。

\ named type unnamed type
named type
unnamed type

(例) 2行目3列の場合は☓なので割当できない

// named type to unnamed type
hoge1 := "hoge1"
type a string 
var hoge2 a
hoge2 = "hoge2"
hoge1 = hoge2 // error : cannot use hoge2 (type a) as type string in assignment

ただし、interface 型の場合は例外で形状(実装するメソッド)が一致しているかどうかだけが問題になる

(例)

type c struct{}
func(p c) hoge(){}

func main(){

type hoge interface{hoge()}
var b1 hoge
var b2 interface{hoge()}

b1 = c{} // ok , named type to named type
b2 = c{} // ok , named type to unnamed type
}

複雑な型について

例えば、map[string]interface{}map[string]int は割当可能か?

型に階層関係の存在する言語(型システム)に慣れていると、これは割当可能ではないかと感じるが Go の型には階層関係がないので割当できない。互いに独立した無名型でしかない。

例えばTypeScriptの場合は map 型は以下のように割当できる。

const a = (b : Map<string, any>) => {};
const c = new Map<string, number>([['hoge', 1]])

a(c); // ok

TypeScript は、複雑な型(オブジェクト、クラス、配列、関数の戻り値)等はそのプロパティに関して全て共変である(=サブタイプ or 同じ型を要求すうる)とのこと*1

Go の場合は型に階層自体がないので、変性という概念もないのかもしれない。

Go は duck typing (あるいは structural typing) なのか

そもそも duck typing とは何か、その明確な定義があまりよく分かっていない。duck typing は動的型付言語に対して言う言葉らしいので、duck typing ではなく structural typing という言葉が正しいらしい。

例えば TypeScript は structural typing と言われ、いわゆる named type (名前型) はサポートしていないので以下が通ってしまう。

type a = string
const b = (c :a) => {};
b('hoge'); // ok 

Go は interface 型については structural typing だが、上でも書いたとおり名前型が使えるという点では完全な structural typing な言語とは言えないのでないか? その言語が structural typing である、というとき、それはどういう意味で使われているんだろうか?

Does Golang use structural typing, nominal typing, or both?

上記の回答によると、Go に関しては両方ということになるらしい。まあ確かにそうである。

これも Go が行っている試みの1つなのかもしれない

There are many things in the Go language and libraries that differ from modern practices, simply because we feel it's sometimes worth trying a different approach.

Why does Go not have assertions? より引用

参考

Named and Unnamed Types

*1:プログラミングTypeScript P122

シェルスクリプトの任意の箇所で git の branch 名をあいまい検索するエイリアスが便利

環境

モチベーション

git pushgit checkout など、branch 名を タイプしないといけないときに正確に branch 名を入力するのが面倒くさい

結果

B と書かれている箇所にあいまい検索で見つけた branch 名を挿入する

f:id:pokuwagata:20200523224610g:plain

設定

.zshrc に以下のエイリアスを置く

alias -g B='$(git branch -a | fzf)'
  • fzf のインストールは必要
  • -g オプションでコマンドの先頭以外でもエイリアスが効くようにする

その他

remote にしか branch がない場合は git checkout -t B すると 対象を upstream に指定しつつローカルに同名の branch を作れる