Iterator

Trong Go từ khóa dùng để lặp qua các cấu trúc dữ liệu cụ thể là for range trong các chương trước đã giới thiệu một số ứng dụng của nó nó chỉ có thể áp dụng cho một vài cấu trúc dữ liệu built-in của ngôn ngữ

• Mảng
• Slice
• Chuỗi
• Map
• Chan
• Giá trị số nguyên

Như vậy việc sử dụng rất không linh hoạt không có khả năng mở rộng hầu như không hỗ trợ cho loại tùy chỉnh nhưng may mắn sau khi cập nhật phiên bản go1.23 từ khóa for range hỗ trợ range over func như vậy iterator tùy chỉnh trở thành khả thi.

Nhận biết

Dưới đây thông qua một ví dụ để sơ bộ nhận biết iterator không biết các bạn còn nhớ ví dụ dùng closure để tính dãy Fibonacci đã giới thiệu trong phần hàm không mã thực hiện của nó như sau

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
  }
}

Chúng ta có thể cải tạo nó thành iterator như sau có thể thấy lượng mã đã giảm bớt một chút

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 của Go là phong cách range over func chúng ta có thể trực tiếp sử dụng từ khóa for range để sử dụng việc sử dụng cũng tiện lợi hơn so với trước

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

Kết quả xuất như sau

0
1
1
2
3
5
8
13

Như đã trình bày ở trên iterator là một closure function nó nhận một callback function làm tham số bạn thậm chí có thể thấy những từ như yield trong đó những người đã viết python đều rất quen thuộc nó tương tự như generator trong python. Iterator của Go không thêm bất kỳ từ khóa hay tính năng cú pháp nào trong ví dụ trên yield cũng chỉ là một callback function nó không phải là từ khóa Go đặt tên như vậy là để thuận tiện cho việc hiểu.

Iterator kiểu đẩy

Về định nghĩa của iterator chúng ta có thể tìm thấy giải thích sau trong thư viện iter

An iterator is a function that passes successive elements of a sequence to a callback function, conventionally named yield.

Iterator là một hàm truyền các phần tử liên tiếp của một chuỗi cho một callback function thường được gọi là yield.

Chúng ta có thể xác định rõ một điều iterator là một hàm nó nhận một callback function làm tham số trong quá trình lặp sẽ truyền các phần tử của chuỗi cho callback function yield từng cái một. Trong ví dụ trước chúng ta sử dụng iterator theo cách sau

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

Theo định nghĩa chính thức việc sử dụng iterator Backward trong ví dụ trên tương đương với đoạn mã sau

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

Body của vòng lặp là callback function yield của iterator khi hàm trả về true iterator sẽ tiếp tục lặp ngược lại sẽ dừng.

Ngoài ra thư viện chuẩn iter cũng định nghĩa loại iterator iter.Seq loại của nó chính là hàm.

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

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

Callback function của iter.Seq chỉ nhận một tham số nên khi lặp for range chỉ có một giá trị trả về như sau

for v := range iter {
  // body
}

Callback function của iter.Seq2 nhận hai tham số nên khi lặp for range có hai giá trị trả về như sau

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

Mặc dù thư viện chuẩn không định nghĩa Seq với 0 tham số nhưng điều này hoàn toàn được phép nó tương đương với

func(yield func() bool)

Sử dụng như sau

for range iter {
  // body
}

Số lượng tham số của callback function chỉ có thể từ 0 đến 2 nếu nhiều hơn sẽ không thể biên dịch thành công.

Nói một cách ngắn gọn body vòng lặp trong for range chính là callback function yield trong iterator for range trả về bao nhiêu giá trị thì hàm yield tương ứng có bấy nhiêu tham số đầu vào mỗi lần lặp iterator sẽ gọi hàm yield tức là thực hiện mã trong body vòng lặp chủ động truyền các phần tử trong chuỗi cho hàm yield loại iterator chủ động truyền phần tử này chúng ta thường gọi là iterator kiểu đẩy (pushing iterator) ví dụ điển hình là foreach trong các ngôn ngữ khác như js

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

Biểu hiện trong Go là các phần tử được lặp trả về bởi range.

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

Trong một số ngôn ngữ (như Java) nó còn có một tên gọi khác xử lý luồng dữ liệu.

Vì mã trong body vòng lặp được truyền vào iterator dưới dạng callback function và rất có thể là một closure function Go cần để một closure function khi thực hiện các từ khóa như defer return break goto biểu hiện giống như một đoạn mã vòng lặp thông thường hãy suy nghĩ về vài tình huống sau.

Ví dụ như return trong vòng lặp iterator vậy trong callback function yield phải xử lý return này như thế nào?

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

Không thể trực tiếp return trong callback function làm như vậy chỉ khiến iterator dừng mà không đạt được hiệu quả return

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

Lại ví dụ như sử dụng defer trong vòng lặp iterator

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

