[Nim] 程式設計教學：函數式程式設計 (Functional Programming)

Nim 官方文件僅有簡略地提到 Nim 支援函數式程式，但沒有強調相關概念，範例也相對零散。本文整理一些常見的函數式程式，供讀者參考。如果覺得函數式程式較難，也可用等效的指令式程式代替；不過，適當地使用函數式程式，可使程式碼更簡短。

第一級物件

程式語言支援函數式程式的前提，在於該語言可將函式視為第一級物件 (first-class object)，即函式可做為值 (value)，像是做為另一個函式的參數或回傳值。

在以下例子中，我們將一個匿名程序 (anonymous procedure) 傳入 filter 程序中，做為過濾序列的條件：

import sequtils

let arr = @[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
let even = arr.filter(proc (n: int): bool = n mod 2 == 0)

assert(even == @[2, 4, 6, 8, 10])

也可以用稍微簡略的 do 來撰寫匿名函式：

import sequtils

let arr = @[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
let even = arr.filter do (n: int) -> bool: n mod 2 == 0

assert(even == @[2, 4, 6, 8, 10])

閉包

閉包 (closure) 是帶有狀態的 (stateful) 函式。如以下範例：

proc number(): proc =
    var i = -1

    return proc (): int =
        i += 1
        i

var f = number()

# The state of f changes with each call.
assert(f() == 0)
assert(f() == 1)
assert(f() == 2)

以下例子用閉包生成費伯那西數：

proc fib(): proc =
  var a = 0
  var b = 1

  return proc (): int =
    var n = a

    let c = a + b
    a = b
    b = c

    n

var f = fib()

let arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
for n in arr:
    assert(f() == n)

以下例子用閉包生成質數：

import math

proc prime(): proc =
    var n = 1
    var prime: int

    return proc(): int =
        while true:
            n += 1
            var isPrime = true

            for i in countup(2, int(sqrt(float(n)))):
                if n mod i == 0:
                    isPrime = false
                    break

            if isPrime:
                prime = n
                break

        prime

var p = prime()

let arr = [2, 3, 5, 7, 11, 13, 17, 19, 23]
for n in arr:
    assert(p() == n)

在下列範例中，我們用 table 做為簡易的快取 (cache)，再將其存在閉包中：

import tables

proc fib(): proc =
    var cache = {0: 0, 1: 1}.toTable

    proc f(n: int): int =
        if cache.hasKey(n):
            return cache[n]

        var o = f(n - 1) + f(n - 2)
        cache[n] = o

        o

    f

var f = fib()
echo f(10)

模擬介面

我們在先前討論多型的章節中，有用 tuple 模擬介面的實例，讀者可自行回頭閱讀。

迭代器

迭代器 (iterator) 提供公開介面，讓走訪元素的過程變得簡單，迭代器的特色在於使用者不需知道迭代器內部的實作；迭代器常用於資料結構 (data structures) 或容器 (collections)。Nim 提供 iterator 和 yield 來製做迭代器；iterator 區塊類似於 proc 區塊，但可搭配 yield 敘述使用；當程式運行到 yield 敘述時，程式會暫時跳出迭代器，經過一輪迭代後，再跳回 iterator 區塊，直到無法繼續迭代時，結束迴圈。

以下範例用迭代器撰寫費伯那西數列：

# fib starts from 0
iterator fib(i: Natural): Natural =
    var a = 0
    var b = 1

    for c in countup(0, i - 1):
        yield a

        let o = a + b
        a = b
        b = o

let arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
var i = 0
for n in fib(10):
    assert(n == arr[i])
    i += 1

以下範例用迭代器生成質數數列：

import math

# prime lasts till max value.
iterator prime(max: Natural): Natural =
    var p = 1

    while p <= max:
        p += 1
        var isPrime = true

        for n in countup(2, int(sqrt(float(p)))):
            if p mod n == 0:
                isPrime = false
                break

        if isPrime:
            yield p

let arr = [2, 3, 5, 7, 11, 13, 17, 19, 23]
var i = 0
for p in prime(25):
    assert(p == arr[i])
    i += 1

迭代器可和閉包結合，用來儲存迭代器的狀態。如下例：

proc countTo(n: int): iterator(): int =
  return iterator(): int =
    var i = 0
    while i <= n:
      yield i
      i += 1

# Iterate with `for`
var cTo10 = countTo(10)
for n in cTo10():
    echo n

# Iterate with `while`; stop with `finished`
cTo10 = countTo(10)
while true:
    let next = cTo10()

    if finished(cTo10):
        break

    echo next