Hi Ignat, as an example of what an extensible records system might look like in Haskell, you could play with Hugs.Trex -- https://www.haskell.org/hugs/pages/hugsman/exts.html#sect7.2
To match a few of its features to your post:
> suppose I have two functions: one is a layout algorithm that assigns to nodes some spatial positions, and the second is a topological algorithm that discerns roots and leaves. These two functions are conceptually independent and ...
r1 = (label = blah1)
r2 = (topology = blah2 | r1)
r3 = (v2 = blah3 :: Double | r2)
The `( ... | r1)` means extend `r1` with some extra field or fields comma-separated. This is an 'extensible' 'anonymous' records system -- 'anonymous' in that you don't pre-declare your record types via `data`. You can name your record types, either with a `type` decl or with a `newtype` that provides a constructor for known-in-advance types.
> may be applied in any order,
Yes you can extend an existing record with arbitrary fields, the result is always a 'flat' tuple with the labels-value pairs forming a set: two records are same type providing they have the same set of labels and the same field types at each label, irrespective of how the labels got added.
> I would like to make sure their fields are not mixed.
> I need to be able to add more and more fields to labels, but in such a way that it is impossible to assign an unsuitable field.
There's a so-called 'lacks' constraint you can put on record operations (written with backslash):
foo :: r1\topology => Rec r1 -> a -> Rec (edges :: a | r1)
is the type of a function that will extend record type `r1` lacking label 'topology' with a field `edges` at type `a`.
You can put record types with lacks constraints on instances:
instance (r2\v2) => Foo (Rec (label :: String | r2)) (Rec (v2 :: Double, label :: String | r2)) where ...
holds for any record that includes label `label` at `String`, and possibly other labels in `r2`, but lacks `v2`. (I'm presuming there's a FunDep on Foo so the second instance parameter is the return type.)
> a huge number of `HasThis` and `HasThat` instances
That instance head is in effect a `Has` `label` constraint. There's also a shorthand `#label` that generates a function to extract the value at `label` **from any record with a `label`** -- that is, Hugs infers the `Has` constraint for you.
> it seems to me that some smart technology is needed to make this manageable.
I'm not seeing Trex as 'smart'. It follows conventional relational algebra semantics; was developed ~1996; last release of Hugs was 2006. I'd have thought GHC would come up with something comparable by now. As Olaf's and Henning's replies show, you could fake it with "a lot of boilerplate" and/or some dubious type trickery.
AntC