美思 [Nim] 程式設計教學:函數式程式設計 (Functional Programming)

Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

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 來製做迭代器;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
關於作者

身為資訊領域碩士,美思認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目,那就是開發者和使用者雙贏的局面。

美思喜歡用開源技術來解決各式各樣的問題,但必要時對專有技術也不排斥。閒暇之餘,美思將所學寫成文章,放在這個網站上和大家分享。