Лучшее представление рекурсивной полиморфной структуры типа - PullRequest
Новая
       23

Лучшее представление рекурсивной полиморфной структуры типа

0 голосов
/ 03 октября 2018

Я реализую дерево.Во время выполнения моей программы данные добавляются в узел.

Код ниже показывает мою первую реализацию: 

type 'a tree =
  | Node of 'a
  | Leaf

type nodata_node =
  {
    b: nodata_node tree;
  }

type data_node =
  {
    a: int;
    b: data_node tree;
  }

Проблема с этой реализацией состоит в том, что я не могу представить значениеb в следующем фрагменте: 

let a = { b = Node { b = Leaf } }

let b = { b = Node { a = 1; b = Leaf } }

Мне нужно иметь возможность представить node, у которого нет data, но у всех детей есть.

Так что япредложил следующую реализацию: 

type _ data =
  | Unknown : unit -> unit data
  | SomeInt : int -> int data

type 'a tree =
  | Node of ('a, 'a) node
  | Leaf

and ('a, 'b) node =
  {
    a: 'a data;
    b: 'b tree;
  }

let a = { a = Unknown (); b = Node { a = Unknown (); b = Leaf } }

let b = { a = Unknown (); b = Node { a = SomeInt 1; b = Leaf } }

Это работает, но кажется немного неуклюжим иметь поле, которое сначала пустое, а потом заполняется.Мне было интересно, есть ли способ получить представление, эквивалентное второму, но с решением, аналогичным первому, в котором узел без данных не представлен структурой с пустым полем данных.

РЕДАКТИРОВАТЬ: теперь я понимаю, что мое использование GADT не приносит много в вопрос, который я задаю, поэтому вот более простая версия моей второй попытки: 

type 'a tree =
  | Node of ('a, 'a) node
  | Leaf

and ('a, 'b) node =
  {
    a: 'a;
    b: 'b tree;
  }

let a = { a = (); b = Node { a = (); b = Leaf } }

let b = { a = (); b = Node { a = 1; b = Leaf } }

EDIT2: Я думаю, что есть способсделать это с помощью функторов и взаимно рекурсивного определения.Меня интересует решение, которое не опирается на функторы.

1 Ответ

0 голосов
/ 03 октября 2018

Если вы хотите сохранить конструктор типа 'a tree, вы можете выбрать: 

type 'a tree =
  | Node of 'a
  | Leaf
type child_node = {data:int; x: child; y:child}
and child = child_node tree
type parent = child tree

let x: parent = Node (Node {data=0; x=Leaf; y = Leaf})
...