I have recently come up with a new way of representing functional references.

As you might recall, functional references (also called lenses) are like a pointer into a field of some data structure. The value of this field can be extracted and modified. For example:

GHCi> get fstF (123,"hey") 123 GHCi> set fstF 456 (123,"hey") (456,"hey") GHCi> modify fstF (*2) (123,"hey") (246,"hey")

where `fstF` is a functional reference to the first element of a pair.
It has the type `RefF (a,b) a`, i.e. in a 'record' of type `(a,b)` it points to an `a`.

Previous representations relied on a record that contained the `get` and `set` or the `get` an `modify` functions.
But there is a much nicer looking representation possible using Functors.

First of all we will need a language extension and some modules:

{-# LANGUAGE Rank2Types #-} import Control.Applicative import Control.Monad.Identity

Now the representation for functional references I came up with is:

type RefF a b = forall f. Functor f => (b -> f b) -> (a -> f a)

This type looks a lot like a continuation passing style function, which would be simply `(b -> r) -> (a -> r)`, but where the result is `f a` instead of any `r`.
With different functors you get different behaviors. With the constant functor we can `get` the field pointed to:

get :: RefF a b -> a -> b get r = getConst . r Const

While the identity functor allows a function us to `modify` the field:

modify :: RefF a b -> (b -> b) -> a -> a modify r m = runIdentity . r (Identity . m) set :: RefF a b -> b -> a -> a set r b = modify r (const b)

As an example of an 'instance', here is the `fstF` function I used in the introduction:

fstF :: RefF (a,b) a fstF a_to_fa (a,b) = (\a' -> (a',b)) <$> a_to_fa a

If we had tuple sections it could be written as simply

fstF x (a,b) = (,b) <$> x a

To get access to inner fields, functional references can be composed. So `compose fstF fstF` points to the first element inner inside the first outer element of a nested pair.
One of the things that I like about the cps/functor based representation is that composition is quite beautiful and symmetric:

compose :: RefF b c -> RefF a b -> RefF a c compose r s = s . r idF :: RefF a a idF = id

Let me conclude with the pair operator, called `(***)` in Control.Arrow.
Unfortunately this operator is not as easy to define.

pair :: RefF a c -> RefF b d -> RefF (a,b) (c,d) pair r s cd_to_fcd (a,b) = some_ugly_code

In fact, the only way I know of implementing pair is by moving back and forth to a get/set representation

where some_ugly_code = let fcd = cd_to_fcd (get r a, get s b) -- :: f (c,d) cd_to_ab (c,d) = (set r c a, set s d b) -- :: (c,d) -> (a,b) in fmap cd_to_ab fcd -- :: f (a,b)

The problem is that we need to split one function of type `(c,d) -> f (c,d)` into two, `c -> f c` and `d -> f d`, because that is what the left and right arguments expect.
Then later, we would need to do the reverse and combine two of these functions again.

Does anyone have a better suggestion for implementing `pair`?

## Comments

Just take a hint from Control.Arrow: implement in terms of first, second, and compose. There's a little magic in figuring out how to implement "first", but from there, it's easy.

Oops, forgot the instances:

That looks good.

I had tried a similar approach myself, but I made a mess of it. You make it look much simpler :)

One disadvantage is that

pairis still done in two steps, first the first element is transformed and than the second (or the other way around). I.e. you go fromf (a,b)tof (c,b)tof (c,d). You construct a pair, only to destroy it again layer.I think this is even nicer if we give

RefFa different name (withTypeOperators):In this, we have a category formed with

compose/idF, andgetis something I've been using like this:That is,

$'realizes' an arrow in the category as a true Haskell function that can be applied to something.It appears your formatting is a bit borked...

Your RealCategory is a nice idea.

I didn't use type operators, the Category class or other classes to keep the presentation simple. For a real system we should eventually use something like a

RefCategoryclass, see overloading functional references.I also don't think these Functor based references are the best choice in practice. Something like

would have less overhead.

Interesting, I must admit to not having really read your blog before so it seems I'm covering some stuff you've already done :)

I would love to see what a re-implementation of the Haskell Prelude along these and other more recent lines of development (such as Edward Kmett's category work) would look like.

To be fair, it took me the better part of an hour to come up with that answer. :)

So, I think you are right that the functor version is overkill, and here's why:

The insight here is that by parametricity, the only operations that

ref mk acan do to create thef ait has to return is to call themkfunction with some argument, and thenfmapon the result with someb -> afunction to convert fromf btof a.So, we can just store those two values: the argument to

mk, and the functions passed tofmap, and we've encompassed everything that a reference can possibly do. This is exactly whatAnyFdoes. Since there is an isomorphism betweenRefF a banda -> AnyF b a, we might as well use the version without the overloading overhead.Also, your regexp for matching

codeblocks is broken. It seems to skip intervening at-signs. :)Just came back to this after a while and was thinking about it again.

Actually, if you inline it and see what happens, the compiler probably optimizes out the intermediate pair. Here's one of the intermediate steps:

Notice the

case (c,b) of (c,b) ->; the compiler (or us) can easily remove that and be left with (after some further simplification:Although I guess the fmap passed to rac/rbd includes some information about pair manipulation. I guess I need to think about this some more.

"This type looks a lot like a continuation passing style function, which would be simply (b -> r) -> (a -> r), but where the result is f a instead of any r." Then it would be (b ->

f a) -> (a -> f a). :) It reminds me a f-coalgebra, so it maps coalgebras.## Reply