Problems inferring instances

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Problems inferring instances

dcmorse+haskell@gmail.com
Learning from the example of "read" and also Real World Haskell, I
come across the idea to overload my function's return types. Trying to
think of an application for this, I've always wanted to write ==
applications like in Icon, that is

a === b === c means a == b && b == c.

This requires === to sense what context it is called in. If it's being
called for a Boolean value, it needs to return a Boolean value. If
it's being called as a parameter to another === application, then it
needs to somehow remember both it's truthiness and if true what value
its already seen.

The idea is to eventually expand this to be able to write

a >== b >== c

...but one thing at a time!

My plan of attack is to write a typeclass:
class Chain a b c where
 (==) :: a -> b -> c
First check: Turned on -fglasgowexts to allow multiple parameters to
typeclasses.


Then write instances for the various contexts in which == might be
applied. For boolean return values there are three instances:

instance Eq a => Chain a a Bool ...
 example: 5 == 4
instance Eq a => Chain (Valid a) a Bool
 example:  rightmost == in (5==4)==3
instance Eq a => Chain a (Valid a) Bool
 example: leftmost == in 5==(4==3)

 Sidebar: Valid is just an imitation of Maybe:
 data Valid a = Value a | Fail deriving (Show)

But back to ==, the interesting part is the times when one senses
we're in a context of comparing more values, for example, the left ==
in (x==y)==z.

instance Eq a => Chain a a (Valid a)
instance Eq a => Chain (Valid a) a (Valid a)
instance Eq a => Chain a (Valid a) (Valid a)

To test out this implementation I write a test function:
test2 :: Eq a => a -> a -> Bool
test2 a b = a === b
and this works as expected.

The problem comes when chainging the ===s together, I have to
spoon-feed the compiler the inferred type:


-- compiling this causes an error
test3choke :: Eq a => a -> a -> a -> Bool
test3choke a b c = a === b === c

The error text:

 [1 of 1] Compiling ME               ( ME.hs, interpreted )

 ME.hs:63:19:
     Could not deduce (Chain a a c) from the context (Eq a)
       arising from use of `===' at ME.hs:63:19-25
     Possible fix:
       add (Chain a a c) to the type signature(s) for `test3choke'
     In the first argument of `(===)', namely `a === b'
     In the expression: (a === b) === c
     In the definition of `test3choke':
         test3choke a b c = (a === b) === c

 ME.hs:63:19:
     Could not deduce (Chain c a Bool) from the context (Eq a)
       arising from use of `===' at ME.hs:63:19-31
     Possible fix:
       add (Chain c a Bool) to the type signature(s) for `test3choke'
       or add an instance declaration for (Chain c a Bool)
     In the expression: (a === b) === c
     In the definition of `test3choke':
         test3choke a b c = (a === b) === c
 Failed, modules loaded: none.


-- but spoon-feeding it the types will work
test3Int  :: Int -> Int -> Int -> Bool
test3Int  a b c = ((a === b) :: Valid Int) === c

So it seems that the compiler is not doing instance inference the same
way it does type inference. This is frustrating because the output of
the parenthesiszed a === b can only be either of type Bool or Valid a,
and the second argument of the outer === has to have the same type,
which will force it to Valid a in most cases (Bool being an
interesting exception).

Is there some way to goad the compiler forward on this one, or is this
the wrong approach altogether?

Attachment: http://www.osaurus.us/~dm/tmp/ME.hs
Reply | Threaded
Open this post in threaded view
|

Problems inferring instances

Dave Bayer
Here's a very indirect answer, more a hunch:

I'm not sure how, but what you're trying to do reminds me of  
Control.Applicative. Go take a look at the documentation and/or source  
code for that library, then follow the link to

        Applicative Programming with Effects
        Conor McBride and Ross Paterson
        http://www.soi.city.ac.uk/~ross/papers/Applicative.html

which is one of the most beautiful papers ever written on Haskell.  
Even if I'm sending you on a wild goose chase, you'll enjoy the paper.

I've had similar monumental struggles trying to push the type system  
past my understanding of how it works. I find that invariably, if I  
roll back one click on my ambitions, type "darcs revert", step outside  
for 30 seconds, then what I want to do works without incident on the  
next try. A good example of this is the "wrapper" class Sum in  
Data.Monoid. You'd think that one could just tell the type system that  
a Num is a Monoid, but the type system _really_ likes something to  
chew on, hence the wrapper. I spent way too long contemplating GHC  
error messages proposing the option -XLetGravityFailButDontBlameUs,  
before accepting that if there was a better way, it would be in the  
library code.

So the key to maintaining momentum as a Haskell beginner is to see the  
simplification, one-click compromise that makes your obstacle trivial.  
Here, if I were you I'd first write your code for practice with the  
left- (or right-?) most === a different operator. By analogy with  
Applicative, or with the . . . . $ pattern one sees everywhere when  
composing. Then maybe it will be clear how to write it the way you want.

On Jan 5, 2009, at 6:40 PM, [hidden email] wrote:

> Learning from the example of "read" and also Real World Haskell, I
> come across the idea to overload my function's return types. Trying to
> think of an application for this, I've always wanted to write ==
> applications like in Icon, that is
>
> a === b === c means a == b && b == c.
Reply | Threaded
Open this post in threaded view
|

Problems inferring instances

Brandon S Allbery KF8NH
In reply to this post by dcmorse+haskell@gmail.com

On 2009 Jan 5, at 21:40, [hidden email] wrote:

> Learning from the example of "read" and also Real World Haskell, I
> come across the idea to overload my function's return types. Trying to
> think of an application for this, I've always wanted to write ==
> applications like in Icon, that is
>
> a === b === c means a == b && b == c.
>
> This requires === to sense what context it is called in. If it's being
> called for a Boolean value, it needs to return a Boolean value. If
> it's being called as a parameter to another === application, then it
> needs to somehow remember both it's truthiness and if true what value
> its already seen.

My thought is that Icon's notion of failure as an out-of-band result  
is best captured by the Monad instance for Maybe (or, perhaps more  
generally, MonadZero or whatever we're going to call it this time  
around; at the moment that means Monad).  Unfortunately, this can't be  
made especially clean:  given

 > (<==) :: Eq a => a -> a -> m Bool
 > a <== b = if a <= b then b else fail ">"

which causes -1 <== x <== 1 (say) to do the right thing, you have to  
either escape the monad to use it as a comparison or create a lifted  
if-then-else.

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [hidden email]
system administrator [openafs,heimdal,too many hats] [hidden email]
electrical and computer engineering, carnegie mellon university    KF8NH