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

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

4 голосов
/ 27 сентября 2011

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

Я хотел бы закодировать в терминах, подобных Haskell Prolog, но каждое решение, которое я придумалесть разные недостатки, которых я бы очень хотел избежать.Я хотел бы найти дешевый и элегантный способ кодирования грамматики 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 можетбыть немного неприятным, чтобы потом управлять кодом (я думаю ... я новичок в Haskell).

Решение 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 ]

7 голосов
/ 27 сентября 2011

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

data Term = TLit    Literal
          | TVar    String
          | TPred   Predicate

data Literal = LitS String
             | LitI Int
             | LitF Double

data Predicate = Predicate String [Term]
2 голосов
/ 28 сентября 2011

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

{-# 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.

...