Type Inference for Plain Data
11 days ago
- #haskell
- #type-inference
- #json
- The post explains how to implement type inference for plain data structures like JSON or YAML.
- It introduces a `Type` datatype in Haskell to represent JSON types, inspired by TypeScript.
- The goal is to implement an `infer` function that converts a JSON `Value` to its inferred `Type`.
- Key cases for `infer` include handling strings, booleans, numbers, nulls, arrays, and objects.
- For arrays, the post details a unification algorithm to merge element types into a single type.
- A `Monoid` instance for `Type` is implemented to facilitate unification via `mempty` and `(<>)`.
- The unification laws ensure that the inferred types are supertypes of all possible input types.
- The post includes proof sketches showing that the implementation satisfies monoid and unification laws.
- The final implementation is concise, leveraging Haskell's type system and monoid properties.