Appropriate abstraction in lieu of heterogenous (but shared-class) list?

Question

The Problem

I'm trying to write a game engine in PureScript. I'm new to it, but learning has been smooth since I've previously gone through Real World Haskell (though I haven't much experience using Haskell for "real" things, either). Anything that moves as many as possible of my runtime errors into compiletime errors, is a win in my book - but if the language proves to be overly restrictive of my ability to abstract away the problems, it can remove some of that win.

Okay, so, I'm trying to build a 2d gaming engine in PureScript over the HTML5 Canvas/context2d (Obviously purescript-canvas makes an excellent choice for this - I much prefer it over Elm's Graphics.Canvas module, as it maps so much more closely to the actual underlying JS API, and in particular gives me access to the individual pixels of the Canvas).

In my existing (unfinished, but usable) JS engine, the core functionality was that I would keep a list of "sprites" (heterogeneous, except that they all share a common class), and loop over them all to call .update(timeDelta) and .draw(context2d) methods.

The sprites all share a common interface, but would have to support fundamentally different data under the hood. One might have x/y coordinates; another (representing perhaps an environmental effect) might have a "percent complete" or other animation state.

The thing is, I just can't come up with an equivalent abstraction (to heterogeneous/shared-class lists) that does what I'd need it to do, without abusing the FFI to hack my way into very impure code.

Solutions (and their issues)

Heterogeneous Lists (duh)

Obviously, the best possible abstraction that can do the equivalent of a heterogeneous list, is a heterogeneous list.

Haskell-style

It turns out Haskell (that is, tricked-out GHC, not the official spec/report) offers exactly what I want - you can box up type information while still keeping class constraints, applying a single polymorphic function across all items in the list, without breaking type safety. This would be ideal, but alas PureScript doesn't currently allow me to express a type like:

data ShowBox = forall s. Show s => SB s

PureScript-Style (state of the art)

For PureScript, there's the purescript-exists package, which probably is intended to provide equivalent functionality to the Haskell solution immediatly above, and would let me—not hide, but remove—type information, and put it back in again. This would let me have a heterogeneous list, but at the expense of completely breaking type safety.

More to the point, I don't think i could make it work to my satisfaction, because even if I have a list of [Exists f], I can't just extract/re-add the type as a generic forall a. (Draw a) => a—I have to know the actual type I'm reinstating. I could include a "tag" of some sort that tells me what "real" kind of type I should be extracting, but if I'm pulling those sorts of shenanigans I might as well be coding in plain JS. Which I may have to do (for the list, not necessarily the sprites contained).

All state in one massive data value

I could unify all the sprites as having the same type, by representing all the states of the individual sprites in one massive structure, passing it to each sprite's "update" implementation (still can't use class polymorphism, but I could include a mutation function for each individual sprite value as part of the type, and use that). This sucks for obvious reasons: each sprite has the freedom to mutate/update the data of other sprites. The massive data structure has to be updated globally for each new kind of sprite state I have to represent. Can't make a library of it, because everyone who uses the engine has to modify it. Might as well be JS.

Separate, homogenous state type

Or each sprite could have separate state, and all have the same state representation. This would avoid the "fingers in each others' pies" scenario, but I've still got a uniform structure I have to update with excessive knowledge of every sprite's needs, lots and lots of wasted data for those bits of the type structure not needed by every sprite. Very poor abstraction.

Represent the different data in JSON or what have you

Ew. This way basically is just using JS data and pretending it's PureScript. Have to throw out every advantage of PureScript's typing.

No abstractions

I could just treat them all as entirely unrelated types. This means that if I want to add a new sprite, I have to update the outermost draw function to add a drawThisParticularSprite, ditto for the outermost update function. Probably the worst of all possible solutions.

What I'll probably do

Assuming that I'm correct in my assessment of the abstraction choices available to me, it seems clear that I'll have to abuse the FFI one way or another to do what I need. Perhaps I'll have a unified record type like

type Sprite = { data: Data, draw: Data -> DrawEffect, update: Data -> Data }

where Data is some kludgey type-removed thing like maybe an Exists f of some kind, and

type DrawEffect = forall e. Eff (canvas :: Canvas | e) Context2D

or something. The draw and update methods would both be specific to the individual records, and both "know" the true type to extract from Data.

In the meantime, I'd probably pursue asking the PureScript dev folks about the possibility of supporting the Haskell-style existential stuff so I could get a proper, true heterogeneous list without breaking type safety. I think the main bit would be that (for the Haskell example previously linked), the ShowBox would have to store instance information of its (hidden) member, so it'd know the correct instance of Show to use, from its own override of the show function.

Plea

Can someone please confirm whether the above is accurate in terms of what my available options are currently in PureScript? I'd appreciate any corrections, and in particular if you see a better way of dealing with the issue—especially if there's one that allows me to use only "pure" code without sacrificing abstraction—please let me know!

Answer 1

I'm assuming here that your Draw class looks like

class Draw a where
  draw :: a -> DrawEffect
  update :: a -> a

The purescript-exists option can work, and it definitely is type-safe, despite what you claim about removing information rather than hiding it.

You need to move the operations on the class into a type:

