Поиск наиболее общего унификатора в Haskell с использованием Data.Comp.Unification (вопрос для начинающих)

У меня есть следующая структура в haskell, которая реализует некоторые механизмы для печати и вызывает унификатор. Я получаю следующую ошибку от main:

0 =/= int

Кажется, что 0 - это число, а не переменная. Ниже приведена полная реализация.

 data CType 
      = CVar Int 
      | CArr CType CType
      | CInt
      | CBool
      deriving (Eq, Data)

data Constraint 
  = Equality CType CType
    deriving (Eq, Data)

У меня есть несколько базовых типов (int и bool), тип стрелки и переменные типа. Затем я запускаю некоторые алгоритмы, которые генерируют ограничения равенства, которые представлены выше.

Моя цель состоит в том, что, имея список ограничений, я хочу найти наиболее общий унификатор.

Я наткнулся на эту библиотеку: http://hackage.haskell.org/package/compdata-0.1/docs/Data-Comp-Unification.html

Поскольку я новичок в Haskell, я не могу сразу понять, могу ли я применить его напрямую. Могу ли я использовать эту библиотеку или мне рекомендуется написать унификатор с нуля?

ОБНОВЛЕНИЕ

В настоящее время я вношу следующие изменения в код, но получаю ошибку объединения для уравнения

f=g

module SolveEq where
import Data.Data
import Data.Void
import Data.List as List
import Data.Map as Map
import Data.Set as Set
import Data.Maybe (fromJust)
import Data.Maybe (isJust)
import Control.Monad
import TypeCheck
import Data.Comp.Variables
import Data.Comp.Unification
import Data.Comp.Term
import Data.Comp.Derive
import Constraint
import Lang

data CTypeF a 
    = CVarF Int 
    | CArrF a a
    | CIntF
    | CBoolF
    deriving (Data, Functor, Foldable, Traversable, Show, Eq)

$(makeShowF ''CTypeF)


example :: String
example = showF (CIntF :: CTypeF String)

instance HasVars CTypeF Int where
isVar (CVarF x) = Just x
isVar (CArrF x y) = Nothing
isVar CIntF = Nothing
isVar CBoolF = Nothing

type CType_ = Term CTypeF

f :: CType_
f = Term (CVarF 0)

g :: CType_
g = Term CIntF


unravel :: CType_ -> CType
unravel a = 
    case unTerm a of 
        CVarF i -> CVar i
        CArrF a b -> CArr (unravel a) (unravel b)
        CIntF -> CInt
        CBoolF -> CBool

getUnify :: Either (UnifError CTypeF Int) (Subst CTypeF Int)
getUnify = unify [(f,g)]

main = case getUnify of
  Left (FailedOccursCheck v term)     -> putStrLn ("failed occurs check " ++ show v ++ ": " ++ (show $ unravel term))
  Left (HeadSymbolMismatch t1 t2)     -> putStrLn ("head symbol mismatch " ++ show (unravel t1)  ++ " =/= " ++ (show $ unravel t2))
  Left (UnifError str)     -> putStrLn str
  Right (subst :: Subst CTypeF Int) -> print (fmap unravel subst)

Проблема заключается в unify [(f,g)], который, как я ожидал, сопоставит 0 с Int. Но вроде не видит, что 0 это переменная. Возможно, что-то не так с моим isVar?

Примечание. Я использую compdata-0.12.


person Lana    schedule 16.06.2019    source источник
comment
Не относящееся к теме примечание: лично я не стал бы называть собственный тип Constraint из-за возможной путаницы с тип Constraint, встроенный в GHC   -  person Joseph Sible-Reinstate Monica    schedule 17.06.2019
comment
О, нет! ладно поменяю. Благодарю вас!   -  person Lana    schedule 17.06.2019
comment
Ага, вам нужно сделать отступ для определения isVar внутри вашего экземпляра HasVars. Это должно исправить это.   -  person user11228628    schedule 17.06.2019
comment
омг работает! наконец :) Большое вам спасибо за вашу помощь.   -  person Lana    schedule 17.06.2019


Ответы (1)


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

