[Haskell-beginners] Looking for a data structure

[Calvin Smith]

Hi Levi,

On 09/15/2008 04:11 PM,, Levi Stephen wrote:
 > ...
 >
 > What is the best way to structure this data and hopefully at the type 
level enforce this subset type relationship?
 >

It's not enforced at the type level as you desired, but in terms of 
enforcing the subset relationships, one approach is to use smart 
constructors [1]. This involves not exporting the constructor for the 
ADT, so that clients are not able to create possibly incorrect values, 
and instead providing functions for creating new values that ensure your 
constraints are satisfied.

In your case, if you wanted to ensure that a `Club` contains `Player`s 
that all belong to the same `League`, you would not export the `Club` 
constructor and would instead provide a function for creating new clubs. 
That function might accept a `League`, a name for the club, and some 
players, and the function might return something like `Either String 
Club`, where the string value would be an error message or the Club 
value would be the new club. In the `club` function that creates a new 
`Club`, you would verify that all the `Player`s belong to the given 
`League`.

That function (in a module with the appropriate export list) might look 
something like the following:

-- BEGIN EXAMPLE --

module Football(
   -- We export each data type but not its constructor, and provide a "smart
   -- constructor" function for each type. The client can only create values
   -- of a given type using the smart constructor, which ensures that all
   -- constraints such as subset relationships are satisfied.
   League(), league,
   Club(), club,
   Player(), player
) where

-- Define the types...

data League = League [Club] [Player]
data Club   = Club   String [Player]
data Player = Player String

-- Provide smart constructors that check whatever needs to be
-- checked and fail with an error message if necessary...

club :: League -> String -> [Player] -> Either String Club
club league name players =
   if all_players_in_league league players
      then Right (Club name players)
      else  Left "All players must be in the given league."
   where
      all_players_in_league :: League -> [Player] -> Bool
      all_players_in_league = undefined -- TODO

-- Do likewise for league and player...

league = undefined -- TODO
player = undefined -- TODO

-- END EXAMPLE --

Of course, you might want to verify more than shown. And since the 
`club` function creates a new `Club` in a given `League`, we would need 
to reflect that in the return type of `club` (e.g., `Either String 
(League, Club)` where the league value returned would have the new club 
added to it), but you get the idea.

One downside to this approach is that since we don't export the 
constructors, users of the module can't pattern match on the various 
types, so you also have to provide accessor functions for the various 
types. You can use the Haskell record syntax for defining the types [2], 
but even with the accessors automatically provided, not being able to 
pattern match can lead to more and uglier code, since we can no longer 
have functions like `f (Club league name players) = ...` and are forced 
to accept just a club value and manually extract what we need.

I hope that helps.

calvin

[1] http://www.haskell.org/haskellwiki/Smart_constructors
[2] 
http://en.wikibooks.org/wiki/Haskell/More_on_datatypes#Named_Fields_.28Record_Syntax.29