### Tying Knots Generically

A comment by a friend and a puzzle on Lambda the Ultimate made me realise that the function

The problem it helps to solve is this: building circular datastructures in Haskell, otherwise known as Tying the Knot.

Remember how in my previous article I showed how you could view

Firstly, let's look at doing something similar to the Tying the Knot web page to solve Derek's puzzle. Here potential links are made by using a dictionary structure to allow names of objects to stand for direct references to objects. So define an operator to perform pointwise concatenation of string-valued functions:

Now define lookup into the dictionary, substituting a default value if needed:

And now we can translate some example equations into Haskell by hand. I'm considering

We now just apply

We can use a similar method to make a doubly linked list. Here is "A", "B" and "C" in a list with each letter pointing to its predecessor and successor if it exists:

And here's a nice advantage of using

Note how working your way up and down

But there is a slight problem with

But attempting to evaluate

So my original intuition a few weeks back was right. Taking an interesting axiom of modal logic, interpreting as a type, and them finding an implementation, did lead to something useful.

By the way, while I was thinking about

Update: Ocaml version by Matias Giovannini.

`loeb`that I defined a few weeks back does have a nice application.

> import Maybe

> import Data.Map

> loeb :: Functor a => a (a x -> x) -> a x

> loeb x = fmap (\a -> a (loeb x)) x

The problem it helps to solve is this: building circular datastructures in Haskell, otherwise known as Tying the Knot.

`loeb`solves this problem in a very generic way that imposes the minimum of restrictions on the user.Remember how in my previous article I showed how you could view

`loeb`as a kind of spreadsheet evaluator. You have a container of functions and that is converted into another container by applying these functions to the final container. This is a circular definition, we're applying the functions to the final result to get the final result. If we think of the final container as a collection of answers to a bunch of problems,`loeb`allows each element to be constructed using references to any of the other answers in the container, even if they haven't actually been found yet. This is*exactly*what we need to make circular references.Firstly, let's look at doing something similar to the Tying the Knot web page to solve Derek's puzzle. Here potential links are made by using a dictionary structure to allow names of objects to stand for direct references to objects. So define an operator to perform pointwise concatenation of string-valued functions:

> f +++ g = \x -> f x ++ g x

Now define lookup into the dictionary, substituting a default value if needed:

And now we can translate some example equations into Haskell by hand. I'm considering

`define a x *b`and`define b y *a`. Note how it's trivial to write a parser to make these objects because there's nothing circular going on:

> equations = fromList

> [

> ("a",const "x"+++lookup "b"),

> ("b",const "y"+++lookup "a")

> ] where lookup = Data.Map.findWithDefault ""

We now just apply

`loeb`to get a dictionary containing the actual values:

> values = loeb equations

> a = fromJust $ Data.Map.lookup "a" values

We can use a similar method to make a doubly linked list. Here is "A", "B" and "C" in a list with each letter pointing to its predecessor and successor if it exists:

> data DList a = Nil | Node a (DList a) (DList a) deriving Show

>

> val (Node a _ _) = a

> rt (Node _ _ r) = r

> lft (Node _ l _) = l

>

> nodes = fromList

> [

> ("a", \d -> Node "A" Nil (lookup "b" d)),

> ("b", \d -> Node "B" (lookup "a" d) (lookup "c" d)),

> ("c", \d -> Node "C" (lookup "b" d) Nil)

> ] where lookup = Data.Map.findWithDefault Nil

>

> abc = loeb nodes

> b = fromJust $ Data.Map.lookup "b" abc

`b`is now a doubly linked list and we can use`lft`and`rt`to walk up and down it.And here's a nice advantage of using

`loeb`. You don't have to restrict yourself to storing information about links in a dictionary. Any functorial container will do. For example here's a doubly linked circular list of the integers from 0 to 99 made without using any names:

> zlist = [\z -> Node i (z!!((i-1) `mod` 100)) (z!!((i+1) `mod` 100)) | i <- [0..99]]

> z = loeb zlist

Note how working your way up and down

`zlist`is a slow process because you need to use the slow`(!!)`to access elements. But stepping up and down any element of`z`takes time O(1). Potentially very useful!But there is a slight problem with

`loeb`. I'd like to be able to handle errors better and the obvious way to do that is by allowing the use of monads to handle exceptions, for example if a name lookup in a dictionary fails. I attempted to do this as follows:

> class Monad m => MFunctor m f where

> fmapM :: (a -> m b) -> f a -> m (f b)

> instance Monad m => MFunctor m [] where

> fmapM = mapM

> loebM :: (Monad m,MFunctor m a) => a (a x -> m x) -> m (a x)

> loebM x = r where

> r = do

> lx <- r

> fmapM (\a -> a lx) x

> u = loebM [const (Just 1),const (Just 2)]

But attempting to evaluate

`u`overfows the stack. It also failed when I tried modifying it to use`MonadFix`. So here's a puzzle. Can you write a monadic version of`loeb`? It seems like something that would be very useful for writing interpreters for programming languages that allow mutually recursive definitions.So my original intuition a few weeks back was right. Taking an interesting axiom of modal logic, interpreting as a type, and them finding an implementation, did lead to something useful.

By the way, while I was thinking about

`loeb`I was led to consider what I call*tautological containers*. These are containers where each element tells you how to extricate it from the container. For example, these can be thought of as tautological:`(fst,snd)`,`[head,head.tail]`,`[(!!n) | n <- [0..]]`and`[("a",fromJust . lookup "a"),("b",fromJust . lookup "b")]`. Can you see any use for these objects? Are they universal for some category diagram? I have partial answers to these questions but maybe you can make more sense of them than me.Update: Ocaml version by Matias Giovannini.

Labels: haskell