A functional point of view of some cat theory concepts:

Functors: type constructors. They map types to types. If we consider each algebraic type as a category, the type constructors act as functors.

Natural transformations: polymorphic functions. They map types to types.

I bumped into an article about typesetting. It talks a little about the history, which is kinda interesting.

Below the header, I have added a block “quote of the day”. It is based on the notorious unix program fortune. I found the PHP script here.

I had to hack the theme a little bit to make it look nice. Code wise, changes were made in header.php. One drawback is the fortune data directory is relative to the PHP code that includes the script. So I have to either specify an absolute path or symlink under each directory that wants to include fortune.php. I currently have only two such directories, so not that bad.

Now it’s time to get interesting quotes and fiddle a little bit with the fonts and color.

After playing with WordPress a little bit, I am now slightly exposed to PHP. Generating HTML code with PHP does not seem to be fun, from my point of view, as a researcher in the area of meta programming. The text based approach is so ugly, clumsy and error prone. The generated code is basically not readable to human being. It is also very hard to get different modules to work together well.

Anyway, this is an ugly approach. It would be nice to have a functional HTML library based on AST. And of course, the first thing that comes to my mind is writing Haskell data type definitions, smart constructors and a pretty printer. Thus we can probably write a blogging platform using Haskell :). But I am not sure yet how to interact with databases. I currently have no knowledge in database. We probably will end up with heavy use of IO monad.

For now, there are some pointers I might want to refer to later:

• A Prettier Printer by Phil Wadler.
• HaXML. Since HTML is an application of XML, we certainly want to generalize. HTML might need some tolerence in validity though.
• HXML. This looks like a drop-in replacement of HaXML.

I need more information on:

• How to run a Haskell program as a CGI.
• How to interact with MySQL or other databases.
• Interaction with the system and IO in Haskell.

Type Classes with Functional Dependencies by Mark Jones.

This is an old paper we studied long ago and functional dependency in type classes is not new to me. But Steve asked a very good question today. We are currently required to explicitly declare the functional dependency in a multi-parameter type class definition if one or more type variables are not mentioned in some members. Is it possible for the compiler to infer this automatically? Now the problems reamining:

• Does there exist a least constrained dependency among all dependencies that can make overloading resolvable in a type class? My first intuition is yes and all the dependencies form a complete partial order.
• If so, does there exist a decidable algorithm to find out?

We need to formally define the semantics of the dependencies and try to find an algorithm or disprove the existence.

Purely Functional Random Access Lists by Chris Okasaki.

The problem this paper addresses is that in the traditional functional lists, accessing the ith element requires log(i) time. The approach proposed in this paper reduces lookup and update operations to log(n).

The idea is to represent a list with a list of full binary trees. A pre-order traversal of the trees gives a linear sequence of all the elements in the list. The whole list is broken into full binary trees by a greedy decomposition, with the sizes of the trees in ascending order. The cons operation distinguish several patterns and remains the invariant. The tail operation trivially keeps the invariant.

Drawbacks we have observed:

• Can not do a usual pattern matching on lists. There is a concept of views proposed in Haskell community which has not become an extention to the language yet. But it might be a solution.
• Seems to me that it does not achieve the ++ operation with the same time complexity. Consider concatenating two lists of length 7 and 1 respectively, say [0,1,2,3,4,5,6] and [7]. They are represented as:

  [    0      ] ++ [7] = [0,     1      ]
     /   \                     /   \
    1     4                   2     5
   / \   / \                 / \   / \
  2   3 5   6               3   4 6   7
  

  Basically all the elements are “shuffled”. However, with lazy evaluation, there might be a better amortized time complexity.