LoginSignup
1
0
この記事誰得？ 私しか得しないニッチな技術で記事投稿！
Qiita Engineer Festa20242024年7月17日まで開催中！
@Syuparn

【Go1.23】range over func原理主義者のためのモジュール作りました【itermania】

Posted at

TL; DR

prime := Bind(Inc(2), func(n int) Gen[int] {
	return Where(Const(n), All(Not(Eq(Mod(Const(n), Range(2, n, 1)), Const(0)))))
})

for i := range Head(prime, 10)() {
	fmt.Println(i)
}

2
3
5
7
11
13
17
19
23
29

はじめに

Go1.23から、for文の range に関数を指定することができるようになります。これによって、スライスを用いない反復処理をシンプルに書くことができます。

// 0~2を繰り返すイテレータ
func rotate(yield func(int) bool) {
	i := 0
	for {
		// yieldの引数がループ変数として渡される
		if !yield(i) {
			// for文本体のループがcontinue, break等で終了した場合falseが返るので、イテレータも中断する
			return
		}
		i = (i + 1) % 3
	}
}

func main() {
	// イテレータを range に指定
	for i := range rotate {
		fmt.Println(i)
	}
}
結果
0
1
2
0
1
2
...

ジェネリクス以来の大幅な文法変更、このビッグウェーブを逃すわけにはいきません。
というわけで、本記事ではイテレータ だけで プログラムを組んでいきたいと思います。

イテレータだけで処理を書く

先達はあらまほしきことなり。まずはお手本になる設計を探します。
今回は、Icon言語の「ジェネレータ」を目標にしました。

Icon言語は、言語仕様としてジェネレータ（Goのイテレータに相当）を持っています。
以下、「Rubyist のための他言語探訪」より素数を生成するソースコードの引用です。

素数を無限に生成するジェネレータ（引用、コメントのみ追記）
# 素数を生成するジェネレータ（「エラトステネスの篩」を使用）
procedure sieve()
  # iを2から1ずつ増やし、「2からi-1までのすべての整数(jとする)に対し i % j == 0でない」ならばiを生成
  every i:=seq(2) & not(every i%(2 to i-1)=0 & break) & suspend(i)
end

procedure main()
  # 素数を小さい順に100個表示
  every write(sieve() \ 100)
end

i%(2 to i-1) で「iを2からi-1までの各整数で割ったあまり」（[i % 2, i % 3, i % 4, ..., i % (i - 1)]） というジェネレータが得られるため、反復処理込みで2行で書くことができています。初めて見たときは衝撃を受けました。

もしこれがGoで実現できればどうでしょう？我々はもう深いfor文や嵩むif文に怯える必要はありません。イテレータを使い倒して、1行野郎を目指しましょう1。

言うまでもありませんが 本記事はネタ記事です。実用性は度外視しています。
真面目なコードはお作法に従って書きましょう。

検証したバージョン

  • Go1.23 rc1

正式リリースまでに仕様が変更される可能性があります。

イテレータだけで処理を書く

作ったのがこちらのモジュールです。

このモジュールを使えば、Icon言語のように素数一覧の生成もお手のものです。

prime := Bind(Inc(2), func(n int) Gen[int] {
	return Where(Const(n), All(Not(Eq(Mod(Const(n), Range(2, n, 1)), Const(0)))))
})

for i := range Head(prime, 10)() {
	fmt.Println(i)
}
結果
2
3
5
7
11
13
17
19
23
29

行が多くて気に食わないのであれば、こう書き直しましょう。
Go言語は3行で素数を求められます。

for i := range Head(Bind(Inc(2), func(n int) Gen[int] { return Where(Const(n), All(Not(Eq(Mod(Const(n), Range(2, n, 1)), Const(0))))) }), 10)() {
	fmt.Println(i)
}

FizzBuzzだってこの通りです。

fizzbuzz := Bind(Inc(1), func(n int) Gen[string] {
	return If(Eq(Mod(Const(n), Const(15)), Const(0)), Const("FizzBuzz"),
		If(Eq(Mod(Const(n), Const(3)), Const(0)), Const("Fizz"),
			If(Eq(Mod(Const(n), Const(5)), Const(0)), Const("Buzz"),
				Const(strconv.Itoa(n)))))
})

for i := range Head(fizzbuzz, 15)() {
	fmt.Println(i)
}

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

では、続いて実際の実装について見ていきましょう。

数列を生成するイテレータ

まずは基本となる数列をイテレータで生成します。

Inc

名前の通り、生成される値が1ずつ増えていきます。スライスと異なり 無限長 の要素を生成可能です。

