Haskell evaluating properties of a data type only once when first accessed?

user_6030440 0
Viewed 203

In imperative/object oriented programming with mutable state, it would be very common and useful to declare a structure such as the following:

struct RigidBody {
  float m_mass;
  float m_inverseMass;
  Mat3 m_localInverseInertiaTensor;
  Mat3 m_globalInverseInertiaTensor;

  Vec3 m_globalCentroid;
  Vec3 m_localCentroid;

  Vec3 m_position;
  Mat3 m_orientation;
  Vec3 m_linearVelocity;
  Vec3 m_angularVelocity;
};

Source: http://allenchou.net/2013/12/game-physics-motion-dynamics-implementations/

There are many properties here that are able to be computed directly from others, such as m_inverseMass from m_mass. In a stateless programming language like Haskell, getting derived values is easy enough:

data RigidBody = RigidBody {mass :: Float}

inverseMass :: RigidBody -> Float
inverseMass body = 1 / mass body

But this computes the inverseMass every time we need it, which can get expensive especially in domains where performance is critical, like physics simulation. I've considered memoization, but I wasn't sure if this is a good way of expressing this lazy evaluation of dependent properties, as it seemed to be a complicated solution. How would I store derivative values without having to recompute them?

lazy-evaluation functional-programming haskell
2 Answers

As @4castle and @Shersh note, a simple approach would be to include the derived value in the data type:

data RigidBody = RigidBody
  { m_mass :: Float
  , m_inverseMass :: Float }

and then use a smart constructor to make new RigidBodys:

rigidBody mass = RigidBody mass (1/mass)

The expression 1/mass will create a thunk for m_inverseMass which, after it is first evaluated, will be available without recalculation, so it provides a sort of auto memoization.

More general transformations, like changing the position and properly updating all the global* fields based on the local* values would be handled in a similar manner. As a simplified example:

module Rigid where

type Vec3 = Double  -- just to type check

data RigidBody = RigidBody
  { m_mass :: Float
  , m_inverseMass :: Float
  , m_pos :: Vec3
  , m_localCentroid :: Vec3
  , m_globalCentroid :: Vec3
  }

rigidBody mass pos centroid =
  RigidBody mass (1/mass) pos centroid (centroid + pos)

move body delta =
  rigidBody (m_mass body)
            (m_pos body + delta)
            (m_localCentroid body)

In an application that's performance critical, you would want to take steps to introduce strictness in appropriate places so you don't build up huge piles of unevaluated thunks.

user_72030160

You can store inverseMass as Maybe Float inside RigidBody. When inverseMass is Just someMass you just extract this value. If it's Nothing you compute it and store inside RigidBody. The problem is with this store part. Because as you may know objects are immutable in Haskell.

Naive but simple solution would be to return RigidBody after every computation like this:

data RigidBody = RigidBody 
    { rigidBodyMass        :: Float
    , rigidBodyInverseMass :: Maybe Float }

inverseMass :: RigidBody -> (Float, RigidBody)
inverseMass b@(RigidBody _ (Just inv)) = (inv, b)
inverseMass   (RigidBody mass Nothing) = let inv = 1 / mass 
                                         in (inv, RigidBody mass (Just inv))

If you have a lot of such fields you may find such approach extremely tedious. And it's not very convenient to write code using such functions. So here is the place where State monad becomes handy. State monad can just keep current RigidBody inside explicit state and update it accordingly through all you stateful computation. Like this:

inverseMass :: State RigidBody Float
inverseMass = do
    RigitBody inv maybeInverse <- get
    case maybeInverse of
        Just inv -> pure inv
        Nothing  -> do
            let inv = 1 / mass
            put $ RigidBody mass (Just inv)
            pure inv

Later you can just use inverseMass multiple times and only during your first call inverse of mass will be calculated.

You see, in imperative programming languages like C++ state is explicit. You want to update fields of RigidBody. So basically you have some object of type RigidBody which stores some states. Because state is implicit you don't need to specify in your functions that they change fields of RigidBody. In Haskell (and every good programming language) you specify explicitly what is your state and how you will change it. You specify explicitly what objects you want to work with. inverseMass monadic action (or just function if you want) will update your explicit state depending on the current state at the moment of calling this function. This is more or less idiomatic approach in Haskell for such sort of tasks.

Well, another idiomatic solution: just create values of your data type with all fields set to some function calls. Because Haskell is lazy such fields are calculated first time only when they are needed.

user_29005020
Related