Notes on codes, projects and everything

Imperfect Reimplementation of Lists in PHP

Long long time ago when I was working with Prolog, I was introduced to list. Unlike arrays in most popular programming languages, we weren’t really able to access to a particular member directly. Every list is constructed in a chain-like structure.

Each element of the list consists of two parts, the head and the tail. The head is the first element in the list, the tail is a new list containing the rest of the list. In order to access the second element, you would have to find the head of the original tail. In other words, the structure would looks something like this

+--------------+-----------------------------+
| Head: item-1 | Tail: Rest of original list |
+--------------+-----------------------------+
 
               +--------------+-----------+
Rest of orig.  | Head: item 2 | Tail: ... |
               +--------------+-----------+

Apparently lisp also adopt the same structure for lists. At least we are able to access the list the same way as prolog (not sure which predates another though). I always wanted to translate this structure to PHP somehow, but didn’t really get too far with it.

Implementing it is easy, but making it useful is not. I was bored just now and thought why not try again. So after some quick hacking, I managed to made a quick POC implementation. While it probably is not efficient (certain functions uses recursion, which is painfully unoptimized in PHP), but it does sort of work.

I didn’t spend much time testing it, as this is obviously not fit for production.

Using the functions in the script is easy. Firstly list construction is just simply

$list = list_get(1, 2, 3, 4);

Counting the length of the list

list_count($list);

Doing a map

$new_list = list_map(function($item) { return $item + 1; }, $list);

Doing a reduce

$new_list = list_reduce(function($current, $incoming) { return $current + $incoming; }, $list, 0);

Doing a filter

$new_list = list_filter(function($item) { return $item % 2 == 0; }, $list);

Getting head and tail


$head = list_get_head($list);
$tail = list_get_tail($list);

There are of course a lot of other things to do, for example lists concatenation. However, this is done for fun so I will probably continue working on it when I am bored again in future. The code is hosted at bitbucket as usual, and you probably want to have a quick look at it.

leave your comment

name is required

email is required

have a blog?

This blog uses scripts to assist and automate comment moderation, and the author of this blog post does not hold responsibility in the content of posted comments. Please note that activities such as flaming, ungrounded accusations as well as spamming will not be entertained.

Click to change color scheme