[Haskell-cafe] Re: Polyvariadic functions operating with a monoid

[Kevin Jardine]

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