Saturday, August 31, 2013

Filling in lists with gaps

As I've mentioned before I believe it is useful to be able to specify lists and other related structures using only selected slots like so:
{third 3, fourth 4}
{first 1, second 2, fourth 4}

This naturally leads to a notion of lists with gaps. The gaps of a list are precisely those slots that aren't presently provided with any value. If a list has gaps it naturally follows that we can provide a function to fill in some of those gaps:
(fillin dup? [1 2 nil nil]) ;-> (1 2 1 2)
(fillin dup? [nil 20 10 nil]) ;-> (10 20 10 20)

The idea of the fillin function is to use conditional functional dependencies to fill in any slots of an element of a relation with their necessary values if such values exist. Gaps without necessary values are unaffected. This can be also be used on general lists with a predicate like palindrome?:
(fillin palindrome? [1 2 3 nil nil nil]) ;-> (1 2 3 3 2 1)
(fillin palindrome? [nil 20 30 nil 10]) ;-> (10 20 30 20 10)

The fillin function over this palindrome? predicate can even be used to reverse a list as demonstrated above. My current thinking is that it would be nice to have a relational lisp that has first class support for lists with gaps but that would probably require that I abandon the most popular lisps which is not something I am ready to do.