data DrawOps a = DrawOps { "data" :: a
                         , draw :: a -> DrawEffect
                         , update :: a -> a 
                         }

Now, the type you want is Exists DrawOps, which can be put into a list, for example:

drawables :: List (Exists DrawOps)
drawables = fromArray [ mkExists (DrawOps { "data": 1
                                          , draw: drawInt
                                          , update: updateInt
                                          }
                      , mkExists (DrawOps { "data": "foo"
                                          , draw: drawString
                                          , update: updateString
                                          }
                      ]

You can (safely) unwrap the types by using runExists, noting that the type of runExists forces you to ignore the type of the wrapped data:

drawAll :: List (Exists DrawOps) -> DrawEffect
drawAll = traverse (runExists drawOne)
  where drawOne (DrawOps ops) = ops.draw ops."data"

However, if these are the only operations in your class, then you can use the isomorphic type

data Drawable = Drawable { drawn :: DrawEffect
                         , updated :: Unit -> Drawable
                         }

The idea is that this type represents an unfolding of the operations in DrawOps:

unfoldDrawable :: forall a. DrawOps a -> Drawable
unfoldDrawable (DrawOps ops) 
  = Drawable { drawn: ops.draw ops."data"
             , updated: \_ -> unfoldDrawable (DrawOps (ops { "data" = ops.update ops."data" })) 
             }

Now you can fill a list with Drawable things which hold different types of data:

drawables :: List Drawable
drawables = fromArray [ unfoldDrawable 1     drawInt    updateInt
                      , unfoldDrawable "foo" drawString updateString
                      ]

Again, you can safely unwrap the types:

drawAll :: List Drawable -> DrawEffect
drawAll = traverse drawOne
  where drawOne (Drawable d) = d.drawn

updateAndDrawAll :: List Drawable -> DrawEffect
updateAndDrawAll = traverse updateAndDrawOne
  where updateAndDrawOne (Drawable d) = (d.updated unit).drawn

Answer 2

@phil-freeman (and any other readers): for reference, here's the complete, working version of the code I adapted from the Exists portion of your answer, to verify it for myself (to be found at the bottom). (This is a self-answer to escape the text-length limitations of comments, and not because it's an actual answer)

So, it seems clear that I was mistaken on some crucial aspects of how Exists works. I had read the source code, but being new to PureScript I think I had trouble properly reading the Rank-2 type of runExists. I'd heard of Rank-N types, and understood that they limited the scope of a forall, but didn't understand why that was useful—now I do. :)

As I understand it, its use for runExists forces its function argument to be applicable to all DrawOps, and not just some—which is why it must rely on the DrawOps (and it alone) to be self-aware and DTRT with its update method.

It also took me a bit to figure out what you were doing with the non-Exists example, but I think I get it now. I was thrown a bit by the \_ -> ... definition for Drawable's updated function, probably because I suspect such a technique isn't necessary in lazy-evaluating Haskell, but in PureScript of course it needs to be a function to prevent it form unfolding everything at once.

I was thinking that perhaps the non-Exists method was inferior because it doesn't allow anyone to operate on the data except itself... but of course on reflection, that's nonsense, because the same is true of the Exists method—it looks like an outsider is able to play with the data (in, say, drawOne)—but I guess the type of runExists guarantees that any such "outsider" must rely wholly on the DrawOps's own means to deal with anything specific about the data, so it amounts to the same thing.

Some of the sprites/Drawables will in fact need to know more about each other/interact with each other - for instance, collision-checking, and target-tracking, so I'll have to expand the available functions appropriately to allow the DrawOps or Drawables to reveal more information, but I think I should be able to manage that now.

Thank you for this extremely educational explanation!

(Working Exists sample code follows, for other curious readers:)

module ExistsExample where

import Data.Exists
import Data.List
import Control.Monad.Eff.Console
import Control.Monad.Eff
import Prelude
import Data.Traversable

main :: forall e. Eff (console :: CONSOLE | e) Unit
main = do
    let all = updateAll $ updateAll drawables
    drawAll all

type DrawEffect = forall e. Eff (console :: CONSOLE | e) Unit

data DrawOps a = DrawOps { "data" :: a
                         , draw :: a -> DrawEffect
                         , update :: a -> a
                         }

updateInt = (+1)
updateString = (++ ".")

drawables :: List (Exists DrawOps)
drawables = fromFoldable $ [ mkExists (DrawOps { "data": 1
                                          , draw: print
                                          , update: updateInt
                                          })
                           , mkExists (DrawOps { "data": "foo"
                                          , draw: print
                                          , update: updateString
                                          })
                           ]

drawAll :: List (Exists DrawOps) -> DrawEffect
drawAll list = do
    traverse (runExists drawOne) list
    return unit
  where
    drawOne :: forall a. (DrawOps a) -> DrawEffect
    drawOne (DrawOps ops) = ops.draw ops."data"


updateAll :: List (Exists DrawOps) -> List (Exists DrawOps)
updateAll =
    map (runExists updateOne)
  where
    updateOne :: forall a. DrawOps a -> Exists DrawOps
    updateOne (DrawOps ops) = mkExists (DrawOps ( { draw: ops.draw
                                        , update: ops.update
                                        , "data": ops.update ops."data" } ))