On Tue, 16 Sep 2008, Levi Stephen wrote:

Hi, I'm looking for how best to represent selections from a set of items.

For example, consider a soccer/football type game.

You would have a Player data type. The game would store a player pool of all players in that game. Each club will have a number of players from that player pool, each match will involve that club selecting a number of players from its list of players.

What is the best way to structure this data and hopefully at the type level enforce this subset type relationship?

Thanks, Levi

Hi Levi et al., One way would be to use Data.Map or Data.IntMap to store a list of IDs and then have each club store a list of IDs. For example,

data Player = ... type Id = ... -- probably Int or String newtype Pool = Pool (Data.Map.Map Id Player) data Club = Club { ..., players :: [Id] }

Then, you can Data.Map.lookup a particular player from an the IDs in order to figure out what players a club owns. Depending on how you're using it, you could also store the list of clubs using a particular player along with the player:

data Club = ... data Player = Player { ..., clubs :: [Club] } newtype Pool = Pool (Data.Set.Set Player)

but I think the former is probably closer to what you're looking for. Also, there might be more tricky ways of doing this, but this is simple and probably the way I'd do it: you don't have any problems enforcing the subset type relationship as long as you insert sane IDs. Alex

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_.28Recor...