*s~1~*` >>= \ `*x~1~*` -> `*s~2~*` >>= \ `*x~2~*` -> `…` -> `*s~n~*` >>= \ `*x~n~*` -> return `*r*

where the *s~i~* would be non-monadic expressions of type `Set`. The existence of a normal form would follow from the monad laws. We define a type `UniSet` of such normal forms: > data UniSet a where > > ReturnSet :: a -> UniSet a > > AtmBindSet :: Set a -> (a -> UniSet b) -> UniSet b We can make `UniSet` an instance of `Monad` where the monad operations build expressions and normalize them on the fly: > instance Monad UniSet where > > return a = ReturnSet a > > ReturnSet a >>= f = f a > AtmBindSet sa h >>= f = AtmBindSet sa h' where > > h' a = h a >>= f Note that these monad operations are analogous to operations on lists, with `return` corresponding to singleton construction and `(>>=)` corresponding to concatenation. Normalization happens in `(>>=)` by applying the left-identity and the associativity law for monads. We can use `UniSet` as an alternative set type, representing a set by a normal form that evaluates to this set. This way, we get a set type that is an instance of `Monad`. For this to be sane, we have to hide the data constructors of `UniSet`, so that different normal forms that evaluate to the same set cannot be distinguished. Now we need functions that convert between `Set` and `UniSet`. Conversion from `Set` to `UniSet` is simple: > toUniSet :: Set a -> UniSet a > toUniSet sa = AtmBindSet sa ReturnSet Conversion from `UniSet` to `Set` is expression evaluation: > fromUniSet :: Ord a => UniSet a -> Set a > fromUniSet (ReturnSet a) = returnSet a > fromUniSet (AtmBindSet sa h) = bindSet sa g where > > g a = fromUniSet (h a) The type of `fromUniSet` constrains the element type to be an instance of `Ord`. This single constraint is enough to make all invocations of `bindSet` throughout the conversion legal. The reason is our use of normal forms. Since normal forms are “right-leaning”, all applications of `(>>=)` in them have the same result type as the whole expression. The multiset monad ================== Let us now look at a different monad, the multiset monad. We represent a multiset as a function that maps each value of the element type to its multiplicity in the multiset, with a multiplicity of zero denoting absence of this value: > newtype MSet a = MSet { mult :: a -> Natural } Now we define the *return* operation: > returnMSet :: Eq a => a -> MSet a > returnMSet a = MSet ma where > > ma b | a == b = 1 > | otherwise = 0 For defining the *bind* operation, we need to define a class `Finite` of finite types whose sole method enumerates all the values of the respective type: > class Finite a where > > values :: [a] The implementation of the *bind* operation is as follows: > bindMSet :: Finite a => MSet a -> (a -> MSet b) -> MSet b > bindMSet msa g = MSet mb where > > mb b = sum [mult msa a * mult (g a) b | a <- values] Note that the multiset monad differs from the set monad in its use of constraints. The set monad imposes a constraint on the result element type of *bind*, while the multiset monad imposes a constraint on the first argument element type of *bind* and another constraint on the result element type of *return*. Like in the case of sets, we define a type of monadic normal forms: > data UniMSet a where > > ReturnMSet :: a -> UniMSet a > > AtmBindMSet :: Finite a => > MSet a -> (a -> UniMSet b) -> UniMSet b The key difference to `UniSet` is that `UniMSet` involves the constraint of the *bind* operation, so that normal forms must respect this constraint. Without this restriction, it would not be possible to evaluate normal forms later. The `Monad`–`UniMSet` instance declaration is analogous to the `Monad`–`UniSet` instance declaration: > instance Monad UniMSet where > > return a = ReturnMSet a > > ReturnMSet a >>= f = f a > AtmBindMSet msa h >>= f = AtmBindMSet msa h' where > > h' a = h a >>= f Now we define conversion from `MSet` to `UniMSet`: > toUniMSet :: Finite a => MSet a -> UniMSet a > toUniMSet msa = AtmBindMSet msa ReturnMSet Note that we need to constrain the element type in order to fulfill the constraint incorporated into the `UniMSet` type. Finally, we define conversion from `UniMSet` to `MSet`: > fromUniMSet :: Eq a => UniMSet a -> MSet a > fromUniMSet (ReturnMSet a) = returnMSet a > fromUniMSet (AtmBindMSet msa h) = bindMSet msa g where > > g a = fromUniMSet (h a) Here we need to impose an `Eq` constraint on the element type. Note that this single constraint is enough to make all invocations of `returnMSet` throughout the conversion legal. The reason is again our use of normal forms. A generic solution ================== The solutions to the constrained-monad problem for sets and multisets are very similar. It is certainly not good if we have to write almost the same code for every new constrained monad that we want to make accessible via the `Monad` class. Therefore, we define a generic type that covers all such monads: > data UniMonad c t a where > > Return :: a -> UniMonad c t a > > AtmBind :: c a => > t a -> (a -> UniMonad c t b) -> UniMonad c t b The parameter `t` of `UniMonad` is the underlying data type, like `Set` or `MSet`, and the parameter `c` is the constraint that has to be imposed on the type parameter of the first argument of the *bind* operation. For every `c` and `t`, we make `UniMonad c t` an instance of `Monad`: > instance Monad (UniMonad c t) where > > return a = Return a > > Return a >>= f = f a > AtmBind ta h >>= f = AtmBind ta h' where > > h' a = h a >>= f We define a function `lift` that converts from the underlying data type to `UniMonad` and thus generalizes `toUniSet` and `toUniMSet`: > lift :: c a => t a -> UniMonad c t a > lift ta = AtmBind ta Return Evaluation of normal forms is just folding with the *return* and *bind* operations of the underlying data type. Therefore, we implement a fold operator for `UniMonad`: > fold :: (a -> r) > -> (forall a . c a => t a -> (a -> r) -> r) > -> UniMonad c t a > -> r > fold return _ (Return a) = return a > fold return atmBind (AtmBind ta h) = atmBind ta g where > > g a = fold return atmBind (h a) Note that `fold` does not need to deal with constraints, neither with constraints on the result type parameter of *return* (like `Eq` in the case of `MSet`), nor with constraints on the result type parameter of *bind* (like `Ord` in the case of `Set`). This is because `fold` works with any result type `r`. Now let us implement `Monad`-compatible sets and multisets based on `UniMonad`. In the case of sets, we face the problem that `UniMonad` takes a constraint for the type parameter of the first *bind* argument, but `bindSet` does not have such a constraint. To solve this issue, we introduce a type class `Unconstrained` of which every type is an instance: > class Unconstrained a > > instance Unconstrained a The implementation of `Monad`-compatible sets is now straightforward: > type UniMonadSet = UniMonad Unconstrained Set > > toUniMonadSet :: Set a -> UniMonadSet a > toUniMonadSet = lift > > fromUniMonadSet :: Ord a => UniMonadSet a -> Set a > fromUniMonadSet = fold returnSet bindSet The implementation of `Monad`-compatible multisets does not need any utility definitions, but can be given right away: > type UniMonadMSet = UniMonad Finite MSet > > toUniMonadMSet :: Finite a => MSet a -> UniMonadMSet a > toUniMonadMSet = lift > > fromUniMonadMSet :: Eq a => UniMonadMSet a -> MSet a > fromUniMonadMSet = fold returnMSet bindMSet