func Inc[V constraints.Integer](v V) iter.Seq[V] {
	return func(yield func(V) bool) {
		for {
			if !yield(v) {
				return
			}
			v++
		}
	}
}

for i := range Inc(1) {
	fmt.Println(i)
}

1
2
3
4
5
...

Range

続いて、開始、終了、増分を指定できる数列です。Pythonの range 関数から名前を取ったのですが、range Range の字面が紛らわしいのが反省点です。

func Range[V constraints.Integer](start, stop, step V) iter.Seq[V] {
	return func(yield func(V) bool) {
		i := start
		increasing := step > 0
		for {
			if (increasing && (i >= stop)) || (!increasing && (i <= stop)) {
				return
			}

			if !yield(i) {
				return
			}
			i += step
		}
	}
}
例
for i := range Range(1, 11, 2) {
	fmt.Println(i)
}

1
3
5
7
9

スライス

決め打ちで値を入れたい際にも使えるよう、スライスをイテレータに変換する関数も用意しました。

for s := range FromSlice([]string{"a", "b", "c"}) {
	fmt.Println(s)
}

func FromSlice[V any](values []V) iter.Seq[V] {
	return func(yield func(V) bool) {
		for _, v := range values {
			if !yield(v) {
				return
			}
		}
	}
}

イテレータ同士の演算

続いて、イテレータを加工する関数を用意します。もちろん戻り値もイテレータです。

単項演算

bool反転
for i := range Not(FromSlice([]bool{true, false})) {
	fmt.Println(i)
}

false
true

// 符号反転
func Not(gen iter.Seq[bool]) iter.Seq[bool] {
	uni := Uni(func(v bool) bool {
		return !v
	})
	return uni(gen)
}

// 単項演算の共通処理
func Uni[V, W any](op func(V) W) func(iter.Seq[V]) iter.Seq[W] {
	return func(xSeq iter.Seq[V]) iter.Seq[W] {
		return func(yield func(W) bool) {
			for x := range xSeq {
				if !yield(op(x)) {
					return
				}
			}
		}
	}
}

二項演算

二項演算では、2つのイテレータの直積に対して演算子を適用しています。これは、冒頭のIcon言語の仕様に合わせました。

for i := range Mul(FromSlice([]int{10, 100}), FromSlice([]int{2, 3})) {
		fmt.Println(i)
}

20  // 10 * 2
30  // 10 * 3
200 // 100 * 2
300 // 100 * 3

// 二項演算の共通処理
func Bin[V, W any](op func(V, V) W) func(iter.Seq[V], iter.Seq[V]) iter.Seq[W] {
	return func(xSeq iter.Seq[V], ySeq iter.Seq[V]) iter.Seq[W] {
		return func(yield func(W) bool) {
			for x := range xSeq {
				for y := range ySeq {
					if !yield(op(x, y)) {
						return
					}
				}
			}
		}
	}
}

// 積を求める
func Mul[V Number](xSeq iter.Seq[V], ySeq iter.Seq[V]) iter.Seq[V] {
	bin := Bin(func(xVal V, yVal V) V {
		return xVal * yVal
	})
	return bin(xSeq, ySeq)
}

単一の値をイテレータ化する

すべてをイテレータ化するということは、当然単一の値もイテレータに変換する必要があります（でないと上記の演算用関数の引数に渡せません）。
この関数があれば、以下のように「数列をn倍する」等の演算を簡単に書けます2。

3の倍数の数列
// Const: リテラルをイテレータ化する関数
Mul(Const(3), Inc(1)) // 3, 6, 9, ...

実装はシンプルで、1度だけ値を yield して終了しています。

func Const[V any](v V) Gen[V] {
	return func() iter.Seq[V] {
		return func(yield func(V) bool) {
			if !yield(v) {
				return
			}
		}
	}
}

for i := range Const(5)() {
	fmt.Println(i)
}

5

イテレータを変数として使う

Icon言語の素数を求める処理では、変数を使用して同じイテレータ（ジェネレータ）を複数回使いまわしています。

素数を無限に生成するジェネレータ（再掲）
 procedure sieve()
   # 変数 i を使って、ジェネレータを使いまわしている
   every i:=seq(2) & not(every i%(2 to i-1)=0 & break) & suspend(i)
 end

では、このモジュールでも同じことをやってみましょう。

以下はコンパイルエラー
i := Inc(2)
// ConstやRangeはintを引数に取るが、iはイテレータなので型が合わない
prime := Where(Const(i), All(Not(Eq(Mod(Const(i), Range(2, i, 1)), Const(0)))))

型が合わずにコンパイルエラーになってしまいました。よくよく考えると、変数として扱いたいのは Inc(2) そのものではなく、Inc(2) が生成する各要素です。

