Iterator

Di Go, keyword yang digunakan untuk mengiterasi struktur data tertentu adalah for range. Bab sebelumnya telah memperkenalkan beberapa aplikasinya, keyword ini hanya dapat bekerja pada beberapa struktur data built-in bahasa

Array
Slice
String
Map
Chan
Nilai integer

Penggunaannya sangat tidak fleksibel, tidak ada extensibility, hampir tidak mendukung untuk tipe custom. Namun setelah update versi go1.23, keyword for range mendukung range over func, sehingga membuat custom iterator menjadi mungkin.

Mengenal

Berikut melalui contoh untuk初步 mengenal iterator, tidak tahu apakah masih ingat contoh closure menghitung deret Fibonacci yang dibahas di bagian fungsi, implementasinya sebagai berikut

func Fibonacci(n int) func() (int, bool) {
  a, b, c := 1, 1, 2
  i := 0
  return func() (int, bool) {
    if i >= n {
      return 0, false
    } else if i < 2 {
      f := i
      i++
      return f, true
    }

    a, b = b, c
    c = a + b
    i++

    return a, true
  }
}

Kita dapat mengubahnya menjadi iterator, sebagai berikut, dapat dilihat jumlah kode berkurang sedikit

func Fibonacci(n int) func(yield func(int) bool) {
  a, b, c := 0, 1, 1
  return func(yield func(int) bool) {
    for range n {
      if !yield(a) {
        return
      }
      a, b = b, c
      c = a + b
    }
  }
}

Iterator Go bergaya range over func, kita dapat langsung menggunakan keyword for range untuk menggunakannya, penggunaannya juga lebih nyaman dibanding sebelumnya

func main() {
    n := 8
  for f := range Fibonacci(n) {
    fmt.Println(f)
  }
}

Output sebagai berikut

Seperti ditunjukkan di atas, iterator adalah fungsi closure, ia menerima callback function sebagai parameter, Anda bahkan dapat melihat kata seperti yield di dalamnya, orang yang pernah menulis python seharusnya sangat familiar, ini mirip dengan generator di python. Iterator Go tidak menambahkan keyword atau fitur syntax baru, di contoh di atas yield juga hanya callback function, bukan keyword,官方 mengambil nama ini untuk memudahkan pemahaman.

Push Iterator

Tentang definisi iterator, kita dapat menemukan penjelasan berikut di library iter

An iterator is a function that passes successive elements of a sequence to a callback function, conventionally named yield.
Iterator adalah fungsi yang meneruskan elemen-elemen sequence secara berurutan ke callback function, secara konvensional bernama yield.

Dari sini kita dapat memastikan satu hal, iterator adalah fungsi, ia menerima callback function sebagai parameter, selama proses iterasi akan meneruskan elemen-elemen sequence secara berurutan ke callback function yield. Di contoh sebelumnya kita menggunakan iterator seperti berikut

for f := range Fibonacci(n) {
    fmt.Println(f)
}

Menurut definisi官方, penggunaan iterator Backward di atas setara dengan kode berikut

Fibonacci(n)(func(f int) bool {
    fmt.Println(f)
    return true
})

Body loop adalah callback function yield iterator, saat function mengembalikan true iterator akan melanjutkan iterasi, jika tidak akan berhenti.

Selain itu, library standar iter juga mendefinisikan tipe iterator iter.Seq, tipenya adalah fungsi.

type Seq[V any] func(yield func(V) bool)

type Seq2[K, V any] func(yield func(K, V) bool)

Callback function iter.Seq hanya menerima satu parameter, maka saat iterasi for range hanya memiliki satu nilai return, sebagai berikut

for v := range iter {
  // body
}

Callback function iter.Seq2 menerima dua parameter, maka saat iterasi for range memiliki dua nilai return, sebagai berikut

for k, v := range iter {
  // body
}

