Example to accompany my types in haskell article

group_on-full-example.hs

-- compiles with ghc(i) 7.4.1
import Data.Map (Map, empty, insertWith, toList)
import Data.List(groupBy, group, sortBy, sort)

{- To recap from the main article, we want to define "group_on" via "groupBy", so that its 
   type is something like (b -> b -> Bool) -> (a -> b) -> [a] -> [(b, [a])]

   The method here is to work with a concrete example and gradually massage it 
   into the form we want - using the REPL 

   After a few steps of replacing () by something which matches the expected type, 
   we arrive at "groupBy (\a b -> even a == even b) [1..10]", to give 
   "[[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]]"

   Thinking again about "groupBy", we realise we need to have the 'same' elements 
   adjacent in the list, which we can do by sorting. We'll use the standard 
   "sortBy :: (a -> a -> Ordering) -> [a] -> [a]", whose first argument indicates 
   whether a pair of elements a,b are in order, equal, or out of order. The
   Ordering type is defined in the Prelude like this: 

   data Ordering = LT | EQ | GT deriving (Show, Eq, ...) 
 
   Haskell's Ord type class provides a member function "compare :: a -> a -> Ordering"
   for several types, which returns such a result. For example, "compare 1 2" gives
   LT, "compare 2 2" gives EQ and "compare 2 3" gives GT. 

   So we need a function which compares the result of testing for even. Taking several steps,
   we could go through 

   -- groupBy (\a b -> even a == even b) $ sortBy (\a b -> ()) [1..10]
   -- groupBy (\a b -> even a == even b) $ sortBy (\a b -> compare () ()) [1..10]
   -- groupBy (\a b -> even a == even b) $ sortBy (\a b -> compare (even a) (even b)) [1..10]

   This gets us to [[1,3,5,7,9],[2,4,6,8,10]]

   Finally, we need a bit of tweaking to get the result to the form required. Each list of 
   numbers needs to be tagged with the result of the even test, and it's enough to pick 
   one and test that, since we've already grouped by identicality of result

   -- map (\es -> ()) [[1,3,5,7,9],[2,4,6,8,10]]
   -- map (\es -> ( (), es)) [[1,3,5,7,9],[2,4,6,8,10]]
   -- map (\es -> ( (even (head es)), es)) [[1,3,5,7,9],[2,4,6,8,10]]

   And this produces the required "[(False,[1,3,5,7,9]),(True,[2,4,6,8,10])]"

   The Prelude function "head" does what you expect. Note that we don't have to worry about 
   it being used here with an empty list because of the way grouping works. (If the input
   list is empty then the output is empty. Otherwise, the output will be a non-empty list 
   of one or more non-empty lists.) But wouldn't it be simpler if the compiler could 
   check this for us? 

   Next, we pull out the concrete details by making the list of numbers into a parameter,
   then pulling the various tests out as parameters too.
-}

group_on same eval inp 
  = map (\es -> (eval $ head es, es)) 
  $ groupBy (\x y -> eval x `same` eval y) 
  $ sortBy (\x y -> eval x `compare` eval y) inp

-- Note: I'm using "same" and "compare" as infix operators (like +) by adding 
-- back-ticks. This is a feature of Haskell syntax which sometimes helps readability


-- we can test that we abstracted it correctly by checking what 
-- the group_on function does with our concrete example 
example = group_on (==) even [1..10]
test_example = example == [(False,[1,3,5,7,9]),(True,[2,4,6,8,10])]

{- Now, what about the type of group_on? 

   We're expecting :: (b -> b -> Bool) -> (a -> b) -> [a] -> [(b,[a])] 
   But type inference gives us :: Ord b => (b -> b -> Bool) -> (a -> b) -> [a] -> [(b,[a])] 

   So, an extra requirement or constraint for the 'b' type to be orderable; this comes
   from the use of the overloaded 'compare' function when we are sorting. 

   It's a bit anomalous, so let's think about options. 

   One is to presume that the 'same' test is usually going to be equality, so we can rely 
   on the overloading of "==". In fact, if we know "Ord b" then we get "Eq b" for free
   because of the sub-class relationship. Hence we can simplify a bit:
-}

group_on_v2 eval inp 
  = map (\es -> (eval $ head es, es)) 
  $ groupBy (\x y -> eval x == eval y) 
  $ sortBy (\x y -> eval x `compare` eval y) inp



{- Another annoyance is the repeated calls to 'eval' - can't we try to do something about 
   these? Course we can.

   One way is something like this, tagging the input list with the eval result to give 
   a list of pairs, then sorting and grouping the pairs before removing the tag value. 
-}

group_on_v3 eval inp 
  = map (\es -> (fst $ head es, map snd es)) 
  $ groupBy (\x y -> fst x == fst y) 
  $ sortBy (\x y -> fst x `compare` fst y) 
  $ map (\x -> (eval x, x)) inp 

{- We can tidy this up a bit more, eg. with a new type which represents tagging, say something 
   like the following. The type class stuff says a polymorphic Tag value is Eq-able and Ord-able 
   when the first component is (respectively).

-}

data Tag a b = Tag {tag :: a, value :: b}
instance Eq a  => Eq (Tag a b) where 
  x == y = tag x == tag y 
instance Ord a => Ord (Tag a b) where 
  x `compare` y = tag x `compare` tag y 

group_on_v4 eval inp 
  = map (\es -> (tag $ head es, map value es)) 
  $ group
  $ sort 
  $ map (\x -> Tag (eval x) x) inp 

{- Notice one interesting feature of the various group_on versions - because of sorting the
   groups are in ascending tag order. It might be useful to know this on occasion, although 
   there's no easy way to encode this in Haskell's type system. -}



{- Finally, what does a more direct version look like? We can use Haskell's fairly standard
   "Map" library for hash-like functionality, and define: 

   Basically, it loops over the input list, building up a hash from empty, using the tag
   values as keys and the elements as values - appending lists of values for the same key. 

-}

group_on_v5 eval = toList . foldr (\x -> insertWith (++) (eval x) [x]) empty 



{- This version also requires ordering on the tag values for the hash table implementation,
   but we can do another version with just equality tests too. Exercise for the reader... -}