Расширение существующего типа в OCaml

Question

В последнее время я занимался программированием на OCaml, чтобы выучить язык и познакомиться с функциональным программированием. Недавно я начал думать, что хотел бы иметь возможность расширять существующий тип (встроенный или собственный), например:

type bexp =
  And of bexp * bexp
| Or of bexp * bexp
| Xor of bexp * bexp
| Not of bexp;;

Теперь предположим, что я хочу добавить вариант Nop к этому типу, но только для использования в новом типе - что-то вроде наследования. Эй, это должны быть алгебраические типы данных, верно? Так почему бы не что-то вроде:

type nbexp = bexp | Nop nbexp ;;

... но это недопустимый OCaml, он выдает синтаксическую ошибку. По сути, я пытаюсь сказать, что я хочу, чтобы nbexp включил все, что включает в себя bexp, а также добавил к этому Nop. Я предполагаю, что это невозможно, потому что, если, например, вы использовали конструктор And, не было бы способа определить, был ли это тип bexp или тип nbexp. (Я думаю, что конструктор Nop, принимающий nbexp, также может быть проблематичным.)

Так есть ли способ сделать что-то подобное в OCaml? И можно ли это реализовать в Haskell (возможно, с классами типов)?

Answer 1

Интересным решением является использование полиморфного варианта:

type bexp =
[ `And of bexp * bexp
| `Or of bexp * bexp
| `Xor of bexp * bexp
| `Not of bexp ];;

type nbexp = [ bexp | `Nop of nbexp ];;

Обратите внимание, что полиморфные варианты сложнее обычных, но допускают расширение типа.

Интересный пример оценки выражения с расширением с использованием полиморфного варианта можно найти в справочных каталогах источника ocaml, см. svn

Answer 2

Как вы сами правильно догадываетесь, это невозможно в алгебраических типах. Я согласен с предложением Apocalisp, что вы можете просто обернуть «унаследованную» часть nbexp в свой собственный конструктор.

Я бы добавил, что отсутствие наследования алгебраических типов является частью их чудесности. Это означает, что выражение типа And(foo, bar) набрано недвусмысленно, и приведение (вверх или вниз) не играет никакой роли в системе типов. Это обеспечивает как большую безопасность, так и большую ясность. Конечно, от программиста требуется, чтобы он / она явно обрабатывал случаи, когда он / она хочет взаимодействовать с bexp частями nbexp, но если вы подумаете об этом, именно так достигается повышенная безопасность и ясность на практике.

Answer 3

Эй, это должны быть алгебраические типы данных, верно?

правый. И алгебраические типы данных создаются с помощью теговых (или дискриминируемых) объединений и продуктов. То, что вам нужно, - это просто (без тегов) объединение, которое не является алгебраическим типом данных и не поддерживается Haskell. OCaml имеет полиморфные варианты (см. Другие ответы).

Типизированная схема поддерживает не отмеченные тегами союзы, так что вы можете проверить это.

Answer 4

Обновление: Ocaml теперь имеет расширяемые типы. http://caml.inria.fr/pub/docs/manual-ocaml/extn.html#sec246

Здесь вы бы сделали

type bexpr += Nop of bexpr