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!

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!

Simple Memoization in Haskell

Being a beginner in Haskell, it took me quite a while to figure out a nice solution to this problem. (Of course, since I’m a beginner, I can’t guarantee that better solutions don’t exist!)

What’s the problem? Well, Haskell is, of course, a purely functional language, meaning that:

  • It has no real state to speak of,
  • Everything that’s calculated, is calculated by recursion.

See any contradictoins there? The classic solution to recursive problems is memoization. But memoization requires us to save state — something that’s unnatural and difficult in Haskell! So I’ll walk through a simple but general way to solve this problem.

Let’s use the classic example of the Fibonacci numbers, because I’m too lazy to come up with anything else and complexity would only get in the way. Note, however, that our solution works on recursive formulas of any number of variables.

fibs 0 = 1
fibs 1 = 1
fibs n = (fibs (n-1)) + (fibs (n-2))

Looks great, but if you try “fibs 40” you’ll never get an answer. We’re going to fix this by making a Data.Array. This array will store our Fibonacci numbers. The only downside is that we have to know ahead of time how large we want our Array to be.

OK, first we need to know how to make an Array. For more info on Arrays, you should check out the relevant article on A Gentle Introduction to Haskell. But for now, we’re going to use the mkArray function presented in that article:

import Data.Array
mkArray :: (Ix a) => (a -> b) -> (a,a) -> Array a b
mkArray f bnds = array bnds [(i, f i) | i <- range bnds]

-- make a one-dimensional array indexed from one to ten,
-- element at i is equal to i
arr1 = mkArray (\x -> x) (1,10)

-- make a 2d array from (0,0) to (10,10),
-- entry (i,j) is equal to i+j
arr2 = mkArray (\e -> (fst e) + (snd e)) ((0,0),(10,10))

Good. Now, how do we apply this to fibs in a general way?  Well, first we’ll transform our function into a “let” construct:

fibs x =
       let f 0 = 1
           f 1 = 1
           f n = (fibs (n-1)) + (fibs (n-2))
        in f x

Now we’re going to take “fibs” out and make it its own function, using the “let” construct to build our array.

fibarr = mkArray func (0,10000)
        let ...

fibs x = fibarr!(x)

Here we see how to access our array. More generally, if we want to access an n-dimensional array at a1,…,an, we have to access it using a tuple:  myarray!(a1,a2,…,an).

Ok, the last step is to connect the “func” used in building the array to our let clause down below. We’ll do this simply by defining func:

fibarr = mkArray func (0,10000)
    where func elem =
            let f 0 = 1
                f 1 = 1
                f n = (fibs (n-1)) + (fibs (n-2))
             in f elem

fibs x = fibarr!(x)

Note here that elem is a tuple in the more general case. With more than three variables, you may need to write your own functions to access the elements of a tuple beyond the first and second, or download the appropriate library. But here’s how the construct looks in the 2-dimensional case:

-- li and ui are lower and upper bounds
myarr = mkArray func ((l1,l2),(u1,u2))
    where func elem =
             let f x1 x2 = ...
                 ...
                 ...
              in f (fst elem) (snd elem)

origfunc x1 x2 = myarr!(x1,x2)

And here’s our complete code for fibs:

import Data.Array
mkArray :: (Ix a) => (a -> b) -> (a,a) -> Array a b
mkArray f bnds = array bnds [(i, f i) | i <- range bnds]

fibarr :: Array (Int) Integer
fibarr = mkArray func (0,10000)
    where func elem =
            let f 0 = 1
                f 1 = 1
                f n = (fibs (n-1)) + (fibs (n-2))
             in f elem

fibs :: Int -> Integer
fibs x = fibarr!(x)

main = do print (fibs 10000)

Installing Mercurial on Linux

Update: I’ve updated this post to focus on the steps to take in order to get mercurial working on your system, and some rough guidelines.

To install, use your installation/package manager. In Ubuntu, run:

sudo apt-get install mercurial

Now you need to set permissions. Inside your home directory, ~/, you can set up your “hgrc” (mercurial configuration file) with your username and default email address. Note that you must create and edit this file as the owner of ~/, not as root, because mercurial will only trust files that you created.  So open or create the file ~/.hgrc. Then enter the following lines:

[ui]

username = My Name <example@emailaddress.com>

with your name and email. Now you should be able to check out and use repositories.

Note that if you get errors about untrusted users (for example, mercurial ignores anything from “untrusted user root”, the only fix may be to edit your systems hgrc file to trust those users. The file is called /etc/mercurial/hgrc and you should add these lines to it:

[trusted]

users = root

Or any other users you wish to trust.

Using Mercurial

I won’t cover how to set up a Mercurial repository, because I didn’t — I just used bitbucket. To start out with a repository located at some url, use cd to navigate to the directory you want to use, then use hg clone to get a copy of a project. For example:

cd ~/my-documents/my-projects/
hg clone https://hostofproject.com/my-project-1

Or wherever it is. Now you’re ready to start developing!  If you create a new file or folder, you must add it to the project:

hg add *

Sending and receiving updates is a two-step process. To finalize all the changes and additions you’ve made, you must commit the changes. To send that final version to the repository, you must push it.

hg commit -m 'Made some changes'
hg push

Conversely, to get the newest version from the repository, you must pull it. To change your working copy to incorporate this new version, you must updateit.

hg pull
hg update

That’s the gist of it.

Easily Open a File in Java

Say you wanted to open a file in Java, either for reading or writing. But it’s not clear how to do it, and whether you need a GUI, and blah blah blah, wouldn’t it be nice to just find a minimal example?  Well then, here you go.

import javax.swing.*;   // for JFileChooser
import java.io.*;       // for File
import java.util.*;     // for Scanner (if you want to read it in)

class FileOpener {

    public static void main(String[] args) {
        JFileChooser fc = new JFileChooser();
        int returnVal = fc.showOpenDialog(null);
        if(returnVal == JFileChooser.APPROVE_OPTION) {
            File f = fc.getSelectedFile();
            // it's in your hands now...
        }
    }
}

Solid. Now say you want to read from the file:

            try {
                // read in the file
                Scanner s = new Scanner(f);
                String str = s.nextLine();
                // ...
            } catch(FileNotFoundException e) {
                // Couldn't find the file for some reason
                e.printStackTrace();
            }

Or writing to the file:

            try {
                FileWriter fw = new FileWriter(f);
                fw.write("Hello, World!");
                // ...
            } catch(IOException e) {
                // didn't work
                e.printStackTrace();
            }

Ta-da! Protip: If you’re using this as part of a GUI with a Component “comp” showing your main GUI screen, set “comp” to be the parent of the filechooser dialog by calling fc.showOpenDialog(comp);.

Other protip: if you really want, you can subject yourself to the official tutorial here.