[Haskell-beginners] Looking for a data structure
cs-haskell at protempore.net
Tue Sep 16 15:21:15 EDT 2008
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 . 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
That function (in a module with the appropriate export list) might look
something like the following:
-- BEGIN EXAMPLE --
-- 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.
-- 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."
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 ,
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.
More information about the Beginners