Map & ReadonlyMap support

[toastal]

Feature request: Map support

Current Behavior

No support

Desired Behavior

Map are a useful data structure to use, especially since the keys can be just about anything.

Suggested Solution

import * as IO from "io-ts"

export interface MapC<K extends IO.Mixed, V extends IO.Mixed>
  extends IO.Type<
    Map<IO.TypeOf<K>, IO.TypeOf<V>>,
    Map<IO.OutputOf<K>, IO.OutputOf<V>>,
    unknown
  > {}

export function Map<K extends IO.Mixed, V extends IO.Mixed>(
  keyCodec: K,
  valueCodec: V,
  name: string = `Map<${keyCodec.name}, ${valueCodec.name}>`
): MapC<K, V> {
  return // unsure
}

Unsure what comes from here. The Map constructor can take an array of tuples or other iterable. I'm new to TypeScript and am not sure how to model this.

Who does this impact? Who is this for?

All users

Describe alternatives you've considered

Creating a Codec with an array of Tuples, then on decode map((x) => new Map(x), myArrayOfTuples) transform the output. The part I don't understand is how to compose Types that well (similar to ∀ i k v. Interable i ⇒ IO.Type (i (Tuple k v)) → IO.Type (Map k v))--I understand composing Codecs but not Types and the documentation is very sparse on io-ts.

Your environment

Software	Version(s)
fp-ts	2.11.5
io-ts	2.2.16
io-ts-types	0.5.16
TypeScript	4.5.4

[mlegenhausen]

Actually the usefulness in a fp-ts context for Map is pretty low. There is a discussion in the fp-ts issue tracker about this. The problem with Map is that the key is compared by reference which breaks referential transparency. To work around that you need to iterate over the whole Map and compare each key via an Eq instance with your lookup key. Which increases the runtime complexity to O(n).

For making this Typ beneficial for the io-ts cosmos a mapFromRecord codec would be great cause normally the output type of a codec is serializable. See setFromArray as reference.

[toastal]

I actually made an attempt at ReadonlyMap (I left a message to review it on #fp-ts @ Libera.Chat, but hadn't gotten a response) that is working for me. I understand the issue here. The difference is that Map can have keys that are more "arbitrary". In an example using a newtype USD = USD number:

// this is weird key, but people like using currencies for Newtypes
const m: Map<USD, string> = new Map()
const a: USD = isoUSD.wrap(1)
m.set(a, "test")

console.log("test map:", m)
//=> test map: Map { 1 → "test" }
console.log("get a:", m.get(a))
//=> get a: test
console.log("get new:", m.get(isoUSD.wrap(1)))
//=> get new: test
console.log("get new wrong:", m.get(isoUSD.wrap(2)))
//=> get new wrong: undefined
console.log("get 1:", m.get(1))
// did not complie

What I can't do with Records is Record<USD, string>. Restricting to keys of only number | string | symbol loses you a fair amount of type safety; we don't want stringly-typed programs. I think my situation may be a bit of an asterisk though as, I'm using this only to Map.prototype.get from the structure (decoded JSON for viewing). I noted the reference thing when creating new Objects and it failing to get the key, however, the Newtypes seem to work (and I don't know enough about TypeScript to begin to guess why).

Would be interesting to have real world examples where a Map is more superior than a Record in a functional programming context. In my 10 years programming exclusively JS I never had the need for a Map.

@mlegenhausen as you asked in that issue though, this would at least seem to me like a valid use case.

So what is the solution for something like Dictionary<Newtype, A>?

Obviously you could create a structure that uses a type that is valid and partially apply a Lens to go to/from the compatible types or use a Lens over the whole structure, but I'd prefer something better. There's a myriad of wrappers around Elm's Dict as the keys need to be comparable in Map comparable a and without typeclasses, adhoc versions sprung up to address for instance not being able to use enums as keys with a (a -> comparable) argument.

The other solution would be if newtype-fs had a way to be represented one way to the compiler and then factored out/replaced on compilation like Elm does for data Foo = Foo String where it become type Foo = String. However its Newtypes seem to be a literal object looking more like the Haskell newtype Foo = Foo { unFoo :: String } with interface Foo extends Newtype<{ readonly Foo: unique symbol }, string> {}.

[mlegenhausen]

We do actually the same, using newtypes as keys but we go the Record<string, A> route and create access and manipulation functions that do the Newtype to string conversion so we can use lenses from monocle-ts. This worked actually pretty good for us and is compatible with fp-ts.

I find your example interesting, but for getting the same performance I would need the same trick and create my own access function and sacrifice serializability which is pretty useful for debugging.

You can try if branded types would give you better type-safety on record keys.

Or you could actually use Newtype again and hide the Record<string, A> type.

interface Money extends Newtype<{ readonly Money: unique symbol }, Record<string, string>> {}

function get(dollar: USD): (money: Money) => string {
  return money => pipe(money, isoMoney.unwrap, RR.lookup(isoUSD.unwrap(dollar))
}

This will be a little bit more wrap and unwrap but I think you get the maximum type safety.

[toastal]

Seems like there should be a compromise in the form of a data structure everyone can use, ya know? Newtyping everything is good and should be encourage which having easy ergonomics and performance optimized for all end users.