I have a data structure like this:
data DBM = DBM {
evaluated :: Bool,
arr :: Array (Int, Int) Constraint
}
evaluate :: DBM -> DBM
evaluate (DBM n _ mat) = DBM n True (... mat)
And, there are a bunch of functions like this (which require the evaluated form):
subsetDBM :: DBM -> DBM -> Bool
subsetDBM dbm1 dbm2
| evaluated dbm1 && evaluated dbm2 = ...
| otherwise = subsetDBM (evaluate dbm1) (evaluate dbm2)
And a bunch of functions like this (which modify the data structure, leaving it unevaluated):
constrain :: Int -> Int -> Constraint -> DBM -> DBM
constrain i j constr dbm = dbm { arr = ..., evaluated = False }
Some notes about the evaluation
function:
- Given some
x
,x
andevaluate x
contain the same information. So, there is no reason to keepx
around ifevaluate x
is already computed. - Evaluation is idempotent.
evaluate x = evaluate (evaluate x)
- Running
evaluate
is expensive. Thus, it is better to callevaluate
lazily (e.g, not call evaluate everytimeconstrain
is called.
The above features can be taken advantage of in a very clean way in a stateful environment, for example, by maintaining some state which replaces the original value of x
in place evaluate x
is computed. See this Rust Implementation, for example
What are some good ways to model this in Haskell?
- Option A: Use a flag, like above:
data DBM = DBM {evaluated :: Bool, ...}
- Option B: Use different types:
EvaluatedDBM
,UnEvaluatedDBM
- Option C: ???