Cũng không thể trực tiếp sử dụng defer trong callback function vì làm như vậy khi callback function kết thúc sẽ trực tiếp gọi trì hoãn

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

Một vài từ khóa khác như break continue goto cũng tương tự may mắn là những tình huống này Go đã xử lý giúp chúng ta chỉ cần sử dụng là được có thể tạm thời không cần quan tâm đến những điều này nếu quan tâm có thể tự duyệt mã nguồn trong rangefunc/rewrite.go.

Iterator kiểu kéo

Iterator kiểu đẩy (pushing iterator) là do iterator kiểm soát logic lặp người dùng bị động nhận phần tử ngược lại iterator kiểu kéo (pulling iterator) là do người dùng kiểm soát logic lặp chủ động lấy phần tử chuỗi. Nói chung iterator kiểu kéo đều có các hàm đặc biệt như next() stop() để kiểm soát bắt đầu hoặc kết thúc lặp nó có thể là một closure hoặc struct.

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

Như đã trình bày ở trên Scanner thông qua phương thức Text() để lấy dòng văn bản tiếp theo trong file thông qua phương thức Scan() để biểu thị lặp có kết thúc hay không đây cũng là một mô hình của iterator kiểu kéo. Scanner sử dụng struct để ghi lại trạng thái còn iterator kiểu kéo được định nghĩa trong thư viện iter sử dụng closure để ghi lại trạng thái chúng ta thông qua hàm iter.Pull hoặc iter.Pull2 có thể chuyển đổi một iterator kiểu đẩy tiêu chuẩn thành iterator kiểu kéo sự khác biệt giữa iter.Pull và iter.Pull2 là giá trị trả về của cái sau có hai cái ký hiệu như sau

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())

Cả hai đều nhận một iterator làm tham số sau đó trả về hai hàm next() và stop() dùng để kiểm soát tiếp tục và dừng lặp.

func next() (V, bool)

func stop()

next sẽ trả về phần tử được lặp và một giá trị boolean biểu thị giá trị hiện tại có hợp lệ hay không khi lặp kết thúc hàm next sẽ trả về giá trị zero của phần tử và false. Hàm stop sẽ kết thúc quá trình lặp khi người gọi không còn sử dụng iterator nữa phải sử dụng hàm stop để kết thúc lặp. Nhân tiện việc nhiều goroutine gọi hàm next của cùng một iterator là sai lầm vì nó không an toàn đồng thời.

Dưới đây thông qua một ví dụ để demo chức năng của nó là cải tạo iterator Fibonacci trước đó thành iterator kiểu kéo như sau

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

Kết quả xuất

0
1
1
2
3
5
8
13
21
34

Như vậy chúng ta có thể thông qua hàm next và stop để thủ công kiểm soát logic lặp. Bạn có thể cảm thấy việc làm này là thừa nếu muốn làm như vậy thì tại sao không trực tiếp sử dụng phiên bản closure ban đầu là được cả hai đều có thể tự kiểm soát lặp ý tưởng của chúng đều giống nhau cái sau còn vì các xử lý khác nhau mà dẫn đến拖累 hiệu suất. Thành thật mà nói việc làm này quả thực là thừa ứng dụng của nó quả thực không nhiều nhưng iter.pull là để tồn tại cho iter.Seq tức là để chuyển đổi iterator kiểu đẩy thành iterator kiểu kéo nếu bạn chỉ muốn có một iterator kiểu kéo còn chuyên môn vì thế mà thực hiện một iterator kiểu đẩy để chuyển đổi thì hãy cân nhắc độ phức tạp và hiệu suất của việc tự thực hiện giống như ví dụ dãy Fibonacci này đi một vòng lại trở về điểm xuất phát lợi ích duy nhất có lẽ là phù hợp với quy phạm iterator chính thức.

Xử lý lỗi

Khi lặp xảy ra lỗi thì làm sao? Chúng ta có thể truyền nó cho hàm yield để for range trả về để người gọi xử lý giống như ví dụ iterator lặp dòng này

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

Đáng chú ý iterator ScanLines chỉ sử dụng được một lần sau khi file đóng không thể sử dụng lại.

Có thể thấy giá trị trả về thứ hai của nó là loại error sử dụng như sau

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

Xử lý như vậy không khác gì xử lý lỗi thông thường iterator kiểu kéo cũng tương tự

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)
}

Nếu xảy ra panic giống như bình thường sử dụng recovery là được.

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)
}

Iterator kiểu kéo vẫn tương tự ở đây không demo nữa.

Thư viện chuẩn

Có nhiều thư viện chuẩn cũng hỗ trợ iterator thông dụng nhất là thư viện chuẩn slices và maps dưới đây giới thiệu một vài chức năng thực tế.

slices.All

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

slices.All sẽ chuyển đổi slice thành một iterator slice

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

Kết quả xuất

0 1
1 2
2 3
3 4
4 5

slices.Values

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

