Skip to content

References Tutorial

Boldizsár Németh edited this page Sep 30, 2016 · 4 revisions

What is a reference?

A reference is a property accessor. You can think of it as a setter and getter method. For example if you have a point datatype: data Point = Point Double Double then, you may define references x and y to access the two Double values inside the point. You can use the reference to get their values and also to modify them.

Why do we need references?

The simplest problem references solve is the problem of handling a large nested data structure. For example, take the following datatypes:

data Arrow = Arrow { from :: Point, to :: Point }
data Point = Point { x :: Double, y :: Double }

If you want to shift the arrow, you have to define a function that takes it to parts and repacks it:

shiftArrowX :: Double -> Arrow -> Arrow
shiftArrowX d (Arrow (Point fromX fromY) (Point toX toY)) 
  = Arrow (Point (fromX + d) fromY) (Point (toX + d) toY)

This packing and repacking gets more complicated each time the representation grows. The references library solves this problem by letting you define references:

data Arrow = Arrow { _from :: Point, _to :: Point }
data Point = Point { _x :: Double, _y :: Double }
makeReferences ''Arrow
makeReferences ''Point

Then shiftArrowX can be defined using references:

shiftArrowX :: Double -> Arrow -> Arrow
shiftArrowX d = (from &+& to) & x .- (+d)

What is the type of a reference?

The type of :t from is (Monad w, Monad r) => Reference w r MU MU Arrow Arrow Point Point

The first 4 type variables are the write-read semantic monads of the reference. The last 4 are the type of the context type, and the accessed element.

We don't have any constraints (aside from Monad) for w and r, and that shows that the from element is always present in an arrow. The two occurrence of MU shows that this reference cannot be inverted.

Semantic monads can express the multiplicity of the accessed element in the context.

data Polygon = Polygon { _points :: [Point] }
data Shape = ArrowShape { _arrow :: Arrow }
           | PolygonShape { _polygon :: Polygon }

The semantic monads of the reference arrow (that accesses the arrow in a shape if it is an arrow) will be w and r where w must be a monad and r must also be able to represent a Maybe. That guarantees that we can represent the missing element with Nothing. The semantic monads of points&traversal (it accesses each point of a polygon) will be similar, but here r must be able to represent [], so multiple elements can be represented in the return of a get. This representation of types is defined in the instance-control package.

Here the context type and the accessed element is present twice in the type. This shows that it is a simple reference that won't change the type of the context. In other cases when the data type is polymorphic, using a reference may actually change the type of the context. For example, the type of the context and elements types for the reference just (that accesses the possible existing element inside a Maybe value) will be: (Maybe a) (Maybe b) a b. That shows that by replacing the element inside a just with something of type b, you will get a (Maybe b) as a result

How to combine references?

In the motivation example we have already shown how references can be combined. There is two combinator, the & and &+& operators.

& composes references. This resembles composition of functions. If I have a reference ab that accesses a b inside an a and a bc reference that accesses a c inside a b then I can create a ab&bc reference that accesses the c inside the a.

This is most useful when building up deep nested data structures and have to manipulate the basic building blocks of it.

&+& adds references. To add references their context and element type must be the same. The resulting reference will access both values. For example, combining _1 and _2 references into _1 &+& _2 will result in a reference that accesses both elements of a pair.

Warning: The references combined by &+& should access disjunct values. Otherwise it will result in references that access the same value multiple times.

How can I use references?

We have a set of pure operators and a set of monadic operators for working with references. The pure ones are:

(^.) :: s -> Getter Identity s t a b -> a
(.=) :: Setter Identity s t a b -> b -> s -> t
(.-) :: Setter Identity s t a b -> (a -> b) -> s -> t

The first gets the value of the accessed element, the second modifies it, the third applies a given pure function to it. Getter and Setter are just type synonyms for references with unnecessary type arguments fixed.

getX :: Point -> Double
getX p = p ^. x

projectToX :: Point -> Point
projectToX = y .= 0

Monadic operations on references are flexible, they can work in any suitable monadic context:

(^?) :: Monad m => s -> Getter m s t a b -> m a 
(!=) :: Setter m s t a b -> b -> s -> m t
(!~) :: Setter m s t a b -> (a -> m b) -> s -> m t

Using monadic operators enables us to use references thats value may not be present (like just), or that may have multiple values.

getAllPoints :: Shape -> [Point]
getAllPoints sh = sh ^? arrow&(from&+&to) &+& polygon&points&traversal

How to define references?

References can be defined using different methods:

  • Create them for your own datatypes with makeReferences.
  • Make them from getter, setter functions with our generators.
  • Using lenses from the lens package, an alternative library to references.

What to do next?

  • cabal install references
  • Use import Control.Reference
  • ??
  • Profit 😄