Вот что это значит: ваш тип CType является рекурсивным, поскольку он содержит другие экземпляры CType в одном из своих конструкторов (CArr). Переписать рекурсивный тип данных как сигнатуру означает создать тип данных, который принимает параметр типа, и использовать этот параметр типа везде, где вместо этого вы использовали бы рекурсию. Как это:

 data CTypeF a 
      = CVar Int 
      | CArr a a
      | CInt
      | CBool
      deriving (Eq, Data)

Теперь в вашей программе, где вы ранее использовали CTypes, вам нужно будет работать с чем-то более сложным, чем просто CTypeF. Ваш новый CType-эквивалент должен циклически применять CTypeF к самому себе. К счастью, Term это для вас, поэтому импортируйте Data.Comp.Term и замените все свои CType на Term CTypeF. (Конечно, вы всегда можете использовать псевдоним type CType = Term CTypeF, чтобы сэкономить время на наборе текста; просто имейте в виду, что Term CTypeF буквально не совпадает с исходным CType; вам нужно будет добавить несколько конструкторов Term в места, которые производят и потребляют CType.)

Наконец, чтобы использовать механизм унификации в compdata, вам понадобится экземпляр HasVars для CTypeF, который идентифицирует ваш конструктор CVar как переменную. Вам также потребуется сделать CTypeF и Functor, и Foldable, но если вы включите DeriveFunctor и DeriveFoldable функции языка, GHC может сделать это за вас — это строго механический процесс.


Запуская unify, вы должны убедиться, что делаете это в контексте, где монада ошибки m и тип переменной v однозначны. Есть много способов сделать это, но для примера предположим, что мы используем простейшую монаду ошибок Either e в качестве нашего m, и, конечно, вы хотите, чтобы v было Int. Итак, вы можете написать:

f = Term (CVar 2)
g = Term CInt

-- By matching against Left and Right, we're letting GHC know that unify
-- should return an Either; this disambiguates `m`
main = case unify [(f, g)] of
  Left _      -> print "did not unify"
  Right subst -> doMoreWork subst

-- The Int here disambiguates `v`
doMoreWork :: Subst CTypeF Int -> IO ()
doMoreWork subst = undefined -- fill in the blank!
person user11228628    schedule 16.06.2019
comment
Все работает прямо сейчас. Всего одна маленькая вещь. В настоящее время я хочу протестировать функцию унификации из этого пакета и объявляю f = (Term (CVarF 2)) и g = (Term CIntF) и t = (f,g). Подпись unify меня очень смущает. Мне интересно, можете ли вы показать простую функцию, которая просто вызывает unify на t? - person Lana; 17.06.2019
comment
Это должно быть просто unify [t]... что происходит, когда вы пытаетесь это сделать? - person user11228628; 17.06.2019
comment
Я получаю: • Неоднозначные переменные типа «v0», «m0», возникающие из-за использования «unify», предотвращают решение ограничения «(Control.Monad.Error.Class.MonadError (UnifError CTypeF v0) m0)». поэтому я предполагаю, что должен напечатать его, но подпись типа очень странная, поэтому я потерялся в том, что это должно быть - person Lana; 17.06.2019
comment
Ах хорошо! Это означает, что вы вызываете unify правильно с точки зрения его сигнатуры, но то, что вы делаете с результатом unify, слишком неограничено. Вам нужно предоставить GHC больше информации о том, что вы ожидаете от unify, так или иначе. Смотрите отредактированный ответ. - person user11228628; 17.06.2019
comment
По какой-то причине объединение [t] дает неверный ответ. Это приводит к несоответствию символов заголовка 2 =/= int. я реализовал все упомянутое выше. Должен ли я был реализовать что-то еще? Я бы ожидал, что решатель сопоставит 2 с int. - person Lana; 17.06.2019
comment
Я бы тоже. Можете ли вы обновить свой вопрос с помощью MCVE? Вы не можете пропустить какие-либо необходимые экземпляры, иначе ваша программа не скомпилируется; должно быть, что-то было написано неправильно. (Я подозреваю экземпляр HasVars, но мне нужен ваш код, чтобы быть уверенным.) - person user11228628; 17.06.2019
comment
О, и не забудьте указать, какие версии библиотек вы используете; похоже, что API compdata изменился между версией 0.1, которую вы связали, и самой последней версией 0.12. - person user11228628; 17.06.2019
comment
Да, безусловно. Обновление сейчас! - person Lana; 17.06.2019