[Lua] 程式設計教學：撰寫函數式程式 (Functional Programming)

函數式程式 (functional programming) 的前提在於函式是第一階物件 (first-class objects)，簡單地說，函式也可以是值 (value)。在此基礎上，函式可以傳入另一個函式做為參數，也可以做為某個函式的回傳值。Lua 雖然不是純函式語言，但的確支援某些函數式語言的特性。

由於函數式程式是相對進階的概念，一開始覺得難以理解的話，先略過本文也沒關係。

匿名函式 (Anonymous Function)

匿名函式 (anonymous function) 指的是不宣告函式名稱的函式，通常是用來做為參數或回傳值，如下例：

function array_eq(a1, a2)
  if #a1 ~= #a2 then
    return false
  end

  for i = 1, #a1 do
    if a1[i] ~= a2[i] then
      return false
    end
  end

  return true
end

local arr = {2, 4, 1, 5, 3}
table.sort(arr, function (a, b) return a < b end)

assert(array_eq(arr, {1, 2, 3, 4, 5}))

在本例中，我們宣告一個匿名函式 function (a, b) return a < b end，將其做為參數傳入 table.sort 中，table.sort 就可以依據我們所傳入的匿名函式來排序。

閉包 (Closure)

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

function number()
    local i = -1

    return function()
        i = i + 1
        return i
    end
end

local f = number()

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

在這個例子中，number 函式回傳一個匿名函式，該匿名函式帶有內部帶著一個計數器 i，而 i 的狀態會隨著每次呼叫而更新。

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

function fib()
    local a = 0
    local b = 1

    return function()
        local out = a
        c = a + b
        a = b
        b = c
        return out
    end
end

local f = fib()

local arr = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}
for i = 1, #arr do
    assert(f() == arr[i])
end

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

function prime()
    local n = 1
    local out

    return function()
        while true do
            n = n + 1
            local isPrime = true

            for i = 2, math.floor(math.sqrt(n)) do
                if n % i == 0 then
                    isPrime = false
                    break
                end
            end

            if isPrime then
                out = n
                break
            end
        end

        return out
    end
end

local f = prime()

local arr = {2, 3, 5, 7, 11, 13, 17, 19, 23}
for i = 1, #arr do
    assert(f() == arr[i])
end

在以下閉包中，我們使用一個 table 做為快取，減少重覆計算所需的時間：

function fib()
    local cache = {}
    cache[0] = 0
    cache[1] = 1

    function f(n)
        assert(n >= 0 and n % 1 == 0)
        if cache[n] ~= nil then
            return cache[n] 
        end

        local out = f(n - 1) + f(n - 2)
        cache[n] = out
        return out
    end

    return f
end

local f = fib()
-- f starts with 0
assert(f(10) == 55)

高階函式 (Higher-Order Function)

高階函式 (higher-order function) 是指使用函式做為參數或用函式做為回傳值的函式。我們先前的閉包也是一種高階函式。雖然 Lua 內建的函式庫不強調高階函式的運用，實作這些高階函式並不會太難。我們展示幾個常見的高階函式的模式。

grep

grep 函式接收一個陣列和一個函式，根據該函式的結果過濾符合條件的值，再回傳一個新的陣列。如下例：

function grep(arr, f)
    local a = {}

    for i = 1, #arr do
        if f(arr[i]) then
            table.insert(a, arr[i])
        end
    end

    return a
end

# Declare array_eq as above.

local arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
local even = grep(arr, function (n) return n % 2 == 0 end)
assert(array_eq(even, {2, 4, 6, 8, 10}))

map

map 函式接收一個陣列和一個函式，根據該函式的結果轉換值，再回傳一個新的陣列。如下例：

function map(arr, f)
    local a = {}

    for i = 1, #arr do
        table.insert(a, f(arr[i]))
    end

    return a
end

# Declare array_eq as above.

local arr = {1, 2, 3, 4, 5}
local sqr = map(arr, function (n) return n * n end)
assert(array_eq(sqr, {1, 4, 9, 16, 25}))

reduce

reduce 函式接收一個陣列和一個函式，根據該函式的結果將陣列縮減為單一值後回傳。如下例：

function reduce(arr, f)
    assert(#arr > 0)

    if #arr == 1 then
        return arr[1]
    end

    local out = arr[1]
    for i = 2, #arr do
        out = f(out, arr[i])
    end

    return out
end

local arr = {1, 2, 3, 4, 5}
local sum = reduce(arr, function (a, b) return a + b end)
assert(sum == 15)

sort

Lua 內建的 table.sort 即使用高階函式的概念，我們在先前的例子已經展示過，這裡不再重覆。

zip

zip 函式接收兩個相同長度的陣列，以兩個陣列的元素組成新的元組，回傳一個以元組為元素的陣列。如下例：

function zip(p, q)
    assert(#p == #q)

    local arr = {}

    for i = 1, #p do
       table.insert(arr, {p[i], q[i]}) 
    end

    return arr
end

function zip_eq(a1, a2)
  if #a1 ~= #a2 then
    return false
  end

  for i = 1, #a1 do
    if a1[i][0] ~= a2[i][0] and a2[i][1] ~= a2[i][1] then
      return false
    end
  end

  return true
end

local p = {1, 2, 3, 4, 5}
local q = {"a", "b", "c", "d", "e"}
local zipped = zip(p, q)
assert(zip_eq(zipped, {{1, "a"}, {2, "b"}, {3, "c"}, {4, "d"}, {5, "e"}}))

partition

partition 函式接收一個陣列和一個函式，根據該函式的結果將陣列拆解成兩個新的陣列，兩陣列長度不一定相等。如下例：

function partition(arr, f)
    local p = {}
    local q = {}

    for i = 1, #arr do
        if f(arr[i]) then
            table.insert(p, arr[i])
        else
            table.insert(q, arr[i])
        end
    end

    return p, q
end

# Declare array_eq as above.

local arr = {1, 2, 3, 4, 5, 6, 7, 8}
local even, odd = partition(arr, function (n) return n % 2 == 0 end)
assert(array_eq(even, {2, 4, 6, 8}))
assert(array_eq(odd, {1, 3, 5, 7}))

迭代器 (Iterator)

迭代器 (iterator) 指的是會逐一走訪容器或其他物件中元素的實體，外部使用者不需知道迭代器的內部實作；在 Lua，迭代器可用匿名函式來實作，並搭配用 for 來走訪。

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

function fib(n)
    local a = 0
    local b = 1
    local i = 1

    return function ()
        while i <= n do
            local out = a

            c = a + b
            a = b
            b = c

            i = i + 1

            return out
        end

        return nil
    end
end

local arr = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}
local i = 1

-- fib starts from 1
for n in fib(12) do
    assert(n == arr[i])
    i = i + 1
end

當迭代器結束時，需回傳 nil，這時候外部的 for 會將迴圈中止。

以下範例用迭代器撰寫質數數列：

function prime(n)
    local num = 1
    local i = 1

    return function()
        while i <= n do
            num = num + 1
            local isPrime = true

            for i = 2, math.floor(math.sqrt(num)) do
                if num % i == 0 then
                    isPrime = false
                    break
                end
            end

            if isPrime then
                return num
            end
        end

        return nil
    end
end

local arr = {2, 3, 5, 7, 11, 13, 17, 19, 23}
local i = 1

-- prime starts from 1.
for n in prime(9) do
    assert(n == arr[i])
    i = i + 1
end