<p>Convenience aside, doesn't the functor instance conceptually violate some sort of law?</p>
<p>fmap (const 1) someSet</p>
<p>The entire shape of the set changes.</p>
<p>fmap (g . h) = fmap g . fmap h</p>
<p>This law wouldn't hold given the following contrived ord instance</p>
<p>data Foo = Foo { a, b :: Int }<br>
instance Ord Foo where<br>
compare = compare `on` a</p>
<p>Given functions</p>
<p>h foo = foo { a = 1 }<br>
g foo = foo { a = b foo }</p>
<p>Does this library address this? If so, how? If not, then you'd best note it in the docs.</p>
<p><blockquote type="cite">On Jun 15, 2012 6:42 PM, "George Giorgidze" <<a href="mailto:giorgidze@gmail.com" target="_blank">giorgidze@gmail.com</a>> wrote:<br><br>I would like to announce the first release of the set-monad library.<br>
<br>
On Hackage: <a href="http://hackage.haskell.org/package/set-monad" target="_blank">http://hackage.haskell.org/package/set-monad</a><br>
<br>
The set-monad library exports the Set abstract data type and<br>
set-manipulating functions. These functions behave exactly as their<br>
namesakes from the Data.Set module of the containers library. In<br>
addition, the set-monad library extends Data.Set by providing Functor,<br>
Applicative, Alternative, Monad, and MonadPlus instances for sets.<br>
<br>
In other words, you can use the set-monad library as a drop-in<br>
replacement for the Data.Set module of the containers library and, in<br>
addition, you will also get the aforementioned instances which are not<br>
available in the containers package.<br>
<br>
It is not possible to directly implement instances for the<br>
aforementioned standard Haskell type classes for the Set data type<br>
from the containers library. This is because the key operations map<br>
and union, are constrained with Ord as follows.<br>
<br>
map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b<br>
union :: (Ord a) => Set a -> Set a -> Set a<br>
<br>
The set-monad library provides the type class instances by wrapping<br>
the constrained Set type into a data type that has unconstrained<br>
constructors corresponding to monadic combinators. The data type<br>
constructors that represent monadic combinators are evaluated with a<br>
constrained run function. This elevates the need to use the<br>
constraints in the instance definitions (this is what prevents a<br>
direct definition). The wrapping and unwrapping happens internally in<br>
the library and does not affect its interface.<br>
<br>
For details, see the rather compact definitions of the run function<br>
and type class instances. The left identity and associativity monad<br>
laws play a crucial role in the definition of the run function. The<br>
rest of the code should be self explanatory.<br>
<br>
The technique is not new. This library was inspired by [1]. To my<br>
knowledge, the original, systematic presentation of the idea to<br>
represent monadic combinators as data is given in [2]. There is also a<br>
Haskell library that provides a generic infrastructure for the<br>
aforementioned wrapping and unwrapping [3].<br>
<br>
The set-monad library is particularly useful for writing set-oriented<br>
code using the do and/or monad comprehension notations. For example,<br>
the following definitions now type check.<br>
<br>
s1 :: Set (Int,Int)<br>
s1 = do a <- fromList [1 .. 4]<br>
b <- fromList [1 .. 4]<br>
return (a,b)<br>
<br>
-- with -XMonadComprehensions<br>
s2 :: Set (Int,Int)<br>
s2 = [ (a,b) | (a,b) <- s1, even a, even b ]<br>
<br>
s3 :: Set Int<br>
s3 = fmap (+1) (fromList [1 .. 4])<br>
<br>
As noted in [1], the implementation technique can be used for monadic<br>
libraries and EDSLs with restricted types (compiled EDSLs often<br>
restrict the types that they can handle). Haskell's standard monad<br>
type class can be used for restricted monad instances. There is no<br>
need to resort to GHC extensions that rebind the standard monadic<br>
combinators with the library or EDSL specific ones.<br>
<br>
[1] CSDL Blog: The home of applied functional programming at KU. Monad<br>
Reification in Haskell and the Sunroof Javascript compiler.<br>
<a href="http://www.ittc.ku.edu/csdlblog/?p=88" target="_blank">http://www.ittc.ku.edu/csdlblog/?p=88</a><br>
<br>
[2] Chuan-kai Lin. 2006. Programming monads operationally with Unimo.<br>
In Proceedings of the eleventh ACM SIGPLAN International Conference on<br>
Functional Programming (ICFP '06). ACM.<br>
<br>
[3] Heinrich Apfelmus. The operational package.<br>
<a href="http://hackage.haskell.org/package/operational" target="_blank">http://hackage.haskell.org/package/operational</a><br>
<br>
_______________________________________________<br>
Haskell mailing list<br>
<a href="mailto:Haskell@haskell.org" target="_blank">Haskell@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell" target="_blank">http://www.haskell.org/mailman/listinfo/haskell</a><br>
</blockquote></p>