[Haskell-cafe] Re: I just don't get it (data structures and OO)

[Arie Peterson]

You could also use 'compositional functional references'. These are
introduced in the paper "A Functional Programming Technique for Forms in
Graphical User Interfaces" by Sander Evers, Peter Achten and Jan Kuper.

=== Introduction ===

There are two things one typically wants to do when working with a
substructure of some larger data structure: (1) extract the substructure;
and (2) change the larger structure by acting on the substructure. A 'Ref
cx t' encodes both of these functions (for a substructure of type 't' and
larger structure (context) of type 'cx').

> data Ref cx t
>  = Ref
>    {
>      select :: cx -> t
>    , update :: (t -> t) -> cx -> cx
>    }

A Ref is a bit like a typed and composable incarnation of apfelmus's
indices, or a wrapper around Tillmann's change* functions, containing not
only a setter but also the accompanying getter.

=== Use ===

These Refs are compositional: given 'x :: Ref a b' and 'y :: Ref b c', we
can form

> z :: Ref a c
> z = Ref
>     {
>       select = select b . select a
>     , update = update a . update b
>     }

. In fact we can almost make 'Ref' into an arrow. (Only 'pure :: (a -> b)
-> Ref a b' does not make sense, because a pure function 'f : a -> b'
doesn't give information about how to transform a change in 'b' into a
change in 'a'.)

I've written a template haskell function to derive Refs from a data
structure definition (with record syntax): given

> data Universe
>   = Universe
>     {
>       galaxies :: [Galaxy]
>     }

, it creates

> galaxiesRef :: Ref Universe [Galaxy]

. Together with some Ref functions for container types (List, Map, etc.)
this eliminates most (all?) necessary boilerplate code.


Greetings,

Arie