Hacker News Reader

Comment by posix_monad | Hacker News Reader

MLs require a lot of ceremony modelling simple record types.

What we want to express here is an object with a map of properties (name to type):

    string Type map

For the OOP minded:

    Map<string, Type>

And also compose those:

    type Foo = { "_foo", int }

    type Bar = { "_bar", string }

    type FooBar = mergeMaps Foo Bar

But at compile-time, of course.

Have any languages achieved this? I know TypeScript can do some of these things, but it's clunky.

View on HN

I think what you describe is called "extensible records". Elm had them in a prior version. You can implement them in a language with an expressive enough type system (e.g. Haskell or Scala) without special support, but the syntax can be a bit unwieldy.

Here's three recent papers on extensible records:

* https://arxiv.org/pdf/2108.06296 * https://arxiv.org/pdf/2404.00338 * https://dl.acm.org/doi/pdf/10.1145/3571224

I'm not claiming these are definitive in any sense, but they are useful guides into the literature if any reader wants to learn more. (If you are not used to reading programming language papers, the introduction, related work, and conclusions are usually the most useful. All the greek in the middle can usually be skipped unless you are trying to implement it.)

> I think what you describe is called "extensible records".

From what I read, gp only asks for a way to express the type, not a way to change/extend the type of something during runtime.

Elm's current implementation does this just fine.

This is often referred to as "row typing", and the only language I've ever used that implemented it first-class with polymorphism is Purescript[0]. It's possible to model such things in other languages with sufficiently powerful type systems, though they're normally not as nice to use.

As an aside, Purescript is one of the most fun languages I've ever used for frontend work, and I lament that Elm seems to have overtaken it in the FP community.

[0]: https://hgiasac.github.io/posts/2018-11-18-Record-Row-Type-a...

Even if Elm has had no new version in 4 years while purescript has?

You made me want to try purescript :)

