Haskell: Encouraging GHC to Derive the Right Intermediate Type

Question

I thought it would be neat to allow arbitrary matching in Haskell, so that you could perform simple range checks, for example:

x <= y < z 

And more complicated things like

 x /= y < z == a 

If the above two are semantically equivalent

 x <= y && y < z x /= y && y < z && z == a 

Just see if I can make the syntax work.

So, I got most of the way using a couple of type classes:

 {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} module ChainedOrd where import Prelude hiding ((<), (<=), (>), (>=), (==), (/=)) class Booly va where truthy :: v -> a falsy :: v -> a instance Booly a Bool where truthy = const True falsy = const False instance Booly a (Maybe a) where truthy = Just falsy = const Nothing class ChainedOrd ab where (<),(>),(<=),(>=),(==),(/=) :: (Booly bc) => a -> b -> c infixl 4 < infixl 4 > infixl 4 <= infixl 4 >= infixl 4 == infixl 4 /= instance Ord a => ChainedOrd aa where x < y = case compare xy of LT -> truthy y ; _ -> falsy y x > y = case compare xy of GT -> truthy y ; _ -> falsy y x <= y = case compare xy of GT -> falsy y ; _ -> truthy y x >= y = case compare xy of LT -> falsy y ; _ -> truthy y x == y = case compare xy of EQ -> truthy y ; _ -> falsy y x /= y = case compare xy of EQ -> falsy y ; _ -> truthy y instance Ord a => ChainedOrd (Maybe a) a where Just x < y = case compare xy of LT -> truthy y ; _ -> falsy y Nothing < y = falsy y Just x > y = case compare xy of GT -> truthy y ; _ -> falsy y Nothing > y = falsy y Just x <= y = case compare xy of GT -> falsy y ; _ -> truthy y Nothing <= y = falsy y Just x >= y = case compare xy of LT -> falsy y ; _ -> truthy y Nothing >= y = falsy y Just x == y = case compare xy of EQ -> truthy y ; _ -> falsy y Nothing == y = falsy y Just x /= y = case compare xy of EQ -> falsy y ; _ -> truthy y Nothing /= y = falsy y 

Which compiles fine, but not exactly like chaining due to a problem of intermediate types.

 -- works checkRange1 :: Ord a => a -> a -> a -> Bool checkRange1 xyz = x `lem` y <= z where lem :: Ord a => a -> a -> Maybe a lem = (<=) -- works checkRange2 :: Ord a => a -> a -> a -> Bool checkRange2 xyz = (x <= y) `leb` z where leb :: Ord a => Maybe a -> a -> Bool leb = (<=) 

checkRange1 and checkRange2 work fine, because both of them set a limit on the intermediate type (either as a result of the first comparison or as an argument of the second).

 -- error checkRange3 :: Ord a => a -> a -> a -> Bool checkRange3 xyz = (x <= y) <= z 

When I try to let the compiler infer an intermediate type, however, it barks at me.

 ChainedOrd.hs:64:30: Ambiguous type variable `a0' in the constraints: (ChainedOrd a0 a) arising from a use of `<=' at ChainedOrd.hs:64:30-31 (Booly a a0) arising from a use of `<=' at ChainedOrd.hs:64:24-25 Probable fix: add a type signature that fixes these type variable(s) In the expression: (x <= y) <= z In an equation for `checkRange3': checkRange3 xyz = (x <= y) <= z 

Is there any way to convince the compiler that he should use Maybe a as an intermediate type a0 satisifying Booly a a0, ChainedOrd a0 a , since this is the only instance he knows about?

Otherwise, is there any other way I can make an arbitrary comparison chain?

Answer 1

 infixl 4 ==? class ChainedEq ab where (==?) :: a -> b -> Maybe b instance (Eq a) => ChainedEq (Maybe a) a where x ==? y = if x == Just y then x else Nothing instance (Eq a) => ChainedEq aa where x ==? y = if x == y then Just x else Nothing unChain :: Maybe a -> Bool unChain Nothing = False unChain (Just _) = True test :: Int -> Int -> Int -> Bool test xyz = unChain $ x ==? y ==? z 

Answer 2

There are ways to tell the compiler which type to use,

 checkRange4 xyz = ((x <= y) `asTypeOf` Just x) <= z 

or you can use ScopedTypeVariables , bring the type variable into scope and put the type label on x <= y . But you cannot tell the compiler to use only those instances that he knows about. The compiler works on the principle of an open world, other instances can be defined, and the code should work, if any, and fall within the scope. Therefore, everything you do will be more awkward than

 checkRange5 xyz = x <= y && y <= z 

Answer 3

Here is how I would do it:

 {-# LANGUAGE NoMonomorphismRestriction #-} data Chain ve = Link { evaluation :: e , val :: v , next :: Chain ve } | Start { val :: v } liftChain :: (a -> a -> b) -> Chain ab -> a -> Chain ab liftChain f ch x = Link { evaluation = val ch `f` x, val = x, next = ch } (.<) = liftChain (<) (.>) = liftChain (>) (.<=) = liftChain (<=) (.>=) = liftChain (>=) (.==) = liftChain (==) toList :: Chain ve -> [v] toList (Start v) = [v] toList (Link _ vn) = v : toList n toList' :: Chain ve -> [e] toList' (Start _) = [] toList' (Link e _ n) = e : toList' n and' :: Chain v Bool -> Bool and' = and . toList' 

Using:

 ghci> and' $ Start 3 .< 4 .< 7 .== 7 .< 9 .>= 0 .== (2-2) True 

Answer 4

It haunted me that it could not seem expressive without the uncomfortable completion / unpacking functions. What I came up with to allow purely infix expressions:

 {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE TypeFamilies #-} module ChainedComp where infixl 4 ==.. , .==. , ==? data Comp1Chain a = Sofar1OK a | Already1Failed data Comp2Chain a = Sofar2OK a | Already2Failed data Comp3Chain a = Sofar3OK a | Already3Failed -- ... (==..) :: (Eq a) => a -> a -> Comp1Chain a x==..y | x==y = Sofar1OK y | otherwise = Already1Failed class ChainableComp c where type AppendElem c :: * type ChainAfterAppend c :: * (.==.) :: c -> AppendElem c -> ChainAfterAppend c (==?) :: c -> AppendElem c -> Bool instance (Eq a) => ChainableComp (Comp1Chain a) where type AppendElem (Comp1Chain a) = a type ChainAfterAppend (Comp1Chain a) = Comp2Chain a chn.==.y | (Sofar1OK x)<-chn, x==y = Sofar2OK x | otherwise = Already2Failed chn==?y | (Sofar1OK x)<-chn, x==y = True | otherwise = False instance (Eq a) => ChainableComp (Comp2Chain a) where type AppendElem (Comp2Chain a) = a type ChainAfterAppend (Comp2Chain a) = Comp3Chain a chn.==.y | (Sofar2OK x)<-chn, x==y = Sofar3OK x | otherwise = Already3Failed chn==?y | (Sofar2OK x)<-chn, x==y = True | otherwise = False -- ... 

And with that you can write

 *ChainedComp> 7 ==..7.==.7==? 7 True *ChainedComp> 7 ==..7.==.6==? 7 False *ChainedComp> 5 ==..5.==.5.==.4.==.5.==.5==? 5 False 

Not quite pretty, but IMO is better read than other solutions. The number of required instance descriptions, of course, is not so good, but once for all, so I believe that this is not so bad.