Relational Algebra in Haskell

I've just spoken to Jon about the problems and ideas I have posted about previously. One of the things I came away with is the suggestion that I might be thinking about relational algebras (perhaps an algebra over a set) rather than hypergraphs. I'm not entirely sure that this is the case (the "hypergraph" Wikipedia article above seems to describe what I'm thinking of), but the "algebra over a set" article is certainly applicable as well).

As a result, I've been able to dig up a couple of things that look like they might help me implement support for generic frames (i.e. those with an arbitrary number of n-relations for arbitrary values of n greater than 0).

While I've seen A Relational Algebra Simulator in Haskell before, it didn't occur to me that it might be applicable to my problem. RATH - Relation Algebra Tools in Haskell, however is new to me and looks like it provides a complete library (rather than the example program of the first link).

Whether I have enough time to catch up on my course-work, finish my system (as it stands), write a thesis and learn enough about this topic to extend the system using such a generalisation remains to be seen.

Another possibly useful generalisation might be to extend the concept of "relation" from sets of tuples to mutisets (or bags) of tuples, thereby allowing relations in a frame to be mutigraphs (i.e. graphs allowing multiple edges between a given pair of vertices). The Data.Graph.Inductive library supports labelled edges which suggests that it might also support multigraphs to some degree (if edges with non-identical labels are non-identical, then you can simulate an unlabelled multigraph by labelled each edge with an index).

I'd like to write a generic graph library with support for multigraphs and [uniform] hypergraphs, possibly by extending Data.Graph.Inductive, but this will probably wind up being pushed back until the Christmas break.

Modal Logic Wikipedia Articles

I've been poking at Wikipedia again (I dislike free time) and decided that a list of articles relevant to modal logic might be useful. To that end, I present a partial list of Wikipedia articles:

• Kripke Semantics
• Modal Logic
• Temporal Logic
• Proof Theory
• Model Theory
• Analytic Tableaux

In addition to the articles above (which aren't really directly relevent to my work), there are a number of articles that I've found useful in trying to puzzle my way through things. A partial list of these useful articles is:

• Hypergraph
• Multigraph
• Power set
• Algebra over a set

More articles will be added to this list as they are uncovered.

Annoyances of the Feature Kind

Yesterday, I finally sat down and wrote a priority queue (a heap to those in the know) to store the formulae on a branch that still need to be processed. Chris Okasaki (in his book Purely Functional Data Structures) defines the interface of a heap as follows:

class Heap h where empty :: (Ord a) => h a
isEmpty :: (Ord a) => h a -> Bool

insert :: (Ord a) => a -> h a -> h a
merge :: (Ord a) => h a -> h a -> h a

findMin :: (Ord a) => h a -> a
deleteMin :: (Ord a) => h a -> h a


This is a problem (in my opinion) in that it requires that heaps (all heaps) be over ordered data-types. The entire reason that I am attempting to extend the heap is to remove the ordering from the contained type, and use a priority type instead. Thus we are no longer saying that, for example, α < β but that (priority α) < (priority β)

I'll be the first to admit that this isn't much of a distinction to make (especially from a pragmatic "programmer" point of view), but it is a nicer approach.

I got around this problem, such as it is, by modifying my Prioritised class to have a function to inject values into my Priority type and one to extract them. The heap then is a type synonym:type PriorityHeap t = LeftistHeap (Priority t) with the restriction that you need to explicitly wrap values you insert into a heap:let h' = insert (priority v) h in ... and unwrap those you get out: let v = value $ findMin h' in ...

Not terribly inconvenient, but not ideal. I'm fairly sure that this could be solved with some functional dependancies magic, but the current state of affairs is good enough to be getting on with.

Purely Functional Data Structures

The Haskell code from Purely Functional Data Structures by Chris Okasaki can be found as his web-site at the United States Military Academy.

RSChem is Burning Down, Burning Down, Burning Down...

RSChem is currently on fire. There haven't been any reported injuries, but they have evacuated that precinct of the campus.