Generalized Monads --> Gonads :-)

Here is the usual (basic) definition of monads:

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

This is very much restricted to ordinary function types!
Let's see how this restriction can be lifted...

class Category (~>) => Geonad (g (~>)) where
  return :: a ~> g (~>) a
  (>>=) :: g (~>) a ~> (a ~> g (~>) b) ~> g (~>) b

Since the semantics of gonads are already eminently taken, I settled for the name Geonad.

No idea whether this can produce something relevant for our lives :-)

Cheers,
      Gabor

Category

With lots of rejoicing, today I discovered that the base-3.0 library, to be distributed with the upcoming GHC 6.10, will contain the Control.Category type class. This is exactly what is needed to put Thrist (~>) into a general context!

Can't wait till September...

PS: It is also a nice surprise that Ashley Yakeley, the maintainer of this module is an old-time Dylan person :-)
Sometime I have to blog about the lots of developers who share a common Haskell/Dylan heritage.

I'd like to see, but do you want to Show?

So, yesterday I tried to implement

instance Show (Thrist (a ~> b)) where ...

... and ran against several walls. The short story is: Forget it!

The long story comes next, if you are interested.

First of all, what do we want? In my paper I define a nice thrist

[('A', 33), (65, 'a')]l :: Thrist (,) Char Char

and the Ωmega interpreter readily prints it. I wanted to do the same in Haskell too, as a pretty extension of my thrist package. I started like this:

instance Show (a ~> b) => Show (Thrist (~>) a b)
show Nil = "[]l"

I even managed to show singleton thrists (which hold just one element).
But the first obstacle was immediate: When the thrist has more than one element the hidden existential type appears, but the compiler does not know that this (a ~> x) has a Show instance!

So I hoped to extend the context to require Show (forall a b . a ~> b) that is I want all saturations of the type constructor (~>) to be Showable. But GHC does not like this syntax...

At his point I started some fundamental thinking...

Since the type of the thrist only reveals the beginning and the end, there may be arbitrary non-showable types hidden inside, even if the resulting type conveys the illusion of Showability. To wit:

[(5, id), (id, 42)]l :: Thrist (,) Int Int

We can enter such a thing, but there is no hope to show it :-(

So what are our remaining options? Ganesh has brought Show2 to my attention, I might look at it soon, but it won't solve the above problem.

We can say goodbye to (,) and define something like:

newtype Pair a b = (Show a, Show b) => Pair (a, b)

There is some hope that Thrist Pair a b can be declared as a Show2 instance.
Who knows?

PS: Ωmega cheats, of course. It frobs the Show functionality of the underlying Haskell implementation. It also prints functions as <fn>.

Uploaded

It's done!

My first contribution to the Haskell community has just landed in the belly of the beast...

Overall it was a very pleasurable experience:

• the website is well organized and makes it easy to find the relevant information,
• the account is obtained unbureaucratically by e-mail, and the answer is prompt,
• the upload checker provides helpful guidance how to improve the package.

The package itself is in very early stage, please do not expect a wealth of functionality :-). Also the (constructor) function names are expected to change (Cons --> :~) to better fit into the language's overall feel.

I have already included a crucial foldThrist function, which is Ganesh's idea (thanks for the feedback, btw.!). What comes now is to figure out how mapThrist could be defined. It is somewhat tricky, as there are three type parameters to deal with (let alone all the existential types inside).

One thing comes to my mind as I think about it. mapThrist could change the first parameter, i.e.:

Thrist (->) a b -> Thrist (,) a b

an elegant way to record the intermediate values of function composition.

Fun stuff.

Ca(ni)balized

Today I finally came around reading my way through the Creating my First Haskell Package tutorial, and have put together my first cabalized library. And I must confess that I found it really enjoyable. Certainly not more complicated than writing a makefile or adding a macport.

Btw., the said library is thrist-0.0 (what a surprise!) and it is just the embryonal first step. I already have some more stuff in the pipeline...

Could not upload it to Hackage yet because I am waiting for my account on the server.

Trotting Forward

I am in vacation in Brazil, mostly in an apartment building facing the ocean, but I had little chance to enjoy the water so far. There are several reasons for this, the most important being that Helena was sick the past week and still receives antibiotics. It is also raining a lot and is somewhat cold (24 °C) for my taste.
But I have the nights for creative work, so I picked up my recent idea and started fleshing out the design.
I succeeded in writing a QuickCheck generator for randomly creating Insert/Remove sequences steering the lifetime of a Value's def/use chain. I am able to update a given chain according to a history and check that it has still consistently set up waymarks that lead back to the Value.

I am pretty happy with the results so far.

Now it is time to enter the second phase and proactively optimize worn-off waymarks. As discussed in the other blog post the stretchy/shrinky nature of def/use chains leads to deterioration of the waymarks because Stop marks may be punched into the valid (fixed-length) clusters of Zeros/Ones. This happens at Insert events. On the other hand, Remove events may reduce clusters, thus invalidating them. So it is important to refresh the waymarks when longer islands of invalid marks are encountered. The twist is to retain O(1) complexity, which is not too challenging, but given the volatility of the chain some cleverness is needed.

I have a smallish plan how to do it: Since I expect that the volatility mostly occurs at the head of the chain (short-lived Use object getting inserted and soon removed), I intend to adjust the waymarks as far to the end as possible. So I have to keep a pointer to the start to invalid cluster immediately preceding a found valid cluster (or FullStop) and refresh the waymarks if there are enough elements present to form a valid cluster. Alternatively I could use the Prev members to walk backwards (in the C++ implementation, since these do not appear in Haskell).

But I expect that only a nice histogram of a usage statistics will help to find the optimal strategy anyway.