December 21, 2019

A first step into optics

Dipping my toes into a new technique.

A first step into optics

I've recently picked up Chris Penner's book Optics by Example to understand how lenses (and similar) work. I thought I'd put the ideas into practice on an Advent of Code challenge, and day 15's challenge seemed like a good one to start with.

However, the combination of lenses and prisims caused a couple of headaches!

I'm working with these types:

type Position = (Integer, Integer) -- x, y

data Cell = Vacant { _droid :: Droid 
                   , _fromStart :: Integer
                   , _isGoal :: Bool
                   | Wall 
                   | Unknown
                   deriving (Show, Eq)
makeLenses ''Cell
makePrisms ''Cell

type Hull = M.Map Position Cell

The usual way I extract a value from a record in the Map, given its Position, is like this:

robot = _droid $ hull!here
distance = _fromStart $ hull!here

(The algorithm I'm implementing guarantees that hull!here is a Vacant cell.)

What stumped me for a bit is the combination of traversal to work with an indexed container, a prism to work with pattern matching, and a lens to extract the value stumped me at first. However, the nice people at Reddit helped me out.

The data accessors above can be written in a few ways, depending on whether you're using the English names or the operators for the actions, and whether you're using at or ix to locate the items in the Map. This means that the accessors can be written in any of these four ways:

robot = fromJust $ preview (at here . _Just . isGoal) hull
robot = fromJust $ preview (ix here . isGoal) hull
robot = fromJust $ hull ^? at here . _Just . droid
robot = fromJust $ hull ^? ix here . droid

I'm not sure that any of these is an improvement over the "vanilla" way, but they're probably more general.

Setting values in a record is similar in both approaches. The normal way is

newCell = Vacant { _droid = robot'
                 , _fromStart = distance + 1
                 , _isGoal = (found == Goal)

and using lenses its

newCell = _Vacant # (robot', distance + 1, found == Goal)

which is terser, but relies on the ordering of parameters in that tuple.

The containsGoal function does seem to be easier, going from

containsGoal :: Cell -> Bool
containsGoal Wall = False
containsGoal c = _isGoal c


containsGoal :: Cell -> Bool
containsGoal c = fromMaybe False $ c ^? isGoal

which certainly seems much more compact.

And the final example, runDroidMachine goes from this:

runDroidMachine :: Droid -> Droid
runDroidMachine d = d { _machine = machine'
                      , _executionState = halted
                      , _machineOutput = output
    where   machine = _machine d
            input = _currentInput d
            (halted, machine', output) = runMachine input machine

into this:

runDroidMachine :: Droid -> Droid
runDroidMachine d = d & machine .~ machine' 
                      & executionState .~ halted 
                      & machineOutput .~ output
    where (halted, machine', output) = runMachine (d ^. currentInput) (d ^. machine)

Again, neater, but not massively so.

To conclude, the optics seem to have some benefit, but I'm perhaps not using sufficiently complex data structures to see their full advantages yet.


The code is available.


Cover photo by unsplash-logoMalcolm Lightbody