Расширение типа данных в Haskell

Ответ 1

Эта проблема была названа "проблемой выражения" Фила Вадлера, по его словам:

Цель состоит в том, чтобы определить тип данных по случаям, где можно добавить новые типы данных к типу данных и новым функциям над типом данных без перекомпиляции существующего кода и при сохранении безопасность статического типа.

Одно из решений иметь расширяемый тип данных - использовать классы типов.

В качестве примера допустим, что у нас есть простой язык для арифметики:

data Expr = Add Expr Expr | Mult Expr Expr | Const Int

run (Const x) = x
run (Add exp1 exp2)  = run exp1 + run exp2
run (Mult exp1 exp2) = run exp1 * run exp2

например.

ghci> run (Add (Mult (Const 1) (Const 3)) (Const 2))
5

Если мы хотим реализовать его расширяемым образом, мы должны переключиться на классы типов:

class Expr a where
    run :: a -> Int


data Const = Const Int

instance Expr Const where
    run (Const x) = x


data Add a b = Add a b

instance (Expr a,Expr b) => Expr (Add a b) where
    run (Add expr1 expr2) = run expr1 + run expr2


data Mult a b = Mult a b

instance (Expr a, Expr b) => Expr (Mult a b) where
    run (Mult expr1 expr2) = run expr1 * run expr2

Теперь давайте расширим язык, добавляя вычитания:

data Sub a b = Sub a b

instance (Expr a, Expr b) => Expr (Sub a b) where
    run (Sub expr1 expr2) = run expr1 - run expr2

например.

ghci> run (Add (Sub (Const 1) (Const 4)) (Const 2))
-1

Для получения дополнительной информации об этом подходе и вообще о проблеме с выражением отметьте видео Ralf Laemmel 1 и 2 на канале 9.

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

[Add (Const 1) (Const 5), Const 6] -- does not typecheck

В функциональном жемчуге "Типы данных a la carte" представлено более общее решение с использованием копедуктов сигнатур типа.. См. Также Wadler комментарий на бумаге.

Ответ 2

Вы можете сделать что-то более похожее на ООП, используя экзистенциальные типы:

-- We need to enable the ExistentialQuantification extension.
{-# LANGUAGE ExistentialQuantification #-}

-- I want to use const as a term in the language, so let hide Prelude.const.
import Prelude hiding (const)

-- First we need a type class to represent an expression we can evaluate
class Eval a where
  eval :: a -> Int

-- Then we create an existential type that represents every member of Eval
data Exp = forall t. Eval t => Exp t

-- We want to be able to evaluate all expressions, so make Exp a member of Eval.
-- Since the Exp type is just a wrapper around "any value that can be evaluated,"
-- we simply unwrap that value and call eval on it.
instance Eval Exp where
  eval (Exp e) = eval e

-- Then we define our base language; constants, addition and multiplication.
data BaseExp = Const Int | Add Exp Exp | Mul Exp Exp

-- We make sure we can evaluate the language by making it a member of Eval.
instance Eval BaseExp where
  eval (Const n) = n
  eval (Add a b) = eval a + eval b
  eval (Mul a b) = eval a * eval b

-- In order to avoid having to clutter our expressions with Exp everywhere,
-- let define a few smart constructors.
add x y = Exp $ Add x y
mul x y = Exp $ Mul x y
const   = Exp . Const

-- However, now we want subtraction too, so we create another type for those
-- expressions.
data SubExp = Sub Exp Exp

-- Then we make sure that we know how to evaluate subtraction.
instance Eval SubExp where
  eval (Sub a b) = eval a - eval b

-- Finally, create a smart constructor for sub too.
sub x y = Exp $ Sub x y

Таким образом, мы фактически получаем один расширяемый тип, чтобы вы могли, например, смешивать расширенные и базовые значения в списке:

> map eval [sub (const 10) (const 3), add (const 1) (const 1)]
[7, 2]

Однако, поскольку единственное, что мы теперь можем знать о значениях Exp, это то, что они как-то являются членами Eval, мы не можем сопоставлять шаблон или делать что-либо еще, что не указано в классе типов. В терминах ООП, подумайте о значении Exp exp, как об объекте, реализующем интерфейс Eval. Если у вас есть объект типа ISomethingThatCanBeEvaluated, очевидно, что вы не можете смело использовать его в чем-то более конкретном; то же самое относится к Exp.

Ответ 3

Синтаксический сахар обычно обрабатывается парсером; вы должны расширить (не в смысле OO-наследования) парсер для обнаружения новых конструкций и перевести их в структуры, которые может обработать ваш оценщик.