Meskipun library standar tidak mendefinisikan Seq dengan 0 parameter, tetapi ini sepenuhnya diizinkan, ini setara dengan

func(yield func() bool)

Penggunaannya sebagai berikut

for range iter {
  // body
}

Jumlah parameter callback function hanya boleh 0 hingga 2, lebih banyak tidak akan lolos kompilasi.

Singkatnya, body loop di for range adalah callback function yield di iterator, berapa nilai yang dikembalikan for range,相应的 yeild function memiliki berapa parameter input, setiap iterasi, iterator akan memanggil function yield, yaitu mengeksekusi kode di body loop, secara aktif meneruskan elemen-elemen sequence ke function yield, iterator yang secara aktif meneruskan elemen ini umumnya kita sebut pushing iterator, contoh tipikal adalah foreach di bahasa lain, misalnya js

javascript

let arr = [1, 2, 3, 4, 5];
arr
  .filter((e) => e % 2 === 0)
  .forEach((e) => {
    console.log(e);
  });

Bentuk representasi di Go adalah elemen yang diiterasi dikembalikan oleh range.

for index, value := range iterator() {
  fmt.Println(index, value)
}

Di beberapa bahasa (seperti Java) ini memiliki nama lain: stream processing.

Karena kode di body loop adalah sebagai callback function diteruskan ke iterator, dan sangat mungkin adalah closure function, Go perlu membuat closure function saat mengeksekusi defer, return, break, goto dan keyword lainnya berperilaku seperti segmen kode loop biasa, pertimbangkan beberapa situasi berikut.

Misalnya return di loop iterator, lalu bagaimana cara menangani return ini di callback function yield?

for index, value := range iterator() {
    if value > 10 {
        return
  }
  fmt.Println(index, value)
}

Tidak mungkin langsung return di callback function, melakukan ini hanya akan membuat iterasi berhenti, tidak mencapai efek return

iterator()(func(index int, value int) bool {
  if value > 10 {
    return false
  }
  fmt.Println(index, value)
})

Lagi misalnya menggunakan defer di loop iterator

for index, value := range iterator() {
    defer fmt.Println(index, value)
}

Juga tidak bisa langsung menggunakan defer di callback function, karena melakukan ini saat callback function selesai akan langsung delayed call

iterator()(func(index int, value int) bool {
  defer fmt.Println(index, value)
})

Beberapa keyword lainnya break, continue, goto juga serupa, untungnya situasi-situasi ini sudah ditangani oleh Go, kita hanya perlu menggunakannya saja, dapat暂时 tidak perlu memperhatikan ini, jika tertarik dapat自行浏览 source code di rangefunc/rewrite.go.

Pull Iterator

Pushing iterator dikontrol logika iterasi oleh iterator, user pasif mendapatkan elemen, sebaliknya pulling iterator dikontrol logika iterasi oleh user, secara aktif mendapatkan elemen sequence. Umumnya, pulling iterator akan memiliki fungsi spesifik seperti next(), stop() untuk mengontrol mulai atau berakhir iterasi, ini dapat berupa closure atau struct.

scanner := bufio.NewScanner(file)
for scanner.Scan() {
    line, err := scanner.Text(), scanner.Err()
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Println(line)
}

Seperti ditunjukkan di atas, Scanner mendapatkan baris teks berikutnya di file melalui metode Text(), melalui metode Scan() untuk表示 apakah iterasi berakhir, ini juga salah satu mode pulling iterator. Scanner menggunakan struct untuk merekam status, sedangkan pulling iterator yang didefinisikan di library iter menggunakan closure untuk merekam status, kita dapat mengkonversi pushing iterator standar menjadi pulling iterator melalui fungsi iter.Pull atau iter.Pull2, perbedaan iter.Pull dan iter.Pull2 adalah nilai return yang kedua memiliki dua, signature sebagai berikut

func Pull[V any](seq Seq[V]) (next func() (V, bool), stop func())

