Good ways to model things that use 'on-demand' evaluation?

Learn
1

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 and evaluate x contain the same information. So, there is no reason to keep x around if evaluate x is already computed.
  • Evaluation is idempotent. evaluate x = evaluate (evaluate x)
  • Running evaluate is expensive. Thus, it is better to call evaluate lazily (e.g, not call evaluate everytime constrain 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: ???
2

Do you ever call the constrain-like functions on the evaluated form? If not, you can probably go with something like

data DBM = DBM
  { evaluated :: Array (Int, Int) Constraint
  , unevaluated :: Array (Int, Int) Constraint
  }

evaluate :: Array (Int, Int) Constraint -> Array (Int, Int) Constraint
evaluate = ...

makeDBM :: Array (Int, Int) Constraint -> DBM
makeDBM x = DBM (evaluate x) x

subsetDBM :: DBM -> DBM -> Bool
subsetDBM DBM{evaluated = x} DBM{evaluated = y} = ...

constrain :: Int -> Int -> Constraint -> DBM -> DBM
constrain i j constr DBM{unevaluated = x} = makeDBM constrained
  where
    constrained = ...
3

Yes, I definitely have constrain i j constr dbm where evaluated dbm == True.