【在主画面加入捷径】
       
【选择语系】
繁中 简中

Lua 程序设计教学:函数式程序设计 (Functional Programming)

【赞助商连结】

    函数式程序 (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