tag:blogger.com,1999:blog-11295132.post7482277399164715118..comments2014-08-17T09:30:19.334-07:00Comments on A Neighborhood of Infinity: Why isn't ListT [] a monad?Dan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-11295132.post-70155863215785492762008-12-17T01:23:00.000-08:002008-12-17T01:23:00.000-08:00A typo: >a1=1I'm guessing you meant to writ...A typo: <BR/><BR/>>a1=1<BR/><BR/>I'm guessing you meant to write a0=0, a1=a.Alex Rubinsteynhttp://www.blogger.com/profile/04049149415019007603noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-64659253727748673642008-05-12T05:54:00.000-07:002008-05-12T05:54:00.000-07:00I'm a fair bit late here, but here's my $0.02 (or ...I'm a fair bit late here, but here's my $0.02 (or less):<BR/><BR/>It seems to me a valid perspective on the "Set monad" and related issues would be to accept that the given definitions are monads, within the context of the Eq instance. The Monad instance may not be able to constrain the application of the Monad operations, but if (==) isn't defined for "Set a", it's essentially outside the scope of the monad, despite the fact that the typechecker won't slap your hand for it. So, the Set type itself wouldn't qualify as a monad, but its quotient by (==) would.<BR/><BR/>In any case, I think it's important to distinguish between a failure to construct a type-safe implementation of a monad and a failure to construct a monad. Just because it doesn't fit into the Monad type class (or obey the laws) doesn't mean it can't be one, given the right chance.mokusnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-64586539545303570152006-12-15T09:44:00.000-08:002006-12-15T09:44:00.000-08:00Yes, Eq would have to defined to preserve the abst...Yes, Eq would have to defined to preserve the abstraction. E.g., by set differences both ways being empty. And set difference is easy.Lennarthttp://www.blogger.com/profile/07327620522294658036noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-51765683709054176572006-12-15T07:48:00.000-08:002006-12-15T07:48:00.000-08:00Hey, I think you're right and that Set is probably...Hey, I think you're right and that Set is probably is a perfectly decent commutative monad with a suitable definition of Eq. I think ListT Set probably does do what I want, although I haven't tested it yet. I remembered having trouble writing a Set monad ages ago but I realise now that my problems were only about efficiency, not about whether or not it was fundamentally possible.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-62619167084334130212006-12-15T07:39:00.000-08:002006-12-15T07:39:00.000-08:00Ignore my complaint about the lack of ==.Ignore my complaint about the lack of ==.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-48368519475917050622006-12-15T07:34:00.000-08:002006-12-15T07:34:00.000-08:00The obvious problem is that you can't compare thes...The obvious problem is that you can't compare these sets using ==. The second problem is that Set ought to be a commutative monad, which it isn't. If it were commutative, we'd have a pretty construction for free semirings from ListT Set, which we don't. Maybe you have a suggestion for another nice way to make this construction?<br /><br />The suckiness of the implementation is also pretty bad for real applications - and that is actually the real reason I care about this. A while back I tried writing some quantum computation code (which is just a fancy way of saying I wrote some linear algebra code) where I tried to implement vector spaces as a monad. I used something similar to your Set construction where I delayed doing actual work on my vector representation until the last moment (ie. at 'wavefunction collapse'). But for long computations you end up building large intermediate objects, exactly analogous to the way you can find yourself building large 'redundant' lists to represent small sets. Admittedly, none of the examples I tested produced intermediates that caused a performance problem, even for a modest PC, but it's still ugly carrying around all that extra baggage.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-59116804879969971132006-12-15T05:52:00.000-08:002006-12-15T05:52:00.000-08:00So from an implementation perspective my Set type ...So from an implementation perspective my Set type really sucks.<br />But from a mathematical point of view I don't know what you think is wrong with them. They obey all the set axioms you expect, and I don't see why you can't build free semirings with them.<br />This is for the abstract type Set, of course. The concrete type Set has no nice set properties.Lennarthttp://www.blogger.com/profile/07327620522294658036noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-63229913583046342022006-12-14T16:04:00.000-08:002006-12-14T16:04:00.000-08:00But that's not a very satisfying Set monad for all...But that's not a very satisfying Set monad for all sorts of reasons, not not just the fact that you can't use it to build free semirings out of sets and lists like I feel you ought to be able to.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-2673748477489750222006-12-14T14:31:00.000-08:002006-12-14T14:31:00.000-08:00There's no problem making Set a monad if you make ...There's no problem making Set a monad if you make some other sacrifices:<br /><br />module Set(Set, union, intersection, member) where<br /><br />data Set a = Set { unSet :: [a] }<br /><br />instance Monad Set where<br /> return x = Set [x]<br /> Set xs >>= f = Set $ xs >>= unSet . f<br /><br />union :: Set a -> Set a -> Set a<br />union (Set xs) (Set ys) = Set (xs ++ ys)<br /><br />intersection :: (Eq a) => Set a -> Set a -> Set a<br />intersection (Set xs) (Set ys) = Set $ filter (`elem` ys) xs<br /><br />member :: (Eq a) => a -> Set a -> Bool<br />member x (Set xs) = x `elem` xs<br /><br /><br />You can do this many ways. It's only the member function that needs to have a context. (Which is just an indication that it's only member that needs to do any real work.)Lennarthttp://www.blogger.com/profile/07327620522294658036noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-6905820283257255762006-12-14T11:04:00.000-08:002006-12-14T11:04:00.000-08:00Either it's SetT [] or ListT Set, I can never figu...Either it's SetT [] or ListT Set, I can never figure out which way round monad transformers go in my head.<br /><br />BUT, you can't write a Set monad in Haskell. <a href="http://groups.google.com/group/comp.lang.functional/browse_thread/thread/5db5c013d529b653/e10290b2511c65f0">Here</a>'s a discussion about it. In fact, many of the standard mathematical examples of monads can't be implemented nicely in Haskell.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-27676289114563178122006-12-14T08:50:00.000-08:002006-12-14T08:50:00.000-08:00So basically, if I read the argument correctly, yo...So basically, if I read the argument correctly, you would get a monad if you instead of using ListT [] constructed a SetT-monad, using some sort of set implementation (sorted lists, balanced tree, whatever), and then used SetT [] for the free semiring?Mikaelhttp://www.blogger.com/profile/00008302080954798496noreply@blogger.com