I’m reading through this article on msdn. A few observations from a functional programmer’s perspective:

• Expression tree. MSDN does a poor job explaining the concept of meta programs. Expression trees are simply order 1 meta programs. “Expression tree” is more or less referring to the implementation, which does not help understand the concept at all.
• Deferred execution. This is simply call-by-name evaluation. It is NOT lazy evaluation, as it is evaluated every time the value is needed. It is not cached as a lazy evaluation would. Since there is no referential transparency in C#, there is a semantics difference.
• Aggregate. This is simply a left fold operation.
• SelectMany. It is just a composition of concat and Select.
• Anonymous type. It’s just a tuple.

Problem: arrange integers 1 to 15 in a line, so that every two adjacent numbers sum up to a perfect square.

Solution: all perfect squares in question would be 4,9,16, and 25. For each number, find all other numbers that add up to one of those 4 squres. This form a graph. Start from one vertex, find a Hamilton path. Since 8 and 9 each is connected to one edge, they must be the two ends of the path. Start from either of them. The answer is 8,1,15,10,6,3,13,12,4,5,11,14,2,7,9 or the other way round.

(more…)

I got a binary package of ghc from Wolfgang yesterday. But I haven’t had luck with bootstrapping ghc yet. I will give it another try. But meanwhile, I have downloaded alex 2.01 and happy 1.15 and compiled with some minor changes. I had to add the platform to the configure.ac and regenerate configure script. The rest just goes smoothly.

case $HostPlatform in
...
i[[3456]]86-*-darwin*)    
    HostPlatform=i386-apple-darwin    
    TargetPlatform=i386-apple-darwin #hack
    BuildPlatform=i386-apple-darwin #hack
        HostPlatform_CPP='i386_apple_darwin'
        HostArch_CPP='powerpc'
        HostVendor_CPP='apple'
        HostOS_CPP='darwin'
        ;;

One strong point of PERL is regular expression matching. I am thinking about implementing a domain specific embeded language in Haskell for the same purpose. Inspired more or less by Parsec and after one hour of coding, I implemented such a simple matcher. It currently only matches a regular expression against a strings, tells us if it matches or not. It lacks the ability of binding certain parts of the string (which might be more useful). An example:

(more…)

I was working on a simple imperative language interpreter, mostly for the purpose of demonstration of scoping and parameter passing. It’s more like a debugger than an interpreter. Anyway, I guess it’s not important in this post. What I really want to document here is several refactorings I have done on the program.

(more…)

Some thoughts when reading the paper (actually 2 papers, mog89 and mog91).

A complete function of type A->B maps an object in set A to an object in set B. A computation that computes values of B, however, can have different models. It generally maps an object from A to an object of T B. In the case of partial computation, T B could be the lifted set of B.

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.

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.