bells
安裝本網站至主畫面:

[Lua] 程式設計教學:函數式程式設計 (Functional Programming)

PUBLISHED ON JAN 30, 2018 — PROGRAMMING
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

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

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

    匿名函式

    匿名函式 (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) 是帶有狀態的 (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) 是指使用函式做為參數或用函式做為回傳值的函式。我們先前的閉包也是一種高階函式。雖然 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) 指的是會自動走訪元素的函式,外部使用者不需知道迭代器的內部實作,很常用在走訪容器上;在 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
    你或許對以下產品有興趣
    Xmas tree