On Fri, 23 Oct 1998, Ralf Hinze wrote:
| If local instance declarations were admissable I could possibly write
| ... lots of hand-waving ...
|
| > sortBy (rel :: Rel a) = sort where instance Ord a where (<=) = rel
Look at Mondrian:
http://www.cs.chalmers.se/~koen/Papers/mondrian.ps
The intention there was that this would be easy to do. Dictonaries are
implemented by records (possibly containing polymorphic functions):
class Ord a where
{ (<=) :: a -> a -> Bool
}
defines a record type containing one field: <=.
If we want to compare two elements, we can explicitly choose a Ord-record:
intOrd :: Ord Int
intOrd = Ord{ (<=) = primIntCompare }
1 intOrd.<= 2 :: Bool
Or we can leave it implicit:
1 <= 2 :: Ord Int => Bool
Note that the type expresses that we haven't specified an ordering yet.
Implementing a sorting function, is like adding an extra selector function
to the Ord record. It goes like this:
sort :: Ord a => [a] -> [a]
sort xs = ... <= ... xs ...
Now, if we want to use sort on different orderings:
sort [1,2,3,4] :: Ord Int => [Int]
intOrd.sort [1,2,3,4] :: [Int]
crazyOrd.sort [1,2,3,4] :: [Int]
...
We can also implement a function that flips a sorting:
rev :: Ord a -> Ord a
rev ord = Ord{ (<=) = flip (ord.<=) }
Note that this is defined as a record transformer, rather than as a new
selector function for Ord. And now we can define "revsort", using the
flipped ordering:
revsort :: Ord a => [a] -> [a]
ord.revsort = (rev ord).sort
I really like these ideas, and the paper has a few more examples.
Unfortunately there seem to be some semantic issues wrong with it (what to
do if you have multiple record in your contexts).
Regards,
Koen.
--
Koen Claessen,
[EMAIL PROTECTED],
http://www.cs.chalmers.se/~koen,
Chalmers University of Technology.
