Comments on A Neighborhood of Infinity: Tying Knots Generically

Unfortunately, the function loeb given in the text...

2009-11-29T09:02:29.619-08:00

Unfortunately, the function loeb given in the text does not produce a circular data structure with pointers into itself; rather, it produces an infinite stream of identical data structures (indexed by successive calls to loeb) each with pointers into the next. To see this, one needs to add an observable side-effect:

> import Debug.Trace

> zlist' = [\z -> Node i (z!!!((i-1) `mod` 100)) (z!!!((i+1) `mod` 100)) | i <- [0..99]]
> where lst !!! ind = trace ("indexing " ++ show ind) $ lst !! ind

> z' = loeb zlist'

Note how the first time one asks for, say, the lft of some node, it runs down the list looking for it

> val $ lft $ head z'
indexing 99
99

but the second time, that reference is cached

> val $ lft $ head z'
99

Now we can tell that rt . lft does not get us the same node, because the lft of that node has to run down the list again.

> val $ lft $ rt $ lft $ head z'
indexing 0
indexing 99
99

The "indexing 99" is repeated, and shouldn't be.

Fortunately, this bug can be fixed:

> loeb' x = result where result = fmap (\a -> a result) x

> z'' = loeb' zlist'

> val $ lft $ head z''
indexing 99
99

> val $ lft $ rt $ lft $ head z''
indexing 0
99

Now rt . lft really does get us back to the same node, as intended.

Ah...'Naperian' is just the concept I need to help...

2007-01-02T11:40:00.000-08:00

Ah...'Naperian' is just the concept I need to help thinking about these things.

Your tautological containers remind me of Peter Ha...

2007-01-02T01:24:00.000-08:00

Your tautological containers remind me of Peter Hancock's Naperian functors. These are containers of fixed shape (such as the pairs, streams, and ("a","b")-dictionaries you use as examples). The names comes from the fact that they have a notion of "position", which has many of the properties of a logarithm.

ski, u = loebM [const (Just 1),Nothing] Works lo...

2006-12-29T21:13:00.000-08:00

ski,

u = loebM [const (Just 1),Nothing]

Works lovely.

But then I try:

import Prelude hiding ((!!))
...
(!!) :: [a] -> Int -> Maybe a
[] !! _ = Nothing
a !! 0 = Just $ head a
a !! n = do
x <- (tail a) !! (n-1)
return x

u = loebM [const (Just 1),!!0]

and that fails to terminate. The intention is that if !!n returns Nothing then the whole thing should fail with Nothing.

How about the following ? import Control.Monad....

2006-12-29T14:32:00.000-08:00

How about the following ?

import Control.Monad.Fix

class Monad m => MFunctor m f
where
fmapM :: (a -> m b) -> (f a -> m (f b))

instance Monad m => MFunctor m []
where
fmapM = mapM

pamfM :: MFunctor m f => f a -> (a -> m b) -> m (f b)
pamfM = flip fmapM

loebM :: (MonadFix m,MFunctor m f) => f (f a -> m a) -> m (f a)
-- both works
loebM f = mdo let mfa = f `pamfM` ($ fa)
fa <- mfa
return fa
loebM f = mfix $ \fa -> do
f `pamfM` ($ fa)

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

-- Stefan Ljungstrand

joesf, I had more or less convinced myself that l...

2006-12-28T11:41:00.000-08:00

joesf,

I had more or less convinced myself that loebM was impossible but I think you've put the final nail in the coffin. In fact, I think that something like loebM isn't necessarily the best way to handle errors in this situation anyway and that with a bit of extra work, you can still use loeb.

I don't have a solution to your loebM puzzle but a...

2006-12-28T10:52:00.000-08:00

I don't have a solution to your loebM puzzle but an explanation as to why it fails. Your definition of loebM requires that bind is lazy. What I mean is that bottom >>= f /= bottom. If bind is strict then loebM will inevitably diverge.

Now, this leads to a bit of a problem because all monads that I know of that supply some kind of failure have strict binds. I conjecture that this must necessarily be the case, all monads will failure are strict. And this spells doom for you loebM.

I guess you already was aware of this but I'd thought I'd spell it out. And the puzzle remains unsolved.

For some reason your loeb function reminded me a l...

2006-12-28T06:49:00.000-08:00

For some reason your loeb function reminded me a lot of the List-ana(morphism) function from the webpage: http://www.cs.indiana.edu/~jsobel/Recycling/recycling.html

Your definition of loeb:
loeb f =
fmap (\a -> a (loeb f)) f

The definition of list_ana (translated to Haskell)

list_ana psi = f
where f l = map f (psi l)

If we generalize map to fmap then they seem nearly the same. Now the list_ana won't type in Haskell, but this is due to an infinite type which surely could be solved by adding proper constructors and destructors.

Could we perhaps say that loeb is a generalized ana-morphism, or is this reading too much into the seeming similarity.