func Pull2[K, V any](seq Seq2[K, V]) (next func() (K, V, bool), stop func())

Keduanya menerima iterator sebagai parameter, lalu mengembalikan dua fungsi next() dan stop(), digunakan untuk mengontrol lanjutan dan penghentian iterasi.

func next() (V, bool)

func stop()

next akan mengembalikan elemen yang diiterasi, dan nilai boolean yang表示 apakah nilai saat ini valid, saat iterasi berakhir function next akan mengembalikan nilai nol elemen dan false. Function stop akan mengakhiri proses iterasi, saat caller tidak lagi menggunakan iterator, harus menggunakan function stop untuk mengakhiri iterasi. Sekadar informasi, memanggil function next iterator yang sama di beberapa goroutine adalah praktik yang salah, karena ini bukan concurrent safe.

Berikut melalui contoh untuk mendemonstrasikan, fungsinya adalah mengubah iterator Fibonacci sebelumnya menjadi pulling iterator, sebagai berikut

func main() {
  n := 10
  next, stop := iter.Pull(Fibonacci(n))
  defer stop()
  for {
    fibn, ok := next()
    if !ok {
      break
    }
    fmt.Println(fibn)
  }
}

Output

Dengan demikian kita dapat mengontrol logika iterasi secara manual melalui fungsi next dan stop. Anda mungkin merasa ini berlebihan, jika ingin melakukan ini mengapa tidak langsung menggunakan versi closure awal saja, sama juga dapat mengontrol iterasi sendiri, penggunaan closure adalah seperti ini

func main() {
  fib := Fibonacci(10)
    for {
        n, ok := fib()
        if !ok {
            break
        }
        fmt.Prinlnt(n)
    }
}

Proses konversi: closure → iterator → pulling iterator, penggunaan closure dan pulling iterator hampir sama, ide mereka sama, yang kedua akan karena berbagai pemrosesan menyebabkan penurunan performa. Jujur melakukan ini memang berlebihan, scenario aplikasinya memang tidak banyak, tetapi iter.pull adalah untuk iter.Seq yang ada, yaitu untuk mengkonversi pushing iterator menjadi pulling iterator yang ada, jika Anda hanya ingin pulling iterator, masih khusus mengimplementasikan pushing iterator untuk melakukan konversi, untuk melakukan ini lebih baik pertimbangkan kompleksitas dan performa implementasi sendiri, seperti contoh deret Fibonacci ini, berputar-putar kembali ke titik awal, satu-satunya keuntungan mungkin sesuai dengan spesifikasi iterator官方.

Penanganan Error

Bagaimana jika terjadi error saat iterasi? Kita dapat meneruskannya ke function yield untuk dikembalikan oleh for range, biarkan caller yang menangani, seperti contoh iterator baris berikut

func ScanLines(reader io.Reader) iter.Seq2[string, error] {
  scanner := bufio.NewScanner(reader)
  return func(yield func(string, error) bool) {
    for scanner.Scan() {
      if !yield(scanner.Text(), scanner.Err()) {
        return
      }
    }
  }
}

TIP

Perlu dicatat, iterator ScanLines adalah one-time use, setelah file ditutup tidak dapat digunakan lagi.

Dapat dilihat nilai return keduanya adalah tipe error, penggunaannya sebagai berikut

for line, err := range ScanLines(file) {
    if err != nil {
        fmt.Println(err)
        break
    }
    fmt.Println(line)
}

Penanganan seperti ini tidak berbeda dengan penanganan error biasa, pulling iterator juga sama

next, stop := iter.Pull2(ScanLines(file))
defer stop()
for {
    line, err, ok := next()
    if err != nil {
        fmt.Println(err)
        break
    } else if !ok {
        break
    }
    fmt.Println(line)
}

Jika terjadi panic, sama seperti biasa menggunakan recovery saja.

defer func() {
    if err := recover(); err != nil {
        fmt.Println("panic:", err)
        os.Exit(1)
    }
}()

for line, err := range ScanLines(file) {
    if err != nil {
        fmt.Println(err)
        break
    }
    fmt.Println(line)
}

Pulling iterator tetap sama, tidak akan didemonstrasikan lagi di sini.

Library Standar

Banyak library standar juga mendukung iterator, yang paling umum digunakan adalah library standar slices dan maps, berikut memperkenalkan beberapa fungsi yang praktis.

slices.All

func All[Slice ~[]E, E any](s Slice) iter.Seq2[int, E]

slices.All akan mengkonversi slice menjadi iterator slice

func main() {
  s := []int{1, 2, 3, 4, 5}
  for i, n := range slices.All(s) {
    fmt.Println(i, n)
  }
}

Output

slices.Values

func Values[Slice ~[]E, E any](s Slice) iter.Seq[E]

slices.Values akan mengkonversi slice menjadi iterator slice, tetapi tanpa index

func main() {
  s := []int{1, 2, 3, 4, 5}
  for n := range slices.Values(s) {
    fmt.Println(n)
  }
}

Output

slices.Chunk

func Chunk[Slice ~[]E, E any](s Slice, n int) iter.Seq[Slice]

Fungsi slices.Chunk akan mengembalikan iterator, iterator ini akan meneruskan slice dengan n elemen ke caller

func main() {
  s := []int{1, 2, 3, 4, 5}
  for chunk := range slices.Chunk(s, 2) {
    fmt.Println(chunk)
  }
}

Output

[1 2]
[3 4]
[5]

slices.Collect

func Collect[E any](seq iter.Seq[E]) []E

Fungsi slices.Collect akan mengumpulkan iterator slice menjadi slice

func main() {
  s := []int{1, 2, 3, 4, 5}
  s2 := slices.Collect(slices.Values(s))
  fmt.Println(s2)
}

Output

[1 2 3 4 5]

maps.Keys

