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!

Advertisements

A Functional Library For Lua

I’ve put up online a functional programming library for Lua that I wrote this summer. It’s located here:

https://bitbucket.org/luafunctional/lua-functional

 

The idea is to provide a bunch of functional programming constructs such as maps, filters, folds, list comprehensions, zips, some stuff like that. It includes a documentation file and a test suite that I’ve used to make sure the functions are correct and bug-free. (But you can never be sure!)

The bad news — I tested it with Lua 5.1.4, the current version, but Lua 5.2, in beta, introduces some changes that break lua-functional. I hope to have a fix for this up by the time Lua 5.2 is official!