• Me
• Publications
• Teaching
• Software
• Blog

Overloading functional references

Recently there have been some blog post and mailing list messages about "functional references". In this message I will look into ways to improve upon that concept.

The above links should give you an idea of what a functional reference is, but I will explain it here in my own words. You can skip this introduction if you already know what functional references are.

What are functional references?

A functional reference is a data structure that can be used to update parts of another structure, it is a reference into that structure. We need a way to get the part, and a way to replace the part by setting it to something else. This leads to the data type:

data FRef s a = FRef
      { get :: s -> a
      , set :: a -> s -> s
      }

Now FRef s a represents a reference to an a inside an s structure.

One of the simplest possible (non-trivial) references is that to the first part of a pair:

fst :: FRef (x,y) x
fst = FRef
      { get = \(x,y) -> x
      , set = \x (_,y) -> (x,y)
      }

Having defined this, we can use it to access and modify pairs, for example

> get fst (1,2)
1
> set fst 3 (1,2)
(3,2)

You can read this as "get the first part of ..." and "set the first part to 3 in ...".

Another useful function is update,

update :: FRef s a -> (a -> a) -> (s -> s)
update ref f s = set ref (f (get ref s)) s

Update gets the value, applies a function, and sets it again. This allows us to 'map' functions over parts of data structures:

> update fst (+1) (1,2)
(2,2)

The real power of functional references lies in their composability. Like functions, we can compose two references to give a new one

compose :: FRef b c -> FRef a b -> FRef a c
compose bc ab = FRef
      { get = get bc . get ab
      , set = update ab . set bc
      }

We can now modify nested pairs:

> update (fst `compose` fst) (*2) ((3,4),5)
((6,4),5)

Use case: records

The place where these references shine is with records. Say we have the following data type:

data Employee = Employee
      { name   :: String
      , salary :: Int
      }

It would be great if name and salary where references, then we could simply say

giveRaise = update salary (+100)

This shouldn't be too hard to automate with Data.Derive, the functions would look like

name = FRef
      { get = name_
      , set = \n e -> e { name_ = n }
      }

Or better yet, we could specify references as the default behavior in the next Haskell standard!

There is a problem, however, when we have defined the record accessors to be references. Take the normally legal code

johnsSallary = salary john

This is no longer valid, since salary is not a function. Instead we must write

johnsSallary = get salary john

Type classes to the rescue

Fortunately there is a clean solution to this problem using type classes. We can define the type class

class Ref r where
      ref :: (a -> b) -> (b -> a -> a) -> r a b

We can define an instance for functional references,

instance Ref FRef where
      ref = FRef

As well as for functions

instance Ref (->) where
      ref = const

The record accessors can now be defined as

name :: Ref r => r Employee String
name = ref name_ (\n e -> e { name_ = n })

And all is well again:

giveRaise = update salary (+100)
johnsSallary = salary john

While we are at it, we could also add the (.) operator to the class,

class Ref r where
      ref :: (a -> b) -> (b -> a -> a) -> r a b
      (.) :: r b c -> r a b -> r a c
instance Ref FRef where
      ref = FRef
      (.) = compose
instance Ref (->) where
      ref = const
      (.) = (Prelude..) -- the (.) from the prelude

now

giveRaiseToFirst = update (salary . fst) (+100)

Gives a raise to the first employee in a pair.

Concluding remarks

Note that all this is perfectly valid Haskell 98 code, no extensions are needed. This means that it should not be hard to add such references to the language standard.

There are many more neat things you can do with functional references, but I will save that for another time.

Comments

Nickx

I've been futzing around with Template Haskell trying to write an automatic reference generator. It's not done and working but the parts are pasted at: http://hpaste.org/3018

Pseudonymx

compose :: FRef b c -> FRef a b -> FRef a c

Isn't that an Arrow?

Twanx

Yes, it is *almost* an arrow. More about this in my next post.

Maxx

For those of you reaching here via Google, the next post is located at http://twanvl.nl/blog/haskell/References-Arrows-and-Categories

joshx

IMO http://www.haskell.org/pipermail/haskell-cafe/2007-November/035263.html is less clunky.

Erikx

See also the data-accessor package (and related packages) on hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/data-accessor

Reply