[Haskell-cafe] Re: Polyvariadic functions operating with a monoid
Kevin Jardine
kevinjardine at gmail.com
Sat Oct 9 06:22:17 EDT 2010
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... at 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... at haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe
More information about the Haskell-Cafe
mailing list