func Keys[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[K]

maps.Keys akan mengembalikan iterator yang mengiterasi semua key map,配合 slices.Collect dapat langsung dikumpulkan menjadi slice.

func main() {
  m := map[string]int{"one": 1, "two": 2, "three": 3}
  keys := slices.Collect(maps.Keys(m))
  fmt.Println(keys)
}

Output

[three one two]

Karena map tidak berurutan, output juga tidak tetap

maps.Values

func Values[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[V]

maps.Values akan mengembalikan iterator yang mengiterasi semua value map,配合 slices.Collect dapat langsung dikumpulkan menjadi slice.

func main() {
  m := map[string]int{"one": 1, "two": 2, "three": 3}
  keys := slices.Collect(maps.Values(m))
  fmt.Println(keys)
}

Output

[3 1 2]

Karena map tidak berurutan, output juga tidak tetap

maps.All

func All[Map ~map[K]V, K comparable, V any](m Map) iter.Seq2[K, V]

maps.All dapat mengkonversi map menjadi iterator map

func main() {
  m := map[string]int{"one": 1, "two": 2, "three": 3}
  for k, v := range maps.All(m) {
    fmt.Println(k, v)
  }
}

Umumnya tidak langsung menggunakan seperti ini, biasanya配合 fungsi stream processing lainnya.

maps.Collect

func Collect[K comparable, V any](seq iter.Seq2[K, V]) map[K]V

maps.Collect dapat mengkonversi iterator map menjadi map

func main() {
  m := map[string]int{"one": 1, "two": 2, "three": 3}
  m2 := maps.Collect(maps.All(m))
  fmt.Println(m2)
}

Fungsi collect umum digunakan sebagai fungsi terminal stream processing.

Chain Call

Melalui fungsi yang disediakan library standar di atas, kita dapat mengombinasikannya untuk memproses stream data, misalnya mengurutkan stream data, sebagai berikut

sortedSlices := slices.Sorted(slices.Values(s))

Iterator Go menggunakan closure, hanya dapat nested function call seperti ini, sendiri tidak dapat chain call, setelah call chain menjadi panjang readability akan sangat buruk, tetapi kita dapat sendiri melalui struct untuk merekam iterator, sehingga dapat mengimplementasikan chain call.

Demo

Demo chain call sederhana sebagai berikut, ini berisi fungsi yang umum digunakan seperti Filter, Map, Find, Some dll.

package iterx

import (
  "iter"
  "slices"
)

type SliceSeq[E any] struct {
  seq iter.Seq2[int, E]
}

func (s SliceSeq[E]) All() iter.Seq2[int, E] {
  return s.seq
}

func (s SliceSeq[E]) Filter(filter func(int, E) bool) SliceSeq[E] {
  return SliceSeq[E]{
    seq: func(yield func(int, E) bool) {
      // Reorganisasi index
      i := 0
      for k, v := range s.seq {
        if filter(k, v) {
          if !yield(i, v) {
            return
          }
          i++
        }
      }
    },
  }
}

func (s SliceSeq[E]) Map(mapFn func(E) E) SliceSeq[E] {
  return SliceSeq[E]{
    seq: func(yield func(int, E) bool) {
      for k, v := range s.seq {
        if !yield(k, mapFn(v)) {
          return
        }
      }
    },
  }
}

func (s SliceSeq[E]) Fill(fill E) SliceSeq[E] {
  return SliceSeq[E]{
    seq: func(yield func(int, E) bool) {
      for i, _ := range s.seq {
        if !yield(i, fill) {
          return
        }
      }
    },
  }
}

func (s SliceSeq[E]) Find(equal func(int, E) bool) (_ E) {
  for i, v := range s.seq {
    if equal(i, v) {
      return v
    }
  }
  return
}

func (s SliceSeq[E]) Some(match func(int, E) bool) bool {
  for i, v := range s.seq {
    if match(i, v) {
      return true
    }
  }
  return false
}

func (s SliceSeq[E]) Every(match func(int, E) bool) bool {
  for i, v := range s.seq {
    if !match(i, v) {
      return false
    }
  }
  return true
}

func (s SliceSeq[E]) Collect() []E {
  var res []E
  for _, v := range s.seq {
    res = append(res, v)
  }
  return res
}

func (s SliceSeq[E]) Sort(cmp func(x, y E) int) []E {
  collect := s.Collect()
  slices.SortFunc(collect, cmp)
  return collect
}

func (s SliceSeq[E]) SortStable(cmp func(x, y E) int) []E {
  collect := s.Collect()
  slices.SortStableFunc(collect, cmp)
  return collect
}

func Slice[S ~[]E, E any](s S) SliceSeq[E] {
  return SliceSeq[E]{seq: slices.All(s)}
}

Lalu kita dapat memproses melalui chain call, lihat beberapa contoh penggunaan.

Memproses Nilai Elemen

func main() {
  s := []string{"apple", "banana", "cherry"}
  all := iterx.Slice(s).Map(strings.ToUpper).All()
  for i, v := range all {
    fmt.Printf("index: %d, value: %s\n", i, v)
  }
}

Output

index: 0, value: APPLE
index: 1, value: BANANA
index: 2, value: CHERRY

Mencari Nilai Spesifik Tertentu

func main() {
  s := []int{1, 2, 3, 4, 5}
  result := iterx.Slice(s).Find(func(i int, e int) bool {
    return e == 3
  })
  fmt.Println(result)
}

Output

Mengisi Slice

func main() {
  s := []int{1, 2, 3, 4, 5}
  result := iterx.Slice(s).Fill(6).Collect()
  fmt.Println(result)
}

Output

[6 6 6 6 6]

Filter Elemen

func main() {
  s := []int{1, 2, 3, 4, 5}
  filter := iterx.Slice(s).Filter(func(i int, e int) bool {
    return e%2 == 0
  }).All()
  for i, v := range filter {
    fmt.Printf("Index: %d, Value: %d\n", i, v)
  }
}

Output

Index: 0, Value: 2
Index: 1, Value: 4

Sayang Go saat ini belum mendukung anonymous function shorthand, seperti arrow function di js, rust, java, jika tidak chain call dapat lebih ringkas dan elegan.

Performa

Karena Go melakukan banyak pemrosesan untuk iterator, performanya tentu tidak sebaik loop for range native, kita ambil loop slice sederhana untuk menguji perbedaan performa mereka, dibagi beberapa berikut

Loop for native
Pushing iterator
Pulling iterator

Kode tes sebagai berikut, panjang slice tes adalah 1000.

package main

import (
  "iter"
  "slices"
  "testing"
)

var s []int

const n = 10000

func init() {
  for i := range n {
    s = append(s, i)
  }
}

func testNaiveFor(s []int) {
  for i, n := range s {
    _ = i
    _ = n
  }
}

func testPushing(s []int) {
  for i, n := range slices.All(s) {
    _ = i
    _ = n
  }
}

func testPulling(s []int) {
  next, stop := iter.Pull2(slices.All(s))
  for {
    i, n, ok := next()
    if !ok {
      stop()
      return
    }
    _ = i
    _ = n
  }
}

func BenchmarkNaive_10000(b *testing.B) {
  for range b.N {
    testNaiveFor(s)
  }
}

func BenchmarkPushing_10000(b *testing.B) {
  for range b.N {
    testPushing(s)
  }
}

func BenchmarkPulling_10000(b *testing.B) {
  for range b.N {
    testPulling(s)
  }
}

Hasil tes sebagai berikut

goos: windows
goarch: amd64
pkg: golearn
cpu: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
BenchmarkNaive_10000
BenchmarkNaive_10000-16           492658              2398 ns/op               0 B/op          0 allocs/op
BenchmarkPushing_10000
BenchmarkPushing_10000-16         315889              3707 ns/op               0 B/op          0 allocs/op
BenchmarkPulling_10000
BenchmarkPulling_10000-16           2016            574509 ns/op             440 B/op         14 allocs/op
PASS
ok      golearn 4.029s

Dari hasil kita dapat melihat pushing iterator tidak terlalu berbeda dengan for range native, tetapi pulling iterator hampir dua order of magnitude lebih lambat dibanding dua sebelumnya, saat menggunakan各位 dapat mempertimbangkan sesuai situasi aktual.

Ringkasan

Sama seperti situasi generik, iterator Go juga kontroversial, sebagian orang berpendapat iterator memperkenalkan terlalu banyak kompleksitas, melanggar filosofi kesederhanaan Go, seperti kode closure iterator ini setelah banyak, debugging sepertinya agak sulit, reading lebih menyebalkan.

Anda dapat melihat banyak diskusi intens tentang iterator di berbagai tempat

Why People are Angry over Go 1.23 Iterators, evaluasi iterator dari seorang kakak luar negeri, layak dibaca
golang/go · Discussion #56413, diskusi komunitas yang dimulai rsc, banyak orang mengemukakan pendapat mereka

Memandang iterator Go secara rasional, ini memang membuat penulisan kode lebih nyaman, terutama saat menangani tipe slice, tetapi sekaligus juga memperkenalkan sedikit kompleksitas, readability kode bagian iterator akan menurun, namun secara keseluruhan, saya pikir ini memang fitur yang praktis.

Iterator ​

Mengenal ​

Push Iterator ​

Pull Iterator ​

Penanganan Error ​

Library Standar ​

Chain Call ​

Demo ​

Performa ​

Ringkasan ​

Iterator

Mengenal

Push Iterator

Pull Iterator

Penanganan Error

Library Standar

Chain Call

Demo

Performa

Ringkasan