Wed, 21 Dec 2005 00:00:00 UT

SOLSTICE! Pathological Cases, Free Algebras

That's right girls and boys, it's the SOLSTICE! It doesn't get any darker than this, the SUN is RETURNING!
For my own entertainment I tracked down a formula to estimate the amount of sunlight I get in these parts. With latitude 65.8003 and longitude 21.704, and a formula from Dr. Math, I get

I like trying custom settings for sgt-puzzles. Here we see a screenshot of untangle with one thousand nodes.

Derek Elkins made another insightful comment on Lambda the Ultimate. This is something I immediately understand, but cannot explain. Maybe after I read the linked papers. As Derek said, "Monads for Free algebras." Now I have to learn what those are, and what use they have. ^[1] My intuitive understanding is that certain mathematical structures dovetail perfectly with monads. Since I am familiar with monads, I can clearly see how the code below elegantly describes certain conventions used in Haskell. The real question is, once I understand Free Algebras, where else does Haskell mesh perfectly with universal algebra?

data FreeMonad sig a 
  = Return a 
  | Expr (sig (FreeMonad sig a))

foldFM ret expr (Return a) = ret a
foldFM ret expr (Expr e)
  = expr (fmap (foldFM ret expr) e)

instance Functor sig => Functor (FreeMonad sig) where
    fmap f = foldFM (Return . f) Expr

instance Functor sig => Monad (FreeMonad sig) where
    return = Return
    fm >>= f = foldFM f Expr fm

-- examples

-- Maybe is
data MaybeSig x = Nothing

-- Tree (NonDet) is
data NonDetSig x = Fail | Amb x x

-- Either s is
data EitherSig s x = Error s

[1] Wikipedia has the wrong Free Algebras, Cale Gibbard suggests reading the math atlas and purchasing MacLane's "Categories for the Working Mathematician."