Discuss: Homogeneous maps

[Gabriella439]

This is an informal sketch of an idea to add homogeneous maps to the language.

Here is the idea:

• Add a {{ ... }} syntax for authoring a homogeneous map

  It could be any syntax. I'm not married to that particular choice, so feel free to suggest
  alternative syntax ideas

• Add a built-in Map : Type → Type constructor

Example:

{{ foo = 1, bar = 2 }} : Map Natural

• Add two built-in functions

  • Map/length : ∀(a : Type) → Map a → Natural
  • Map/map : ∀(a : Type) → ∀(b : Type) → (a -> b) -> Map a -> Map b

Carefully note here that:

• Keys are not computed

  Specifically, map keys cannot be derived from Text values

• The Map type is not parametrized on the key type

In other words, the key type is essentially opaque. You could pretend that the keys are "symbol" or "atom"s (to use terminology from other languages)

These latter two constraints mean that this proposed support for homogeneous maps could not be used as a backdoor for comparing Text values for equality.

Notably, there would probably not be support for accessing values by key (i.e. no someMap.key support) since in that case the user more likely wanted a record instead of a Map.

We also add Sets in the same way if the Set type were not parametrized (i.e. it could only store sets of field names):

{{ foo, bar }} : Set

... but for now I'm limiting the proposal to just homogeneous maps.

I'm making this a separate issue from #234 which is more about how to make it easier to author association lists, whereas this is more about how to replace association lists with true homogeneous maps. This would not obsolete the other issue because users would probably still want a way to convert homogeneous records to homogeneous maps.

[philandstuff]

Is it worth sketching some use cases for this feature, to make it clear what we’re designing for? I guess anywhere that someone uses dhall-json’s mapkey/mapvalue thing.

I can certainly imagine using this for generating terraform json. Something like:

{aws_iam_role =
  {{`nginx-task-role` = MakeRole ...
  ,  `nginx-execution-role` = MakeRole ...
  }}
}

Where we are using a homogeneous map to define multiple aws_iam_role instances.

[singpolyma]

I'm honestly more interested in more ergonomics / best practises around association lists than a whole other Map type and syntax.

[ocharles]

I am curious how far this can go without a foldWithKey/toList primitive. Not saying it's a must, just something for me to think about

[ari-becker]

I'm not clear with what the use-case for this is. If there is no support for accessing values by key, then what added value is there in using a Map over a List?

[Gabriella439]

@ari-becker @philandstuff: It's mainly for ergonomics, but if people don't strongly desire this feature then I can hold off on it. The context for this was that I was expanding the page on design choices to explain why the language couldn't add support for homogeneous maps, but then I realized that it could.

The main use case I can think of for this is nicer syntax when generating types that are translated to JSON or YAML

[f-f]

The main use case I can think of for this is nicer syntax when generating types that are translated to JSON or YAML

I'm also having doubts about use-cases for this feature. If this is the goal then it seems to me that the mapKey/mapValue support is strictly more powerful (because keys are not opaque and don't have to be known at compile time and this is useful in many cases, I can detail more if needed) so maybe we're better off making ergonomics nicer for that?

[singpolyma]

The main issue I currently have with association lists in Dhall is that they cannot be generically marshalled as maps in an implementation. dhall-to-json currently solves this by having a command line argument that allows specifying the record selector for keys. I think it might be useful to solve this in a more reusable way. I can think of three ways to do this:

1. Support for unnamed tuples: { "key", "value" } and re-use the common convention that the first element is the key
2. Publish a best-practise along with Dhall to use a particular selector (probably key) when intending to build an associative list. Use this practise for standard associative lists (such as import headers).
3. A language feature that marks a particular record selector as "first", such as: { !key = "key", value = "value" } or { <key> = "key", value = "value" }

[f-f]

@singpolyma if I read your comment correctly I'll note that right now we're doing 2.
I.e. the defaults in dhall-json for associative lists are mapKey/mapValue (we settled on this because key is too common in business domains) and they are a "best practice" and used everywhere we need associative lists (e.g. in the Prelude).
They might not be properly documented though 😄

[singpolyma]

I'll note that right now we're doing 2. I.e. the defaults in `dhall-json` for associative lists are `mapKey`/`mapValue` (we settled on this because `key` is too common in business domains) and they are a "best practice" and used everywhere we need associative lists.

I would argue that a dhall-to-json feature not mentioned in dhall-lang hardly counts as a "best practise" though it may indeed form the basis for one. There *is* an associative list defined in the standard, for import headers, and it uses the selector "header" for the key.

[f-f]

@singpolyma you most likely missed my edit to the message above, but it's also used in the Prelude so I'd consider this as a "mention" in dhall-lang

[Gabriella439]

One thing we could do is add a Map type to the Prelude, defined like this:

let Map : Type → Type = λ(a : Type) → List { mapKey : Text, mapValue : a }

in  Map

[singpolyma]

‎> let Map : Type → Type = λ(a : Type) → List { mapKey : Text, mapValue : a } I think this could be good, though I would take a key type as well (to allow for symbol keys like <prod|test> for example) What do people think about moving the import headers to be this kind of map?

[Gabriella439]

@singpolyma: One other thing: if we allow parametrizing on the key-type, then we have the option of using a record to store the type parameters instead of passing them positionally, like this:

let Map
    : { key : Type, value : Type } → Type
    =   λ(type : { key : Type, value : Type })
      → List { key : type.key, value : type.value }

in  Map

... that way you can write:

let Headers = Map { key = Text, value = Text }

in  …

This takes advantage of Dhall's support for type-level records.

[singpolyma]

I don't think I feel strongly on this vs the curried version, but others may.

[Gabriella439]

Thinking about it more, it's probably better to curry, if only so that it's easier to partially apply, which will be a common use case

[Gabriella439]

I ran into a minor issue when attempting to add the above Map to the Prelude, which is that it's not obvious where to put it. If we save the file as ./Prelude/Map then we can't use that as the name of the directory for any Map-related utilities (like Map/map, Map/keys, Map/values, etc.).

[Nadrieril]

Prelude/Map/type.dhall ? That could become a common convention, like module.t in OCaml

[Gabriella439]

@Nadrieril: If we add a .dhall suffix then it could be ./Prelude/Map.dhall

[Gabriella439]

Pull request for adding Map to Prelude is up here: #575

[philandstuff]

I think this is done now. Closing (feel free to reopen if I’m wrong)