イテレータの要素を変数として扱う構文などもちろんありません。ここがGoでできる限界でしょうか...？

変数をbindで書き換える

活路はHaskellのdo記法にありました。

do記法は、変数代入のように扱えるシンタックスシュガーです。

上記サイトより引用
import System.Environment 
 
main :: IO () 
main = do  
    args <- getArgs -- 代入のように見える 
    case args of 
        []   -> putStrLn "empty!!" 
        x:_  -> putStrLn x
    putStrLn "END"

変数のような値（上記の args）は、実態としては bind 関数の引数に渡された関数の仮引数となります。

上記サイトより引用
import System.Environment 
 
main :: IO () 
main = getArgs >>= 
           \args -> (case args of 
                       []   -> putStrLn "empty!!" 
                       x:_  -> putStrLn x) >> 
               putStrLn "END"

また、args は取り出された中身の型となる3（イテレータでいうと要素の型）ので、要件にもあっています。

イテレータを使いまわせるようにする

ところで、bind を実装する際1点問題があります。イテレータを複数個所で使いまわすとそれぞれで要素が消費されてしまう ため、正しく計算できません。

解決するには、使用箇所ごとにイテレータをコピーする必要があります。そこで、「イテレータを生成する関数」を引数に受け取り都度生成できるようにします。

シグネチャが複雑なので、以下 (Gen) とします4。

type Gen[V any] = func() iter.Seq[V]

（先に紹介した Inc, Range, Not, Mul も、実際にはイテレータを生成する関数を返すように実装しています）

これをふまえると、 Bind は以下のように実装できます。

func Bind[V, W any](gen Gen[V], f func(V) Gen[W]) Gen[W] {
	return func() iter.Seq[W] {
		return func(yield func(W) bool) {
			seq := gen()

			for vVal := range seq {
				// 要素に関数を適用し、返ってきたイテレータをループ
				wGen := f(vVal)
				wSeq := wGen()

				for wVal := range wSeq {
					if !yield(wVal) {
						return
					}
				}
			}
		}
	}
}
使用例
Bind(Range(1, 5, 1), func(i int) Gen[int] {
	return Add(Const(i), Const(i))
}) // [2, 4, 6, 8]

補足

「Bind という名前は適切なのか」、「イテレータに使用してよいのか」という疑問が湧いてくる方もいるかと思います。
少なくとも、モジュールで用意されている func(V) Gen[W] 型の関数の範囲ではモナド則を満たしています5。

var x: V, func f(V) Gen[W], var m: Gen[V] に対して以下を満たす 6：

  1. 左単位元結合： Bind(Const(x), f) == f(x)
  2. 右単位元結合：Bind(m, const) == m
  3. 結合律：Bind(Bind(m, f), g) == Bind(m, func(x int) Gen[int] { return Bind(f(x), g) })

先頭要素のみ切り取る

イテレータは要素を無限に生成しますが、プログラムが終わらないと使いづらいこともあるでしょう。
最後に、先頭n個のみ取得する関数も作っておきます。

func Head[V any](gen Gen[V], n int) Gen[V] {
	return func() iter.Seq[V] {
		return func(yield func(V) bool) {
			seq := gen()
			next, stop := iter.Pull(seq)
			defer stop()
			for _ = range n {
				v, ok := next()
				if !ok {
					return
				}
				if !yield(v) {
					return
				}
			}
		}
	}
}

Head(Inc(1), 10) // 1 2 3 4 5 6 7 8 9 10

これで素数を求めるイテレータの準備が整いました。

（Where と All の実装は割愛しましたが、興味のある方は実装をご覧ください）

おわりに

以上、イテレータを濫用するためのモジュールの紹介でした。みなさんも、1.23リリースに備えてイテレータ で遊んで を試してみてはいかがでしょうか？

  1. 今回再現したのはジェネレータの機能のみです。ゴール指向評価（計算が失敗する（=結果がfalseになる）とループを打ち切る）は採用していません。 ↩

  2. もちろん FromSlice を使用しても可能ですが、よく使う処理なので別関数にしました。 ↩

  3. ふわっとした書き方ですみません。モナドの話はあとで出てきます。 ↩

  4. Go1.23時点ではジェネリクスの型エイリアスはexperimentalのため、 GOEXPERIMENT=aliastypeparams GODEBUG=gotypesalias=1 の指定が必要です。 ↩

  5. 副作用がなければおそらくモナドになると思いますが（反例が思いつかない）、証明はしていません。 ↩

  6. 関数としては等価ですが、上記を == 演算子で比較することはできません(Goでは関数は nil としか比較できないため)。 ↩

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0