Turn endomorphisms into Applicative

Question

Say we have a data Vector with an obvious operation (so Vector is instance of Monoid)

(+):: Vector -> Vector -> Vector

Now, say we want some object to be movable by vector. Say I know exactly the types which are considered movable, so there is some move function

move :: Vector -> Movable -> Movable

where data Movable = Movable t1 | t2 | t3

Or the class version

class Movable a where
  move :: Vector -> a -> a

with some instances of the form

instance Movable ti where
  move :: Vector -> ti -> ti

Personally, I prefer the class version.

Now, say we have a series of computations roughly equivalent to

move v1 . move v2 . move v3

Which in the end is equivalent to move (v1 + v2 + v3)

We want an optimization: move (v1 + v2) is way cheaper then move v1 . move v2.

The question: as far I know, that is where Applicative comes handy? How to implement it in proper Haskell?

I came up with the following: store the info in some container of the form

data Move a = Move {data :: a, offset :: Vector}

and have a separate function

transform :: Movable a => Move a -> a

This way we can implement

instance Applicative (Move a)

But it seems ugly to me. Is there a better way? Can it be turned into Monad (just to use flexible standard library)

UPD: What I need is: If I have a Movable object x, and I transform it

y = move v1 $ move v2 $ move v3 $ x

than Haskell must internally make it into

y = move (v1 + v2 + v3) x

only when I evaluate y.

Answer 1

I guess laziness can help.

-- You may want offset :: !Vector, base :: !a.
-- But you definitely don't want result :: !a.
data Moved a = Moved { offset :: Vector, base :: a, result :: a }

-- smart constructor; not really needed, strictly speaking
moved :: Movable a => Vector -> a -> Moved a
moved o b = Moved o b (move o b)

instance Movable a => Movable (Moved a) where
    move v m = moved (v + offset m) (base m)

The first time you access the result of a Moved object, it will be computed, but further accesses will use the previously computed result. Intermediate results will be thrown away without incurring the cost of their moves.

This is very similar to your Move type, except that your transform would recompute its result each time it was called. That may not be desirable, especially if there is the opportunity for shared computation; e.g. one could write

unmoved :: a -> Moved a
unmoved a = Moved zero a a

rebase :: Movable a => Moved a -> Moved a
rebase = unmoved . result

to make a new base object that has accumulated the motions so far; branching off from this object then accumulates a smaller sum in each branch.