Monad instance for partially applied type constructor?
Hi, I have the following code: {-# LANGUAGE TypeSynonymInstances #-} data Vect k b = V [(k,b)] -- vector space over field k with basis b -- for example, V [(5, E 1), (7, E 2)] would represent the vector 5 e1 + 7 e2 data Monomial v = M [(v,Int)] -- monomials over variables v -- for example, M [(A,3), (B,5)] would represent the monomial a^3 b^5 type Poly k v = Vect k (Monomial v) -- multivariate polynomials over field k and variables v instance Monad (Poly k) where return v = V [(1, M [(v,1)])] p >>= f = ... -- variable substitution So my thinking is: 1. The Monad type class is for one parameter type constructors (eg [], IO) 2. Poly is a two-parameter type constructor 3. So Poly k is a one-parameter type constructor 4. What I'm trying to express, that polynomials over field k are a monad, is true. However, GHC 6.12.2 complains: Type synonym `Poly' should have 2 arguments, but has been given 1 In the instance declaration for `Monad (Poly k)' What is going wrong?
Maybe -XLiberalTypeSynonyms is an option:
http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/data-type-extensions...
On 29 September 2010 20:08, DavidA
Hi,
I have the following code:
{-# LANGUAGE TypeSynonymInstances #-}
data Vect k b = V [(k,b)] -- vector space over field k with basis b -- for example, V [(5, E 1), (7, E 2)] would represent the vector 5 e1 + 7 e2
data Monomial v = M [(v,Int)] -- monomials over variables v -- for example, M [(A,3), (B,5)] would represent the monomial a^3 b^5
type Poly k v = Vect k (Monomial v) -- multivariate polynomials over field k and variables v
instance Monad (Poly k) where return v = V [(1, M [(v,1)])] p >>= f = ... -- variable substitution
So my thinking is: 1. The Monad type class is for one parameter type constructors (eg [], IO) 2. Poly is a two-parameter type constructor 3. So Poly k is a one-parameter type constructor 4. What I'm trying to express, that polynomials over field k are a monad, is true.
However, GHC 6.12.2 complains:
Type synonym `Poly' should have 2 arguments, but has been given 1 In the instance declaration for `Monad (Poly k)'
What is going wrong?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Wed, Sep 29, 2010 at 11:08 AM, DavidA
Hi,
I have the following code:
{-# LANGUAGE TypeSynonymInstances #-}
data Vect k b = V [(k,b)] -- vector space over field k with basis b -- for example, V [(5, E 1), (7, E 2)] would represent the vector 5 e1 + 7 e2
data Monomial v = M [(v,Int)] -- monomials over variables v -- for example, M [(A,3), (B,5)] would represent the monomial a^3 b^5
type Poly k v = Vect k (Monomial v) -- multivariate polynomials over field k and variables v
instance Monad (Poly k) where return v = V [(1, M [(v,1)])] p >>= f = ... -- variable substitution
So my thinking is: 1. The Monad type class is for one parameter type constructors (eg [], IO) 2. Poly is a two-parameter type constructor 3. So Poly k is a one-parameter type constructor 4. What I'm trying to express, that polynomials over field k are a monad, is true.
However, GHC 6.12.2 complains:
Type synonym `Poly' should have 2 arguments, but has been given 1 In the instance declaration for `Monad (Poly k)'
What is going wrong?
Haskell doesn't have true type functions; what you are really saying is instance Monad (\v -> Vect k (Monomial v)) TypeSynonymInstances just lets you write stuff like this type Foo = [Int] instance C Foo where ... instead of type Foo = [Int] instance C [Int] where ... But it doesn't let you partially apply the type synonym. On the other hand, if you did this: newtype Compose f g a = O { unO :: f (g a) } type Poly k = Compose (Vect k) Monomial instance Monad (Poly k) where ... would work, but now you have to wrap/unwrap Compose in the instance definition. -- ryan
On 29 September 2010 20:48, Ryan Ingram
But it doesn't let you partially apply the type synonym.
On the other hand, if you did this:
newtype Compose f g a = O { unO :: f (g a) } type Poly k = Compose (Vect k) Monomial
instance Monad (Poly k) where ...
would work, but now you have to wrap/unwrap Compose in the instance definition.
LiberalTypeSynonyms lets you partially apply type synonyms.
On Wednesday 29 September 2010 2:52:21 pm Christopher Done wrote:
LiberalTypeSynonyms lets you partially apply type synonyms.
Not in general. LiberalTypeSynonyms only allows synonyms to be partially applied when expansions of other type synonyms will eventually cause them to become fully applied (or discarded, probably). So, for instance: type Foo a = (a, a) type Bar f = f Int Bar Foo ==> Foo Int ==> (Int, Int) -- valid It does not make partially applied synonyms first class, such that they'd be able to be made instances, or parameters to datatypes, etc. -- Dan
Ryan Ingram
Haskell doesn't have true type functions; what you are really saying is
instance Monad (\v -> Vect k (Monomial v))
Yes, that is exactly what I am trying to say. And since I'm not allowed to say it like that, I was trying to say it using a type synonym parameterised over v instead. It appears that GHC won't let you use partially applied type synonyms as type constructors for instance declarations. Is this simply because the GHC developers didn't think anyone would want to, or is there some theoretical reason why it's hard, or a bad idea?
On Wednesday 29 September 2010 23:15:14, DavidA wrote:
Ryan Ingram
writes: Haskell doesn't have true type functions; what you are really saying is
instance Monad (\v -> Vect k (Monomial v))
Yes, that is exactly what I am trying to say. And since I'm not allowed to say it like that, I was trying to say it using a type synonym parameterised over v instead. It appears that GHC won't let you use partially applied type synonyms as type constructors for instance declarations. Is this simply because the GHC developers didn't think anyone would want to, or is there some theoretical reason why it's hard, or a bad idea?
I think there was a theoretical reason why that isn't allowed (making type inference undecidable? I don't remember, I don't recall ...). For your problem, maybe data Vect k m b = Vect [(k, m b)] instance Monad (Vect k Monomial) where ... is an option?
David, Ryan Ingram wrote:
Haskell doesn't have true type functions; what you are really saying is
instance Monad (\v -> Vect k (Monomial v))
Daniel Fischer wrote:
I think there was a theoretical reason why that isn't allowed (making type inference undecidable? I don't remember, I don't recall ...).
Indeed: type inference in the presence of type-level lambdas requires higher-order unification, which is undecidable [1]. Cheers, Stefan [1] Gérard P. Huet: The Undecidability of Unification in Third Order Logic Information and Control 22(3): 257-267 (1973)
It's hard. Here's a simple example:
type Foo f = f Int
class C (f :: (* -> *) -> *) where
thingy :: f [] -> f IO
-- Should this ever typecheck? I would say no; there's no way to
unify f [] with [Int].
callThingy :: [Int] -> IO Int
callThingy = thingy
-- but what if you say this?
instance C Foo where
-- thingy :: Foo [] -> Foo IO
-- therefore,
-- thingy :: [Int] -> IO Int
thingy (x:_) = return x
Basically, allowing instances for type functions requires you to
*un-apply* any type functions to attempt to do instance selection.
-- ryan
On Wed, Sep 29, 2010 at 2:15 PM, DavidA
Ryan Ingram
writes: Haskell doesn't have true type functions; what you are really saying is
instance Monad (\v -> Vect k (Monomial v))
Yes, that is exactly what I am trying to say. And since I'm not allowed to say it like that, I was trying to say it using a type synonym parameterised over v instead. It appears that GHC won't let you use partially applied type synonyms as type constructors for instance declarations. Is this simply because the GHC developers didn't think anyone would want to, or is there some theoretical reason why it's hard, or a bad idea?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Wed, Sep 29, 2010 at 11:15 PM, DavidA
Ryan Ingram
writes: Haskell doesn't have true type functions; what you are really saying is
instance Monad (\v -> Vect k (Monomial v))
Yes, that is exactly what I am trying to say. And since I'm not allowed to say it like that, I was trying to say it using a type synonym parameterised over v instead. It appears that GHC won't let you use partially applied type synonyms as type constructors for instance declarations. Is this simply because the GHC developers didn't think anyone would want to, or is there some theoretical reason why it's hard, or a bad idea?
The version of the lambda calculus (System Fc) GHC uses for its internal representation doesn't support lambdas at the type level. I've bumped up against this limitation myself, and don't know of any way to 'cheat' it (which makes sense, given that it's so fundamental). You can use newtypes, and recursive definitions (sometimes with overlap and/or fundeps) work for some cases, though they can get quite nasty in the harder ones. I have to assume upgrading the type system to support this would highly nontrivial, though I don't know exactly how high, nor what drawbacks there might be.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Work is punishment for failing to procrastinate effectively.
On 09/29/2010 02:15 PM, DavidA wrote:
instance Monad (\v -> Vect k (Monomial v))
Yes, that is exactly what I am trying to say. And since I'm not allowed to say it like that, I was trying to say it using a type synonym parameterised over v instead.
Why not: instance Monad ((->) Vect k (Monomial v))
On 09/29/2010 09:13 PM, Alexander Solla wrote:
On 09/29/2010 02:15 PM, DavidA wrote:
instance Monad (\v -> Vect k (Monomial v))
Yes, that is exactly what I am trying to say. And since I'm not allowed to say it like that, I was trying to say it using a type synonym parameterised over v instead.
Why not:
instance Monad ((->) Vect k (Monomial v))
Sorry, I guess this is a bit off. I don't think you "really" want a monad. I think you want something like the dual to the reader monad (i.e, a comonad)
On Wed, Sep 29, 2010 at 9:13 PM, Alexander Solla
On 09/29/2010 02:15 PM, DavidA wrote:
instance Monad (\v -> Vect k (Monomial v))
Yes, that is exactly what I am trying to say. And since I'm not allowed to say it like that, I was trying to say it using a type synonym parameterised over v instead.
Why not:
instance Monad ((->) Vect k (Monomial v))
No, what he's trying to say is
instance Monad (Vect k . Monomial)
with some type-level composition for . which would give these signatures:
return :: forall a. a -> Vect k (Monomial a) (>>=) :: forall a b. Vect k (Monomial a) -> (a -> Vect k (Monomial b)) -> Vect k (Monomial b)
Notice that the "forall" variables are inside parentheses in the type; this is what Haskell doesn't allow. Of course you can
newtype VectMonomial k a = VM { unVM :: Vect k (Monomial a) } instance Monad (VectMonomial k) where ...
But now you need to wrap/unwrap using VM/unVM. -- ryan
participants (8)
-
Alexander Solla -
Christopher Done -
Dan Doel -
Daniel Fischer -
DavidA -
Gábor Lehel -
Ryan Ingram -
Stefan Holdermans