Haskell Beginner без подсказки

Question

Мне потребовалось некоторое время, чтобы даже разобраться, что искал этот вопрос. Я должен вернуть только те предложения, которые дают общую оценку Истины. Наш пример: И p (Или q (Нет q)), и я знаю, что p должен быть True, а q может быть либо True, либо False. Для достижения нашей цели нам было дано несколько функций для начала.

type Variable = String 
type Valuation = [(Variable, Bool)] 

data Prop = Falsum   -- a contradiction, or 
      | Var Variable -- a variable, or 
      | Not Prop  -- a negation of a formula, or 
      | Or Prop Prop -- a disjunction of two formulae, or 
      | And Prop Prop -- a conjunction of two formulae, or 
      | Imp Prop Prop -- a conditional of two formulae. 
      deriving (Eq, Show) 

example = And p (Or q (Not q)) 

vars :: Prop -> [Variable] 
vars = nub . vars' 
    where 
     vars' Falsum = [] 
     vars' (Var v) = [v] 
     vars' (Not f) = vars' f 
     vars' (Or f g) = vars' f ++ vars' g 
     vars' (And f g) = vars' f ++ vars' g 
     vars' (Imp f g) = vars' f ++ vars' g 

eval :: Valuation -> Prop -> Bool 
eval val Falsum = False 
eval val (Var v) = case (lookup v val) of 
         Nothing -> error ("Unbound variable: " ++ v) 
         Just t -> t 
eval val (Not f) = not (eval val f) 
eval val (Or f g) = (eval val f) || (eval val g) 
eval val (And f g) = (eval val f) && (eval val g) 
eval val (Imp f g) = eval val (Or (Not f) g) 

valuations :: [Variable] -> [Valuation] 
valuations []  = [[]] 
valuations (v:vs) = map ((v,True):) ds ++ map ((v,False):) ds 
    where ds = valuations vs 

теперь я должен написать функцию модели, и я работал, что typeline должен быть

models :: Prop -> [Valuations] 

, как мой пример должен вернуть список Valuations, которые оценивают Истину, которая является: Пример модели == [[("p", True) ("q", True)], [("p", True) ("q", False)]]

Я знаю, что vars возвращает список переменных без дубликатов, в этом случае ["p", "q"], и что передача результата из варов в оценки дает список всех возможных результаты применения True и False для «p» и «q». Пока я могу получить только первый вывод этого списка для оценки с помощью функции evals. Вот мой код:

models :: Prop -> Bool 
models form = eval v form where (v:vs) = valuations (vars form) 

Я попытался изменить код, чтобы оценить остальные против, но я получаю сообщение об ошибке:

Couldn't match expected type '[Bool]' with actual type 'Bool' 

Вот мой измененный код:

models :: Prop -> [Bool] 
models form = eval v form : eval vs form where (v:vs) = valuations (vars form) 

В идеале я считаю, что хочу отбросить результаты eval, а не сохранять их в списке и возвращать только те оценки, которые оцениваются True. Я просто зациклился на том, как рекурсивно оценить остальную часть vs.

Я считаю, что однажды я могу оценить все элементы в моем списке, используя функцию evals, тогда я могу просто добавить те, которые оценивают True, используя некоторую форму равенства назначение, например:

where finalList == True = 

Увы, это даже не кажется близким к правильному.

Любая помощь с моей логикой будет полезна. О, и объяснение того, как я могу рекурсивно оценить остальную часть списка, будет оценено по достоинству.

Answer 1

Я собираюсь предположить, что вы хотите models :: Prop -> [Valuation], как вы начали писать. Модели возвратятся каждые Valuation, которые удовлетворяют этому предложению. Начиная с чего-то близкого к тому, что у вас было

models form = valuations (vars form) 

достал нас на полпути; он имеет правильный тип, Prop -> [Valuation]. Это просто перечисляет каждые Valuation для переменных в form. Нам бы хотелось иметь только те результаты, которые удовлетворяют предложению. Они могут быть определены вашей функцией eval.

models :: Prop -> [Valuation] 
models form = filter satisfies (valuations (vars form)) 
    where satisfies val = eval val form 

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

example = And (Var "p") (Or (Var "q") (Not (Var "q"))) 

main = do 
    print $ models Falsum 
    print $ models example 
    print $ models $ And (Var "p") (Not (Var "p")) 
    print $ models $ Or (Var "p") (Not (Var "p")) 

Это выводит

[] 
[[("p",True),("q",True)],[("p",True),("q",False)]] 
[] 
[[("p",True)],[("p",False)]] 

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

satisfiable :: Prop -> Bool 

Мы можем легко записать это в терминах models

satisfiable :: Prop -> Bool 
satisfiable = not . null . models 

Для тех же четырех примеров

main = do 
    print $ satisfiable Falsum 
    print $ satisfiable example 
    print $ satisfiable $ And (Var "p") (Not (Var "p")) 
    print $ satisfiable $ Or (Var "p") (Not (Var "p")) 

Это выводит

False 
True 
False 
True