tag:blogger.com,1999:blog-11295132.post2424135430520381113..comments2015-05-30T22:32:59.468-07:00Comments on A Neighborhood of Infinity: Evaluating cellular automata is comonadicDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-11295132.post-72713394410717738192015-04-11T12:36:08.169-07:002015-04-11T12:36:08.169-07:00IHaskell notebook with diagrams drawing of CA:
ht...IHaskell notebook with diagrams drawing of CA:<br /><br />http://nbviewer.ipython.org/urls/gist.githubusercontent.com/miguel-negrao/571be4120ebecdbb3e26/raw/b740adc557fe097f9c6ff66ff7349bbf0a095091/gistfile1.txtMiguel NegrÃ£ohttp://www.blogger.com/profile/05017140798943559501noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-87328593951324693212013-10-17T22:07:02.376-07:002013-10-17T22:07:02.376-07:00Toroidal universes are a pretty simple extension (...Toroidal universes are a pretty simple extension (you could just use circular lists but that would lead to recalculating a lot of values)<br /><br />> right (U a b []) = right (U [] b (reverse a))<br />> right (U a b (c:cs)) = U (b:a) c cs<br />> left (U [] b c) = left (U (reverse c) b [])<br />> left (U (a:as) b c) = U as a (b:c)Jeremy Listhttp://www.blogger.com/profile/15206370639876586108noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-3419765393035123512013-10-17T22:06:07.130-07:002013-10-17T22:06:07.130-07:00Toroidal universes are a pretty simple extension (...Toroidal universes are a pretty simple extension (you could just use circular lists but that would lead to recalculating a lot of values)<br /><br />> right (U a b []) = right (U [] b (reverse a))<br />> right (U a b (c:cs)) = U (b:a) c cs<br />> left (U [] b c) = left (U (reverse c) b [])<br />> left (U (a:as) b c) = U as a (b:c)Jeremy Listhttp://www.blogger.com/profile/15206370639876586108noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-59167974019937031712011-08-08T10:06:04.232-07:002011-08-08T10:06:04.232-07:00scc,
That's an interesting little duality. Th...scc,<br /><br />That's an interesting little duality. The product type can be a comonad with no restrictions, but only a monad if its "extra" type is a monoid. Similarly, the reader type (or function type, whichever you prefer) can be a monad with no restrictions, but can only be a comonad if the "extra" type is a monoid.<br /><br />Also, you were expressing a lack of confidence in your definitions, so let's verify the comonad laws:<br /><br />1.<br /><br />coreturn . cojoin<br />= \x -> coreturn (cojoin x)<br />= \x -> cojoin x mempty<br />= \x -> (curry (x . uncurry mappend)) mempty<br />= \x y -> (x . uncurry mappend) (mempty, y)<br />= \x y -> x (uncurry mappend (mempty, y))<br />= \x y -> x (mappend mempty y)<br />= \x y -> x y<br />= \x -> x<br />= id<br /><br />2.<br /><br />fmap coreturn . cojoin<br />= \x -> fmap coreturn (cojoin x)<br />= \x -> coreturn . cojoin x<br />= \x y -> coreturn (cojoin x y)<br />= \x y -> cojoin x y mempty<br />= \x y -> curry (x . uncurry mappend) y mempty<br />= \x y -> (x . uncurry mappend) (y, mempty)<br />= \x y -> x (uncurry mappend (y, mempty))<br />= \x y -> x (mappend y mempty)<br />= \x y -> x y<br />= \x -> x<br />= id<br /><br />3.<br /><br />cojoin . cojoin<br />= \x -> cojoin (cojoin x)<br />= \x -> cojoin (curry (x . uncurry mappend))<br />= \x -> curry (curry (x . uncurry mappend) . uncurry mappend)<br />= \x y z -> curry (curry (x . uncurry mappend) . uncurry mappend) y z<br />= \x y z -> (curry (x . uncurry mappend) . uncurry mappend) (y, z)<br />= \x y z -> curry (x . uncurry mappend) (uncurry mappend (y, z))<br />= \x y z -> curry (x . uncurry mappend) (mappend y z)<br />= \x y z w -> curry (x . uncurry mappend) (mappend y z) w<br />= \x y z w -> (x . uncurry mappend) (mappend y z, w)<br />= \x y z w -> x (uncurry mappend (mappend y z, w))<br />= \x y z w -> x (mappend (mappend y z) w)<br />= \x y z w -> x (mappend y (mappend z w))<br />= \x y z w -> x (uncurry mappend (y, mappend z w))<br />= \x y z w -> (x . uncurry mappend) (y, mappend z w)<br />= \x y z w -> curry (x . uncurry mappend) y (mappend z w)<br />= \x y z w -> cojoin x y (mappend z w)<br />= \x y z w -> cojoin x y (uncurry mappend (z, w))<br />= \x y z w -> (cojoin x y . uncurry mappend) (z, w)<br />= \x y z w -> curry (cojoin x y . uncurry mappend) z w<br />= \x y z w -> cojoin (cojoin x y) z w<br />= \x y -> cojoin (cojoin x y)<br />= \x y -> (cojoin . cojoin x) y<br />= \x -> cojoin . cojoin x<br />= \x -> fmap cojoin (cojoin x)<br />= \x -> (fmap cojoin . cojoin) x<br />= fmap cojoin . cojoin<br /><br /><br />Phew. That was long. But yes, your definitions are correct.gereeternoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-36117773184088400872009-10-21T13:17:12.476-07:002009-10-21T13:17:12.476-07:00So I went ahead and wrote the code. It's on hp...So I went ahead and wrote the code. It's on hpaste under http://hpaste.org/fastcgi/hpaste.fcgi/view?id=11012#a11019<br /><br />Try to run it, seems to work for me!<br /><br />Alex.Alex S.http://www.blogger.com/profile/11331489673081118981noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-41097915240095266912009-10-21T13:15:41.146-07:002009-10-21T13:15:41.146-07:00So I've gone forward and implemented the game ...So I've gone forward and implemented the game of life, without any fancy printing, but still, it seems to work:<br /><br />http://hpaste.org/fastcgi/hpaste.fcgi/view?id=11012#a11019<br /><br />Comments and suggestions are very welcome!<br /><br />Alex.Alex S.http://www.blogger.com/profile/11331489673081118981noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-81446392845200538572009-02-18T05:57:00.000-08:002009-02-18T05:57:00.000-08:00Pondering rewriting this but representing the 'uni...Pondering rewriting this but representing the 'universe' as a function from an integer leads one to realise that we get a comonad from functions from any monoid as follows:<BR/><BR/>coreturn a = a mempty<BR/>cojoin a = curry (a . uncurry mappend)<BR/>fmap f = (f.)<BR/><BR/>Which allows us to handle automata on 1d, square grids, hex grids, and so on. Albeit perhaps inefficiently.<BR/><BR/>I haven't tried this so it's probably embarrassingly wrong.sccnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-13489199552059595442008-06-30T18:18:00.000-07:002008-06-30T18:18:00.000-07:00Are all Zippers that are instances of Functor Como...Are all Zippers that are instances of Functor Comonads? Conversely, and simply, are all Comonads Zippers that are Functors? I've done a bit of reading on (co)monads, and the above is the current straw I'm grasping at for understanding comonads better. Am I missing the boat entirely?<BR/><BR/>As for the cellular automata implementation, Mathworld, etc, has a list of standardized rules. Rule 30 is demonstrated graphically as the banner of my company's webpage: http://www.logicaltypes.com/.<BR/><BR/>Here is a way to pattern-match to build these standardized rules:<BR/><BR/>> rule30 (U (a:_) b (c:_)) = bitfrom (rule30' (bitof a b c))<BR/>> where rule30' 111 = 0<BR/>> rule30' 110 = 0<BR/>> rule30' 101 = 0<BR/>> rule30' 100 = 1<BR/>> rule30' 011 = 1<BR/>> rule30' 010 = 1<BR/>> rule30' 001 = 1<BR/>> rule30' 000 = 0<BR/>> bitof x y z = 100 * t x + 10 * t y + t z<BR/>> t = fromEnum<BR/>> bitfrom = toEnum<BR/><BR/>(Ah, well, the indentation is not preserved, but you get the idea.)<BR/><BR/>Since all the standardized rules follow the above pattern (where the rule number is the bit-pattern result from the three-bit-pattern input), it is trivial in Haskell to write a generalized <BR/><BR/>rule :: Enum a => Int -> U a -> a<BR/><BR/>for all the rules that follow that pattern.geophfhttp://www.blogger.com/profile/09936874508556500234noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-50804140542767624632008-01-21T22:12:00.000-08:002008-01-21T22:12:00.000-08:00Whoa, and I thought this site was about the iPhone...Whoa, and I thought this site was about the <A HREF="http://personafile.com/iPhone-apps.html" REL="nofollow">iPhone</A>)!kathy greenhttp://www.blogger.com/profile/11053622218690927013noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-4764855201246679072007-08-15T15:51:00.000-07:002007-08-15T15:51:00.000-07:00You should try implementing the "Cellular Potts" m...You should try implementing the "Cellular Potts" model developed by Glazer & Granier. It's more physically meaningful than CA.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-43681462019926279292007-01-02T09:54:00.000-08:002007-01-02T09:54:00.000-08:00I think you're right, my rule doesn't seem to use ...I think you're right, my rule doesn't seem to use c. I just made up random rules until I liked the result.<br /><br /><em>there really is nothing to it</em><br />Yes! There are some incredibly difficult looking papers out there but when you actually get down to implementing examples they can suddenly seem close to trivial. Check out the comonad I define <a href="http://sigfpe.blogspot.com/2006/11/variable-substitution-gives.html">here</a> for an example that's reminiscent of the kinds of adding-up-lists-of-prices examples given in books like "Learn C in 21 days". And yet the paper I drew on is scary as hell!sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-87916294294254888212007-01-02T08:23:00.000-08:002007-01-02T08:23:00.000-08:00When I first saw this, I was frightened off by the...When I first saw this, I was frightened off by the seeming abundance of scary new concepts: cellular automata, comonads, functors (for no good reason I still get nervous when I see that word), universes. Then I read it a second time, read it instead of skimming it, and realised that oh... there really is nothing to it.<br /><br />The comonad stuff will take a while to sink in, but reading your post, I get the impression that they are not fundamentally deeper than monads. No cobrain is required to understand them, after all. Note: fellow weaklings might do well to have Cale's <a href="http://www.haskell.org/haskellwiki/Monads_as_Containers">Monads as containers</a> open in a separate window or browser tab.<br /><br />Thanks for this post. For starters, the literate Haskell helps, pasting and running is useful. More importantly, the post had this wonderful effect of mutual reinforcement, in which several things one does not know well get tied together, and as a result all become clearer. Not only do I now have a slight taste of comonad, I also have now more than heard about cellular automata, and my tenuous grasp of zippers is now strenghtened. Makes me wish zippers were first presented in list terms from the very beginning.<br /><br />What might have been helpful is some means for the easily frightened to realise that the post contains easy stuff, but short of inventing a Haskell coloured belts system, [this post is rated yellow belt; if you understand monads in terms of >>= and return, etc], I don't know what such a mechanism would consist of. Another potentially useful aid might be to put the example automaton rule into words, or even pictures. Incidentally, this particular example rule does not seem to make use of c. Is that right?koweyhttp://www.blogger.com/profile/11175806459477851520noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-30716549491664152282006-12-23T10:24:00.000-08:002006-12-23T10:24:00.000-08:00Here is the exact rule I used in my code:
rule' (...Here is the exact rule I used in my code:<br /><br />rule' (U2 (U<br /> (U (u0:_) u1 (u2:_):_)<br /> (U (u3:_) u4 (u5:_))<br /> (U (u6:_) u7 (u8:_):_))) =<br /> let n = length $ filter id [u0,u1,u2,u3,u5,u6,u7,u8] in<br /> u4 && (n==2 || n==3) || (not u4) && n==3<br /><br />Your code is amazingly close!<br /><br />Maybe I'll tidy up my code and fill it with useful comments so I can post the entire thing here.<br /><br />U2 converts a 1D universe of 1D universes into a 2D universe. 'fmap U2' converts...take a deep breath...a 2D universe of 1D universes of 1D universes into a 2D universe of 2D universes. 'fmap U2 . fmap' converts a 1D universe of 1D universes of 1D universes of 1D universes into a 2D universe of 2D universes. Conceptually, a 2D universe is the same thing as a 1D universe of 1D universes. The guts of the code is written in terms of 1D universes, and 'fmap U2 . U2' is just a bit of fluff at the end to convert everything back to 2D universes so cojoin has the right type.<br /><br />The 'roll' is just taking advantage of the thing I said in an earlier comment. If you think of the inner U's as columns and the outer one as rows, then fmap left and right shift up and down. The slightly weird thing about 'roll' is that exactly the same piece of code does rows and columns whereas you might expect one function with fmaps for columns and one function without for rows. You can think of fmap as 'ducking down' a layer of U-flavoured onion skin. The two rolls do different things because each time it is used there are different layers of onion skin in place. The best way to make sense of it is to do what I did - make U and U2 instances of Show that can print stuff out with a pretty layout and then go through cojoin one step at a time.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-86441136467775275152006-12-23T09:34:00.000-08:002006-12-23T09:34:00.000-08:00well I'm quite lost on the intuition of your roll,...well I'm quite lost on the intuition of your roll, and why you use fmap U2 in cojoin.<br />However, a rule would be written like this?<br />rule (U2 (U ((U (a:_) b (c:_)):_) (U (d:_) x (f:_)) ((U (g:_) h (i:_)):_))) = ...<br />where the letters have this alignment?<br />a b c<br />d x f<br />g h iSaizanhttp://www.blogger.com/profile/07314943153376710289noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-30542910119507659462006-12-22T17:55:00.000-08:002006-12-22T17:55:00.000-08:00Here are some more details:
> data U2 x = U2 (...Here are some more details:<br /><br />> data U2 x = U2 (U (U x)) deriving Show<br /><br />> instance Functor U2 where<br /><br />> fmap f (U2 u) = U2 $ fmap (fmap f) u<br /><br />> instance Comonad U2 where<br /><br />> coreturn (U2 u) = coreturn (coreturn u)<br /><br />> cojoin (U2 u) = fmap U2 $ U2 $ roll $ roll u where<br /><br />> iterate1 f = tail . iterate f<br /><br />> roll a = U (iterate1 (fmap left) a) a (iterate1 (fmap right) a)<br /><br />(Sorry about lack of indentation.) I have the game of life running fine.<br /><br />The strategy for U2 is much the same as that for U. cojoin makes a 2D grid of 2D grids where each inner grid is shifted an amount corresponding to its location within the outer grid. A similar strategy can be used to implement many other comonads. In fact, that was the ulterior motive in writing this CA code: getting intuition about what cojoin typically looks like.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-2793754813094543252006-12-21T07:41:00.000-08:002006-12-21T07:41:00.000-08:00I think there may be an easy but inefficient solut...I think there may be an easy but inefficient solution to the problem of working in 2D using the type U (U Bool). I'd imagine 'up' and 'down' to be defined like 'fmap left' and 'fmap right' or something like that. I think you can then construct a new 'cojoin' with a little bit of work. But this might be a bit inefficient. But maybe not - I'd have to think about it harder but all those 'fmap left's might still only do O(1) work per cell in total. When I next have a moment...sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-50527893470553879222006-12-21T07:03:00.000-08:002006-12-21T07:03:00.000-08:00I like very much this lazy solution, but how would...I like very much this lazy solution, but how would you generalize it to spaces with more dimensions?<br />(Like in Life where you have 8 other cells in your neighborhood.)<br />I can imagine increasing the number of the lists, but not very well how to travel this new universe, especially how to reach the cells in the "oblique" directionsSaizanhttp://www.blogger.com/profile/07314943153376710289noreply@blogger.com