D言語: foreach の変数展開の仕組みが分からない
import std.experimental.all; void main() { foreach (a; [10, 20, 30]) writeln(a); }
と書くと、配列の中身が foreach
の変数 a
に代入されて以下のように出力されます。
10 20 30
次に foreach
の変数をひとつ追加します。
すると、その追加した変数には配列のインデックスが格納されます。
import std.experimental.all; void main() { foreach (i, a; [10, 20, 30]) // 変数 i を追加した writeln(i, " ", a); // i はインデックス。a には配列の各要素 }
実行結果です。
0 10 1 20 2 30
さて、次は標準ライブラリの cartesianProduct 関数を使ったサンプルです。この関数は、引数で渡した配列の各要素の組み合わせを求める関数です。
import std.experimental.all; void main() { foreach (a; cartesianProduct([1, 2], [3, 4])) writeln(a); }
実行結果です。要素はタプルとしてまとめられます。
Tuple!(int, int)(1, 3) Tuple!(int, int)(1, 4) Tuple!(int, int)(2, 3) Tuple!(int, int)(2, 4)
ここで foreach
の変数をひとつ追加します。このとき、各変数にはタプルの各要素が代入されます。
import std.experimental.all; void main() { foreach (a, b; cartesianProduct([1, 2], [3, 4])) writeln(a, " ", b); }
実行結果です。
1 3 1 4 2 3 2 4
なるほど、各タプルの要素が展開されるのですね。
では、たとえば [tuple(1, 2), tuple(3, 4)]
のような、タプルの配列があるとき
foreach
で各タプルの要素を変数で受けようとしても期待する結果にはなりません。
import std.experimental.all; void main() { foreach (a, b; [tuple(1, 2), tuple(3, 4)]) writeln(a, " ", b); }
実行結果です。
0 Tuple!(int, int)(1, 2) 1 Tuple!(int, int)(3, 4)
上記のように、foeach
の変数 a
には配列のインデックスが格納されます。
配列と、cartesianProduct 関数のときで違いがでるのがよく分からないですね。
foreach
の変数 a
に 1 と 3 が代入されるようには書けないのですかね?
追記
twitter で教えていただきました。感謝です!
Tupleの配列と、TupleのInputRangeの違いです。foreachで回せる型は、配列と連想配列とopApplyのあるクラスや構造体とRange(と実はdelegate)があるんです。それぞれで2つの変数にした場合に格納されるものが違うんです。
— SHOO C94でお買い上げの皆様、ありがとうございました!! (@mono_shoo) August 11, 2018
cartesianProductは、ドキュメントに"Returns: A forward range of std.typecons.Tuple..." と書かれているようにRangeを返します。(ForwardRangeはInputRangeの仲間)
— SHOO C94でお買い上げの皆様、ありがとうございました!! (@mono_shoo) August 11, 2018
配列を zip
でくるんで Input Range にするサンプル:
import std.experimental.all; void main() { foreach (a, b; zip([tuple(1, 2), tuple(3, 4)])) { writeln(a, " ", b); } }
実行結果です。
1 2 3 4
D言語: 2, 3, 5, 7... のシーケンスを作る
D 言語で、2, 3, 5, 7... のシーケンスを作る方法です。
素数をふるいにかけるとき
- 2 で割り切れるか
- 3, 5, 7... で割り切れるか
を試しますが、これらを分離せずにひとつのシーケンスとして扱えると便利ですね。
import std.experimental.all; void main() { // 有限のサイズ auto a = chain([2], iota(3, 10, 2)); writeln(a); // [2, 3, 5, 7, 9] // 無限のサイズ auto b = chain([2], recurrence!((a, n) => a[n-1] + 2)(3)); writeln(b.take(10)); // [2, 3, 5, 7, 9, 11, 13, 15, 17, 19] }
隣り合う要素でグループ分け
0 と 1 からなる配列があります。
たとえば [0, 1, 1, 0, 0, 1, 0, 0]
の配列を [[0], [1, 1], [0, 0], [1], [0, 0]]
のように 0 と 1 とでグループ分けする関数が必要になったので作ってみました。
def group(xs) return [] if xs.empty? g = [] buf = [xs[0]] xs.drop(1).each {|e| same = yield buf[-1], e if same buf << e else g << buf buf = [e] end } g << buf g end
実行結果です。
p group([1, 1, 0, 0, 0, 1, 0, 1, 1]) {|a, b| a == b } #=> [[1, 1], [0, 0, 0], [1], [0], [1, 1]] # 偶奇でグループ分け p group([2, 4, 6, 1, 3, 6, 8]) {|a, b| a % 2 == b % 2 } #=> [[2, 4, 6], [1, 3], [6, 8]]
Ruby で三角数の無限シーケンスを作る
まずは Enumerator で三角数を具体的に生成してみよう。
def triangles Enumerator.new do |y| sum = 0 1.step {|i| sum += i y << sum } end end p triangles.take(10) #=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
三角数を生成するところをもっと抽象化したい。
iterate を作ってみる。
def iterate(init) x = init Enumerator.new do |y| y << x loop { y << (x = yield x) } end end def triangles2 x = 1 iterate(1) {|sum| x += 1; sum + x } end p triangles2.take(10) #=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
iterate の外側で変数(x)を定義しないようにできないかな。
def triangles3 iterate([1, 2]) {|a, b| [a + b, b + 1] }.lazy.map {|e| e[0] } end p triangles3.take(10).to_a #=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
iterate 内で三角数とインデックスを引き回すようにしてみた。
lazy
の部分はきちんと理解していない。
Haskell には scanl という関数があるみたいだ。
Ruby で scanl を定義してみよう。
module Enumerable def scanl(z) Enumerator.new do |y| y << z x = z each {|e| y << (x += e) } end end end def triangles4 2.step.scanl(1) {|a, b| a + b } end p triangles4.take(10) #=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
SageMath でフィボナッチ数の練習
sage: def fib(n): ....: if n == 0: return 0 ....: m = matrix([[1, 1], [1, 0]]) ** n ....: return m[0, 1] ....: sage: [fib(i) for i in range(20)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
参考
Python で多次元リストを作る
Python で 2 次元リストを作るには、リスト内包表記を使って以下のように書くことが出来ます。
>>> rows, cols = 2, 3 >>> [[0] * cols for _ in range(rows)] [[0, 0, 0], [0, 0, 0]]
2 次元まではいいのですが、3 次元以上になるとリスト内包表記で書くのはなかなか難しいです。
そこで、多次元リストを返す関数を作ってみました。
def multilist(ds, default): assert len(ds) > 0 and all(e > 0 for e in ds) def rec(index, parent): if index + 1 == len(ds): parent.extend(default() for _ in range(ds[-1])) else: for _ in range(ds[index]): child = [] parent.append(child) rec(index + 1, child) root = [] rec(0, root) return root
こういう風に使います。
>>> multilist([2, 3], lambda: 0) [[0, 0, 0], [0, 0, 0]] >>> multilist([2, 3, 4], lambda: 0) [[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]]
この関数を使って、ABC 029 D - 1 を解いてみました:
collections.defaultdict とタプルを使う方法もあります
>>> import collections >>> d = collections.defaultdict(lambda: 0) >>> d[1, 2, 3] = 100 >>> d[1, 2, 3] 100 >>> d[0, 0, 0] 0
curry, uncurry
Prelude> :t curry curry :: ((a, b) -> c) -> a -> b -> c Prelude> :t uncurry uncurry :: (a -> b -> c) -> (a, b) -> c Prelude> add (a, b) = a + b Prelude> curry add 2 3 5 Prelude> mul a b = a * b Prelude> uncurry mul (2, 3) 6
curry
はタプルから引数へ展開uncurry
は引数をタプルにまとめる
というようなイメージなのかな。
zip
した各要素には uncurry
が使えそう。
Prelude> xs = map (uncurry (+)) $ zip [1..] [2..] Prelude> take 10 xs [3,5,7,9,11,13,15,17,19,21]