The construction of the type 'Map<string, Type>' is entirely standard in languages like Agda and Coq (and I bet Idris too). In these languages, Type is itself a type, and can be treated like any other type (like string or int). Nothing clunky about it. (If you're curious, Type is usually referred to as a "universe type" in type theory circles.)

Haskell does it just fine with the HasField typeclass, but like everything Haskell, it's not always easy to find the information.

    type HasFooBar s = (HasField "_foo" s String, HasField "_bar" s String) => s

Ok, but why?

I like the beauty of an expressive type system as much as the next guy, but is there any scenario where:

    type FooBar = mergeMaps Foo Bar

Is better for solving real-world problems than

    type FooBar = { "_foo", Foo, "_bar", Bar }

or whatever?

With mergeMaps, you don't have to write out all of the properties.

The Ceylon language allowed you to do that sort of thing with types. If you "added" two maps together of types `Map<String, int>` and `Map<String, String>`, you would get back a `Map<String, String | int>` (or, equivalently, `Map<String, String> | Map<String, int>`).

But for some slightly complex reasons, most language designers find adhoc union types (which are required for this to work) a bad idea. See the Kotlin work related to that, they explicitly want to keep that out of the language (and I've seen that in other language discussions - notice how tricky it can be to decide if two types are "the same" or whether a type is a subtype of another in the presence of generalized unions) except for the case of errors: https://youtrack.jetbrains.com/issue/KT-68296/Union-Types-fo...

> If you "added" two maps together of types `Map<String, int>` and `Map<String, String>`, you would get back a `Map<String, String | int>` (or, equivalently, `Map<String, String> | Map<String, int>`).

But these are obviously not equivalent: the first type is a map where all values are either strings or ints, and the second one is either a map where all values are strings, or all values are ints.

If that's confusing, consider: {foo: 1, bar: "2"}. It satisfies `Map<String, String | int>` but not `Map<String, String> | Map<String, int>`.

(In fact, the latter is a subtype of the former.)

P.S. You also seem to have misunderstood the toplevel comment about modeling record types as maps, as being about typing maps that exist in the language.

These types are equivalent if you consider a value of both of these types have the exact same read operations. Calling `get(String)` will return `String | int` in both cases. You're right that you could build a value of one of these types that does NOT conform to the union, however. I am not sure what's the technical name for what I am trying to say... are they "covariantly equivalent"???

EDIT: ok, I just wanted to say that one type, `Map<String, String | int>`, is a supertype of `Map<String, int> | Map<String, String>`, so if a function accepts the former, it also accepts the latter. They're not equivalent but you can substitute one for the other (one way only) and still perform the same operations (always assuming read-only types, if you introduce mutation everything becomes horrible).

I was trying to emphasize how having type "combinations" ends up causing the type system to become undecidable as you end up with infinite combinations possible, but as I haven't really gone too deeply into why, I am having trouble to articulate the argument.

> you would get back a `Map<String, String | int>` (or, equivalently, `Map<String, String> | Map<String, int>`)

How are these equivalent? Wouldn't the latter result in {foo:1, foo:"two"}, where the former wouldn't?

OCaml's first-class modules allow you to do this: https://ocaml.org/play#code=bW9kdWxlIHR5cGUgRk9PID0gc2lnCiAg...

Ocaml object system can also achieve this in a quite lightweight way

    type foo = < foo:int >
    type bar = < bar:int >
    type k = < foo; bar >
    type u = < k; baz:int >
    let f (x: <u; ..>) (\* the type annotation is not needed \*) = x#m

The most consistent solution with the least ceremony. Now it is a module, not a type though.

You can create first-class values of this module type, and since values have types, "it" is a type. Specifically, my_foobar has type (module FOOBAR).

Actually getting values out of such a module-typed structure does involve some ceremony, however:

    let f =
      let module M = (val my_foobar) in
      M.foo

Hence, Objective Caml! This can be modeled in OCaml as an object type,

  type foo_bar = < _foo : int; _bar : string >

For a family of types matching any object with those methods, I think you can write something like

  type 'a has_foo_bar = < _foo : int; _bar : string; .. > as 'a

You can easily do composable tagged (by index type or even comp time strings) tuples in C++. The syntax is not pretty, but there is minimal to non-existent overhead.

On the other hand, thanks to the loose "duck typed" nature of templates, you can write functions that act on a subset of the fields of a type (even type checking it with concepts) while preserving the type of the whole object.

Scala 3 can do it with some macro tricks. But the performance is not as good as with nominally typed structures.

Go structs sorta behave this way if you put a "parent" struct in the first field of a struct definition. They are, of course, not maps though. But a map with statically defined keys/values/types is basically a struct.

I am cheating a bit by naming a non-general purpose language, but Nickel[1] does that, for example through composing contracts.

[1]: https://nickel-lang.org/

Not sure whether this is what you intended, but Go structs can embed other structs

    type Foo struct {
     foo int
    }

    type Bar struct {
     bar string
    }

    type FooBar struct {
     Foo
     Bar
    }

This doesn't function as an interface though. You cannot pass a FooBar to a function that expects a Foo, for example, and although you can fairly easily reference the Foo-part of a FooBar instance (`foobar.Foo`) there is no way to pass e.g. an array of FooBar instances to a function that takes a slice of Foo[] as its argument. That's the problem to be solved.

Ok, Go generics is pretty limited but you can achieve this in C++ via concepts.

    #include <iostream>
    #include <string>
    #include <type_traits>

    // Concept to check for 'foo' field of type int
    template <typename T>
    concept HasFooInt = requires(T t) {
        { t.foo } -> std::convertible_to<int>;
    };

    // Concept to check for 'bar' field of type string
    template <typename T>
    concept HasBarString = requires(T t) {
        { t.bar } -> std::convertible_to<std::string>;
    };

    // Generic function that accepts T with either 'foo' or 'bar'
    template <typename T>
    requires HasFooInt<T> || HasBarString<T>
    void printField(const T& t) {
        if constexpr (HasFooInt<T>) {
            std::cout << "foo: " << t.foo << std::endl;
        } else if constexpr (HasBarString<T>) {
            std::cout << "bar: " << t.bar << std::endl;
        }
    }

    struct Foo {
        int foo;
    };

    struct Bar {
        std::string bar;
    };

    struct FooBar {
        int foo;
        std::string bar;
    };

    int main() {
        Foo s1 { 42 };
        Bar s2 { "hello" };
        FooBar s3 { 100, "world" };

        printField(s1); // prints: foo: 42
        printField(s2); // prints: bar: hello
        printField(s3); // prints: foo: 100 (prefers foo due to order of checks)
        
        return 0;
    }

Totally achievable by using interfaces instead of structs

    type Foo interface {
      Foo() int
    }

    type Bar interface {
      Bar() string
    }

    type FooBar interface {
      Foo
      Bar
    }

Then functions that accept a Foo will also happily take a FooBar. Does not solve the problem of passing a FooBar[] to a function that expects Foo[] but that can be solved with generics or a simple function to convert FooBar[] to Foo[].

That sounds achievable at compile-time in c++ with some type-level map implementation such as in boost.mp11 (sadly the language does not allow general use of types as values preventing the use of standard map containers).

I raise the bar and say the relational model has it and can be made to work at type level.

    type Person = User DESELECT password
    type Invoice = Customer JOIN Inv

Something like this in TypeScript:

    type Person = Omit<User, 'password'>
    type Invoice = Customer & { invoice: Inv }
    // or
    type Invoice = Inv & { customer: Customer }

> Have any languages achieved this?

”The MLs” solved it decades ago. Standard ML has very nice record types.

Reply on news.ycombinator.com