slices.Values sẽ chuyển đổi slice thành một iterator slice nhưng không có index

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

Kết quả xuất

1
2
3
4
5

slices.Chunk

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

Hàm slices.Chunk sẽ trả về một iterator iterator này sẽ đẩy slice cho người gọi với n phần tử làm một slice

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

Kết quả xuất

[1 2]
[3 4]
[5]

slices.Collect

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

Hàm slices.Collect sẽ thu thập iterator slice thành một slice

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

Kết quả xuất

[1 2 3 4 5]

maps.Keys

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

maps.Keys sẽ trả về một iterator lặp tất cả các key của map phối hợp với slices.Collect có thể trực tiếp thu thập thành một slice.

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

Kết quả xuất

[three one two]

Do map không có thứ tự nên kết quả xuất cũng không cố định

maps.Values

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

maps.Values sẽ trả về một iterator lặp tất cả các value của map phối hợp với slices.Collect có thể trực tiếp thu thập thành một slice.

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

Kết quả xuất

[3 1 2]

Do map không có thứ tự nên kết quả xuất cũng không cố định

maps.All

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

maps.All có thể chuyển đổi một map thành một 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)
  }
}

Nói chung không trực tiếp sử dụng như vậy đều拿来 phối hợp với các hàm xử lý luồng dữ liệu khác.

maps.Collect

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

maps.Collect có thể thu thập một iterator map thành một map

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

Hàm collect nói chung được sử dụng như hàm kết thúc của xử lý luồng dữ liệu.

Gọi chuỗi

Thông qua các hàm do thư viện chuẩn cung cấp ở trên chúng ta có thể kết hợp chúng để xử lý luồng dữ liệu ví dụ như sắp xếp luồng dữ liệu như sau

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

Iterator của Go sử dụng closure chỉ có thể lồng hàm gọi như vậy bản thân không thể gọi chuỗi sau khi chuỗi gọi dài khả năng đọc sẽ rất kém nhưng chúng ta có thể tự thông qua struct để ghi lại iterator là có thể thực hiện gọi chuỗi.

demo

Một demo gọi chuỗi đơn giản như sau nó bao gồm các chức năng thông dụng như Filter Map Find Some v.v.

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) {
      // Tái tổ chức 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)}
}

Sau đó chúng ta có thể thông qua gọi chuỗi để xử lý xem vài ví dụ sử dụng.

Xử lý giá trị phần tử

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)
  }
}

Kết quả xuất

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

Tìm một giá trị chỉ định

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)
}

Kết quả xuất

3

Điền slice

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

Kết quả xuất

[6 6 6 6 6]

Lọc phần tử

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)
  }
}

Kết quả xuất

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

Đáng tiếc là Go hiện tại chưa hỗ trợ closure viết tắt giống như hàm mũi tên trong js rust java nếu không gọi chuỗi còn có thể ngắn gọn và tao nhã hơn.

Hiệu suất

Vì Go đã xử lý nhiều cho iterator hiệu suất của nó chắc chắn không bằng vòng lặp for range nguyên sinh chúng ta lấy một ví dụ duyệt slice đơn giản nhất để kiểm tra sự khác biệt hiệu suất của chúng chia thành mấy loại sau

• Vòng lặp for nguyên sinh
• Iterator kiểu đẩy
• Iterator kiểu kéo

Mã kiểm tra như sau kiểm tra độ dài slice là 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)
  }
}

Kết quả kiểm tra như sau

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

Thông qua kết quả chúng ta có thể thấy iterator kiểu đẩy và vòng lặp for range nguyên sinh chênh lệch không đặc biệt lớn nhưng iterator kiểu kéo chậm hơn gần hai bậc độ lớn so với hai cái trước khi sử dụng các bạn có thể cân nhắc dựa trên tình hình thực tế của mình.

Tóm tắt

Giống như trường hợp của generic iterator của Go cũng gặp nhiều tranh cãi quan điểm của một số người là iterator đã đưa vào quá nhiều độ phức tạp vi phạm triết lý đơn giản của Go giống như mã closure của iterator này nhiều hơn sau này e rằng việc debug cũng có chút khó khăn việc đọc sẽ càng khó chịu hơn.

Bạn có thể thấy ở nhiều nơi về các cuộc thảo luận sôi nổi về iterator

• Why People are Angry over Go 1.23 Iterators đánh giá của một anh trai nước ngoài về iterator đáng xem
• golang/go · Discussion #56413 thảo luận cộng đồng do rsc khởi xướng có nhiều người đã phát biểu quan điểm của mình

Nhìn nhận iterator của Go một cách lý tính nó quả thực khiến việc viết mã trở nên tiện lợi hơn đặc biệt là khi xử lý loại slice nhưng đồng thời cũng đưa vào một chút độ phức tạp khả năng đọc của phần mã iterator sẽ giảm xuống nhưng nhìn tổng thể tôi cho rằng đây quả thực là một tính năng thực tế.