Hi Oleg, Thank you for this wonderful detailed solution!
I was attempting to turn this into a small library and wanted to avoid exporting unwrap. I defined: polyToMonoid' = unwrap . polyToMonoid and then GHC told me: No instance for (PolyVariadic a (WMonoid m)) arising from a use of `polyToMonoid' at Data\PolyToMonoid.hs:27:24-36 Possible fix: add an instance declaration for (PolyVariadic a (WMonoid m)) Is there a type signature I can assign to polyToMonoid' to get this to work? Or will it always be necessary to export unwrap as well? Kevin On Oct 9, 5:04 am, o...@okmij.org wrote: > Kevin Jardine wrote: > > instead of passing around lists of values with these related types, I > > created a polyvariadic function polyToString... > > I finally figured out how to do this, but it was a bit harder to > > figure this out than I expected, and I was wondering if it might be > > possible to create a small utility library to help other developers do > > this. > > It seems to me that in the general case, we would be dealing with a > > Monoid rather than a list of strings. We could have a toMonoid > > function and then return > > > polyToMonoid value1 value2 ... valueN = > > > (toMonoid value1) `mappend` (toMonoid value2) 'mappend' ... (toMonoid > > valueN) > > So I tried writing the following code but GHC said it had undecidable > > instances. > > Generally speaking, we should not be afraid of undecidable instances: > it is a sufficient criterion for terminating type checking but it is > not a necessary one. A longer argument can be found at > http://okmij.org/ftp/Haskell/types.html#undecidable-inst-defense > > However, the posted code has deeper problems, I'm afraid. First, let > us look at the case of Strings: > > > class PolyVariadic p where > > polyToMonoid' :: String -> p > > > instance PolyVariadic String where > > polyToMonoid' acc = acc > > > instance (Show a, PolyVariadic r) => PolyVariadic (a->r) where > > polyToMonoid' acc = \a -> polyToMonoid' (acc ++ show a) > > > polyToMonoid :: PolyVariadic p => p > > polyToMonoid = polyToMonoid' mempty > > > test1 = putStrLn $ polyToMonoid True () (Just (5::Int)) > > *M> test1 > True()Just 5 > > Modulo the TypeSynonymInstances extension, it is Haskell98. If we now > generalize it to arbitrary monoids rather than a mere String, we face > several problems. First of all, if we re-write the first instance as > > > instance Monoid r => PolyVariadic r where > > polyToMonoid' acc = acc > > we make it overlap with the second instance: the type variable 'r' may > be instantiated to the arrow type a->r'. Now we need a more > problematic overlapping instances extension. The problem is deeper > however: an arrow type could possibly be an instance of Monoid (for > example, functions of the type Int->Int form a monoid with mempty=id, > mappend=(.)). If polyToMonoid appears in the context requiring a > function type, how could type checker choose the instance of > Polyvariadic? > > The second problem with the posted code > > > class Monoidable a where > > toMonoid :: Monoid r => a -> r > > is that toMonoid has too `strong' a signature. Suppose we have an > instance > > > instance Monoidable String where > > toMonoid = \str -> ??? > > It means that no matter which monoid the programmer may give to us, we > promise to inject a string into it. We have no idea about the details > of the monoid. It means that the only thing we could do (short of > divergence) is to return mempty. That is not too useful. > > We have little choice but to parametrise Monoidable as well as > Polyvariadic with the type of the monoid. To avoid overlapping and > disambiguate the contexts, we use the newtype trick. Here is the > complete code. It turns out, no undecidable instances are needed. > > > > > {-# LANGUAGE TypeSynonymInstances #-} > > {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} > > > module M where > > > import Data.Monoid > > > newtype WMonoid m = WMonoid{unwrap :: m} > > > class Monoid m => Monoidable a m where > > toMonoid :: a -> m > > > class Monoid m => PolyVariadic m p where > > polyToMonoid :: m -> p > > > instance Monoid m => PolyVariadic m (WMonoid m) where > > polyToMonoid acc = WMonoid acc > > > instance (Monoidable a m, PolyVariadic m r) => PolyVariadic m (a->r) where > > polyToMonoid acc = \a -> polyToMonoid (acc `mappend` toMonoid a) > > > instance Show a => Monoidable a String where > > toMonoid = show > > > test2 = putStrLn $ unwrap $ polyToMonoid "" True () (Just (5::Int)) > > The remaining problem is how to tell polyToMonoid which monoid we > want. It seems simpler just to pass the appropriately specialized > mempty method as the first argument, as shown in test2. > > Granted, a more elegant solution would be a parametrized module > (functor) like those in Agda or ML: > > module type PolyM = > functor(M:: sig type m val mempty :: m val mappend :: m -> m -> m end) = > struct > class Monoidable a where > toMonoid :: a -> m > class PolyVariadic p where > polyToMonoid :: m -> p > .etc > end > > The shown solution is essentially the encoding of the above functor. > > _______________________________________________ > Haskell-Cafe mailing list > haskell-c...@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe