Nim 程式設計教學:函數式程式設計 (Functional Programming)

PUBLISHED ON APR 8, 2018 — 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 提供 iteratoryield