tag:blogger.com,1999:blog-11295132.post899713037400110773..comments2015-07-21T17:35:21.901-07:00Comments on A Neighborhood of Infinity: Tying Knots GenericallyDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-11295132.post-31353076808648647992009-11-29T09:02:29.619-08:002009-11-29T09:02:29.619-08:00Unfortunately, the function loeb given in the text...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:<br /><br />> import Debug.Trace<br /><br />> zlist' = [\z -> Node i (z!!!((i-1) `mod` 100)) (z!!!((i+1) `mod` 100)) | i <- [0..99]]<br />> where lst !!! ind = trace ("indexing " ++ show ind) $ lst !! ind<br /><br />> z' = loeb zlist'<br /><br />Note how the first time one asks for, say, the lft of some node, it runs down the list looking for it<br /><br />> val $ lft $ head z'<br />indexing 99<br />99<br /><br />but the second time, that reference is cached<br /><br />> val $ lft $ head z'<br />99<br /><br />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.<br /><br />> val $ lft $ rt $ lft $ head z'<br />indexing 0<br />indexing 99<br />99<br /><br />The "indexing 99" is repeated, and shouldn't be.<br /><br />Fortunately, this bug can be fixed:<br /><br />> loeb' x = result where result = fmap (\a -> a result) x<br /><br />> z'' = loeb' zlist'<br /><br />> val $ lft $ head z''<br />indexing 99<br />99<br /><br />> val $ lft $ rt $ lft $ head z''<br />indexing 0<br />99<br /><br />Now rt . lft really does get us back to the same node, as intended.Alexeyhttp://www.blogger.com/profile/11095629814500390449noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-24048748457052422402007-01-02T11:40:00.000-08:002007-01-02T11:40:00.000-08:00Ah...'Naperian' is just the concept I need to help...Ah...'Naperian' is just the concept I need to help thinking about these things.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-67325190454941871832007-01-02T01:24:00.000-08:002007-01-02T01:24:00.000-08:00Your tautological containers remind me of Peter Ha...Your tautological containers remind me of Peter Hancock's <a href="http://sneezy.cs.nott.ac.uk/containers/blog/?p=14">Naperian functors</a>. 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.Jeremyhttp://www.blogger.com/profile/03945885134870183516noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-43061333815506670822006-12-29T21:13:00.000-08:002006-12-29T21:13:00.000-08:00ski,
u = loebM [const (Just 1),Nothing]
Works lo...ski,<br /><br />u = loebM [const (Just 1),Nothing]<br /><br />Works lovely.<br /><br />But then I try:<br /><br />import Prelude hiding ((!!))<br />...<br />(!!) :: [a] -> Int -> Maybe a<br />[] !! _ = Nothing<br />a !! 0 = Just $ head a<br />a !! n = do<br /> x <- (tail a) !! (n-1)<br /> return x<br /><br />u = loebM [const (Just 1),!!0]<br /><br />and that fails to terminate. The intention is that if !!n returns Nothing then the whole thing should fail with Nothing.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-47218516111233108332006-12-29T14:32:00.000-08:002006-12-29T14:32:00.000-08:00How about the following ?
import Control.Monad....How about the following ?<br /><br /> import Control.Monad.Fix<br /><br /> class Monad m => MFunctor m f<br /> where<br /> fmapM :: (a -> m b) -> (f a -> m (f b))<br /><br /> instance Monad m => MFunctor m []<br /> where<br /> fmapM = mapM<br /><br /> pamfM :: MFunctor m f => f a -> (a -> m b) -> m (f b) <br /> pamfM = flip fmapM<br /><br /> loebM :: (MonadFix m,MFunctor m f) => f (f a -> m a) -> m (f a)<br /> -- both works<br /> loebM f = mdo let mfa = f `pamfM` ($ fa)<br /> fa <- mfa <br /> return fa<br /> loebM f = mfix $ \fa -> do<br /> f `pamfM` ($ fa) <br /><br /> u = loebM [const (Just 1),const (Just 2)]<br /> -- > u <br /> -- Just [1,2] <br /><br />-- Stefan Ljungstrandskihttp://www.blogger.com/profile/10190106980684029949noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-74581007822966928012006-12-28T11:41:00.000-08:002006-12-28T11:41:00.000-08:00joesf,
I had more or less convinced myself that l...joesf,<br /><br />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.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-18568010640542373502006-12-28T10:52:00.000-08:002006-12-28T10:52:00.000-08:00I don't have a solution to your loebM puzzle but a...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.<br /><br />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.<br /><br />I guess you already was aware of this but I'd thought I'd spell it out. And the puzzle remains unsolved.Josefhttp://www.blogger.com/profile/13272830598221833253noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-8822010972907363522006-12-28T06:49:00.000-08:002006-12-28T06:49:00.000-08:00For some reason your loeb function reminded me a l...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<br /><br />Your definition of loeb:<br />loeb f =<br /> fmap (\a -> a (loeb f)) f<br /><br />The definition of list_ana (translated to Haskell)<br /><br />list_ana psi = f<br /> where f l = map f (psi l)<br /><br />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.<br /><br />Could we perhaps say that loeb is a generalized ana-morphism, or is this reading too much into the seeming similarity.Christophe (vincenz)http://www.blogger.com/profile/02320035941417593372noreply@blogger.com