Defining recursive data types

webNeat commented 6 years ago

Hello, I came across an issue while developing my first library based on sanctuary. Here is a code snippet which explains my issue:

const $ = require ('sanctuary-def')
const {create, env} = require('sanctuary')
const S = create({checkTypes: true, env})

const packageName = 'some-awesome-package'
const packageURL = 'some-short-url'

// helpers to create Enum and Union types
const Enum = (name, values) => $.EnumType(
    `${packageName}/${name}`,
    `${packageURL}#${name}`,
    values
)

const Union = (name, types) => $.NullaryType(
    `${packageName}/${name}`,
    `${packageURL}#${name}`,
    S.anyPass(types.map($.test($.env)))
)

// The actual types
const StringSchema = $.RecordType({
  type: Enum('StringSchemaType', ['string']),
  choices: $.Nullable($.Array($.String)),
  match: $.Nullable($.RegExp),
  minLength: $.Number,
  maxLength: $.Number,
})

const NumberSchema = $.RecordType({
  type: Enum('NumberSchemaType', ['number']),
  min: $.Number,
  max: $.Number,
})

const BooleanSchema = $.RecordType({
  type: Enum('BooleanSchemaType', ['boolean']),
})

const ObjectSchema = $.RecordType({
  type: Enum('ObjectSchemaType', ['object']),
  fields: $.StrMap($.Any) // I want to use Schema here!
})

const Schema = Union('Schema', [
  StringSchema,
  NumberSchema,
  BooleanSchema,
  ObjectSchema
])

As you see I need to use Schema while defining ObjectSchema but I need this later to define the first one as well!

davidchambers commented 6 years ago

I spent several hours defining $.delay within sanctuary-def to support this use case, but eventually realized that $.NullaryType is sufficient. :D

In the following example, SchemaProxy is a nullary type which references Schema in its predicate:

const myEnv = $.env;

const def = $.create ({checkTypes: true, env: myEnv});

//    SchemaProxy :: Type
const SchemaProxy = $.NullaryType ('Schema') ('') (x => $.test (myEnv) (Schema) (x));

//    Schema :: Type
const Schema = $.RecordType ({
  name: $.String,
  children: $.Array (SchemaProxy),
});

//    name :: Schema -> String
const name =
def ('name')
    ({})
    ([Schema, $.String])
    (schema => schema.name);

name ({});
// ! TypeError: Invalid value
//
//   name :: { children :: Array Schema, name :: String } -> String
//           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//                                1
//
//   1)  {} :: Object, StrMap a
//
//   The value at position 1 is not a member of ‘{ children :: Array Schema, name :: String }’.

name ({name: 'Foo', children: null});
// ! TypeError: Invalid value
//
//   name :: { children :: Array Schema, name :: String } -> String
//                         ^^^^^^^^^^^^
//                              1
//
//   1)  null :: Null
//
//   The value at position 1 is not a member of ‘Array Schema’.
//
//   See https://github.com/sanctuary-js/sanctuary-def/tree/v0.16.0#Array for information about the Array type.

name ({name: 'Foo', children: []});
// => 'Foo'

name ({name: 'Foo', children: [{name: 'Bar', children: null}]});
// ! TypeError: Invalid value
//
//   name :: { children :: Array Schema, name :: String } -> String
//                               ^^^^^^
//                                 1
//
//   1)  {"children": null, "name": "Bar"} :: Object, StrMap ???
//
//   The value at position 1 is not a member of ‘Schema’.

name ({name: 'Foo', children: [{name: 'Bar', children: []}]});
// => 'Foo'

name ({name: 'Foo', children: [{name: 'Bar', children: [{name: 'Baz', children: null}]}]});
// ! TypeError: Invalid value
//
//   name :: { children :: Array Schema, name :: String } -> String
//                               ^^^^^^
//                                 1
//
//   1)  {"children": [{"children": null, "name": "Baz"}], "name": "Bar"} :: Object, StrMap ???
//
//   The value at position 1 is not a member of ‘Schema’.

name ({name: 'Foo', children: [{name: 'Bar', children: [{name: 'Baz', children: []}]}]});
// => 'Foo'

Does this approach work for you, @webNeat?

webNeat commented 6 years ago

Hello @davidchambers, Thanks for spending time to investigate this problem. I agree that, in my case, a Nullary type is sufficient. I ended up using the following code, where LazySchema is similar to SchemaProxy you mentioned.

const Enum = (name, values) => $.EnumType(
  `${packageName}/${name}`,
  `${packageURL}#${name}`,
  values
)

const Union = (name, types) => $.NullaryType(
  `${packageName}/${name}`,
  `${packageURL}#${name}`,
  S.anyPass(types.map(type => x => $.test($.env, type, x)))
)

const Lazy = (name, type) => $.NullaryType(
  `${packageName}/${name}`,
  `${packageURL}#${name}`,
  x => $.test($.env, type(), x)
)

const LazySchema = Lazy('Schema', () => Schema)

const StringSchema = _({
  type: Enum('StringSchemaType', ['string']),
  choices: $.Nullable($.Array($.String)),
  match: $.Nullable($.RegExp),
  minLength: $.Number,
  maxLength: $.Number,
})

const BooleanSchema = _({
  type: Enum('BooleanSchemaType', ['boolean']),
})

const ObjectSchema = _({
  type: Enum('ObjectSchemaType', ['object']),
  fields: $.StrMap(LazySchema)
})

const Schema = Union('Schema', [
  StringSchema,
  BooleanSchema,
  ObjectSchema,
])

I am closing this issue as we have a good solution.

davidchambers commented 6 years ago

I am closing this issue as we have a good solution.

:tada:

sanctuary-js / sanctuary-def

Defining recursive data types #196