Lua-Functional library updated for Lua 5.2.0

The lua-functional library has been updated to version 1.101 and is now compatible with Lua 5.2.

Two other small changes:

  • range() can now be called with one argument. range(x) is equivalent to range(1,x) = {1,2,…,x}.
  • increased functionality of casef().

I’d like to briefly explain the second one, partly because it’s slightly complicated and partly because I think casef() is cool.

The closely related `case` is basically a long if/elseif chain. It takes in pairs of (x,y) and is equivalent to `if x1 then y1 elseif x2 then y2 elseif …`. Casef packages this behavior into a function that can be called later, and also allows x1 and y1 to be functions.

casef(case1,case2,case3,…) takes one or more arguments. Each table argument such as case1 has the form case1 = {pred,cond}. Each pred and cond argument may be one of the following: true, false, nil, or a function.

casef returns a function f. When called as f(a,b,c,…), it will check each predicate in order. If the predicate is a function, it will call pred(a,b,c,…) and use that as the value to check; otherwise, it just uses the predicate’s value. For the first true predicate (or more exactly, the first non-nil, non-false predicate), it returns the corresponding result. If ‘result’ is not a function, it is returned; if it is, then we return result(a,b,c,…).

Here’s a quick example — a recursion/memoization solution for computing the Levenshtein (or edit) distance between two arrays.

dofile('lua-functional.lua'):loadglobally()

levenshtein_dist = function(arr1,arr2)
    -- d is a list of #arr1 empty lists
    local d = gen({}, function() return {} end,
                  function(a,ind) return ind>#arr1 end)
    
    -- f(i,j) = edit distance between arr1[1:i] and arr2[1:j]
    f = casef(
    {function(i,j) return i==0 end, function(i,j) return j end},
    {function(i,j) return j==0 end, function(i,j) return i end},
    {function(i,j) return d[i][j] end, function(i,j) return d[i][j] end},
    {true, function(i,j)
               d[i][j] = case({arr1[i]==arr2[j],f(i-1,j-1)}, -- match at current location
                              {true, min({f(i-1,j)+1,        -- deletion
                                          f(i,j-1)+1,         -- insertion
                                          f(i-1,j-1)+1})})   -- substitution
               
               return d[i][j]
           end})
    
    return f(#arr1,#arr2)
end

print(levenshtein_dist({1,3,2,3,4},{2,3,3,3,3,4}))

The heart of the method is the recursive function f.  f takes care of its base cases first: if i or j is zero. Then it checks if we have already computed and memoized this square; if so, return it. Finally, for all other cases (condition “true”), recursively compute and memoize the minimum edit distance based on recursive calls to f.

A final note: within this last function, we call case rather than casef. This is somewhat computationally expensive, because we have to call f four times to fill the arguments to the case statement — if we’d used casef and wrapped these calls inside functions, only the necessary one would’ve been called. However, it would have required more typing.

Anyway, as always, I appreciate any feedback, thoughts, or comments on lua-functional!

About these ads

One comment on “Lua-Functional library updated for Lua 5.2.0

  1. Anonymous says:

    How about on Luau…Hawaii.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s