<div class="gmail_quote">On Fri, Apr 24, 2009 at 5:11 PM, Denis Bueno <span dir="ltr"><<a href="mailto:dbueno@gmail.com">dbueno@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi all,<br>
<br>
Suppose I have the following interface to a sorting function:<br>
<br>
sort :: (Ord a) => [a] -> IO [a] -- sort large, on-disk array of records<br>
<br>
but I don't have a sortBy where you can simply pass a compare function.<br>
<br>
Wrapped around this is a command-line program which should allow the<br>
user to specify different orderings on Records. For example, if the<br>
Record has three fields, the user should be able to say "sort only on<br>
the first two".<br>
<br>
Is there an Ord instance that can be dynamically changed in this way?<br>
<br>
My first idea is something like this:<br>
<br>
data CompareRecord = CR{ rCompare :: Record -> Record -> Ordering,<br>
unCR :: Record }<br>
instance Ord CompareRecord where<br>
compare (CR cmp x) (CR _ y) = cmp x y<br>
<br>
where the rCompare field would be a function that is based on the<br>
flags passed to the command-line problem. But this has an ugly<br>
asymmetry. Does anyone have any other ideas?<br></blockquote><div><br></div><div>You can make a safer 'CompareRecord' using 'reflection' from hackage:</div><div><br></div><div><br></div><div><br></div><div>
<br></div><div><div>> {-# LANGUAGE TypeOperators, FlexibleContexts, UndecidableInstances #-}</div><div><br></div><div>> import Data.Reflection</div><div>> import Data.List (sort)<br></div><div><br></div><div>> myList = [1,2,5,4,2]</div>
<div><br></div><div>> newtype (s `Ordered` a) = Ordered { getOrdered :: a }</div><div><br></div><div>> instance (s `Reflects` (a -> a -> Ordering)) => Eq (s `Ordered` a) where</div><div>> a == b = (a `compare` b) == EQ</div>
<div><br></div><div>> instance (s `Reflects` (a -> a -> Ordering)) => Ord (s `Ordered` a) where</div><div>> a `compare` b = reflect (undefined `asReifiedComparison` a) </div><div>> (getOrdered a) (getOrdered b) </div>
<div>> where</div><div>> asReifiedComparison :: s -> (s `Ordered` a) -> s</div><div>> asReifiedComparison = const</div><div><br></div><div>-- for expository purposes, I renamed your sort, 'mySort' and aped it with the Data.List sort</div>
<div><br></div><div>> mySort :: Ord a => [a] -> IO [a]</div><div>> mySort = return . sort</div><div><br></div><div>> withOrder :: s -> a -> s `Ordered` a </div><div>> withOrder = const Ordered</div>
<div><br></div><div>> mySortBy :: (a -> a -> Ordering) -> [a] -> IO [a]</div><div>> mySortBy f as = reify f (\s -> map getOrdered `fmap` mySort (map (withOrder s) as))</div><div><br></div><div>> test1 = mySortBy compare myList</div>
<div>> test2 = mySortBy (flip compare) myList</div><div><br></div><div><div>*Main> test1</div><div>Loading package reflection-0.1.1 ... linking ... done.</div><div>[1,2,2,4,5]</div><div><br></div><div>*Main> test2</div>
<div>[5,4,2,2,1]</div><div><br></div></div><div>The sort function is lifted up to the type level by 'reify' and is extracted uniformly by 'reflect' eliminating the bias or your first proposed implementation. Note that the mapping of withOrder is just to force them all to agree on the type parameter s.<br>
<br></div><div>-Edward Kmett</div></div></div>