Рекурсивные структуры данных в haskell: пролог-подобные термины

У меня есть вопрос о рекурсивных структурах данных в языке Haskell (язык, который я сейчас пытаюсь изучить).

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

Просто в качестве напоминания, некоторые термины пролога могут быть male, sum(2, 3.1, 5.1), btree(btree(0, 1), Variable).

Решение 1 

data Term = SConst String
          | IConst Integer
          | FConst Double
          | Var    String
          | Predicate   {predName :: String, predArgs :: [Term]}

С помощью этого решения я могу иметь вложенные предикаты (так как predArgs являются Term), но я не могу отличить предикаты от других терминов в сигнатурах типа.

Решение 2 

data Term = SConst String
          | IConst Integer
          | FConst Double
          | Var    String

data Predicate = Predicate {predName :: String, predArgs ::[Either Term Predicate}

В этом варианте я могу четко отличать предикаты от базовых терминов, но тип Either в списке predArgs может быть довольно неприятным для управления позже в коде (я думаю... Я новичок в Хаскелле).

Решение 3 

data Term = SConst String
          | IConst Integer
          | FConst Double
          | Var    String
          | Struct String [Term]

data Predicate = Predicate String [Term]

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

Это так же, как решение 1 с двумя конструкторами предикатов для терминов. Один из них-это рекурсия, Struct, а другой, Predicate, должен уметь различать предикаты и регулярные термины.

Проблема с этой попыткой состоит в том, что Struct и Predicate структурно эквивалентны и имеют почти одинаковое значение. то есть, но я не смогу написать функции, которые работают - в примере-как на (Predicate "p" []), так и на (Struct "p" []).

Итак, снова мой вопрос: пожалуйста, есть ли лучший способ кодировать мои предикаты и термины так, чтобы:

  1. я могу различать предикаты и термины в сигнатурах типов;
  2. поддерживаются вложенные предикаты типа p(q(1), r(q(3), q(4)));
  3. я могу написать функции, которые будут работать равномерно на предикатах, без каких-либо различие, подобное тому, что в решении #3?
Пожалуйста, не стесняйтесь обращаться ко мне за дальнейшими разъяснениями, если они вам понадобятся.

Большое вам спасибо.

2 4
haskell grammar bnf

2 ответа:

Можно добавить конструктор термов для обертывания предиката. Здесь я также учитывал все литералы в их собственном типе данных: 

data Term = TLit    Literal
          | TVar    String
          | TPred   Predicate

data Literal = LitS String
             | LitI Int
             | LitF Double

data Predicate = Predicate String [Term]
7

Вот один из способов (это, вероятно, не стоит хлопот): 

{-# LANGUAGE EmptyDataDecls #-}

-- 'T' and 'F' are short for 'True' and 'False'
data T = T
data F

-- 'p' is short for 'mayNotBeAPredicate'
data Term p
    = SConst !p String
    | IConst !p Integer
    | FConst !p Double
    | Var    !p String
    | Predicate {predName :: String, predArgs :: [Term T]}

sconst :: String -> Term T
iconst :: Integer -> Term T
fconst :: Double -> Term T
var :: String -> Term T
predicate :: String -> [Term T] -> Term p
sconst = SConst T
iconst = IConst T
fconst = FConst T
var = Var T
predicate = Predicate

checkPredicate :: Term p -> Maybe (Term F)
checkPredicate (Predicate name args) = Just (Predicate name args)
checkPredicate _ = Nothing

forgetPredicate :: Term p -> Term T
forgetPredicate (SConst _ s) = sconst s
forgetPredicate (IConst _ i) = iconst i
forgetPredicate (FConst _ f) = fconst f
forgetPredicate (Var    _ s) = var s
forgetPredicate (Predicate name args) = predicate name args
Теперь можно писать функции, которые принимают только предикаты, задавая им входной тип Term F, и функции, которые принимают любой входной тип, задавая им входной тип Term p.
2