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

PUBLISHED ON APR 8, 2018 — PROGRAMMING
FacebookTwitter LinkedIn LINE Skype EverNote GMail Email 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