在Haskell中为逻辑表达式生成真值表

第一部分是具有以下类型签名的评估函数:

evaluate :: Logic Expr -> [(Variable, Bool)] -> Bool

这将逻辑表达式和赋值对列表作为输入,并根据提供的布尔赋值返回表达式的值.赋值列表是一个不同的对列表,其中每对包含一个变量及其布尔赋值.也就是说,如果传递给函数表达式A∧B并且赋值A = 1且B = 0,则函数必须返回0(这来自Digital Logic Design,0对应于false,1对应于true).

这是我到目前为止所做的事情:

type Variable =  Char

data LogicExpr = V Variable
                 | Negation  LogicExpr
                 | Conjunction LogicExpr LogicExpr
                 | Disjunction  LogicExpr LogicExpr 
                 | Implication  LogicExpr LogicExpr 


evaluate :: LogicExpr -> [(Variable,Bool)] -> Bool

evaluate (V a) ((x1,x2):xs) | a==x1 = x2
                            | otherwise = (evaluate(V a)xs)

evaluate (Negation a) l | (evaluate a l)==True = False
                        | otherwise = True

evaluate (Conjunction a b) l = (evaluate a l)&&(evaluate b l)

evaluate (Disjunction a b) l = (evaluate a l)||(evaluate b l)

evaluate (Implication a b) l
    | (((evaluate b l)==False)&&((evaluate a l)==True)) = False
    | otherwise = True

下一部分是定义generateTruthTable,它是一个将逻辑表达式作为输入的函数,并以赋值对列表的形式返回表达式的真值表.也就是说,如果你传递给函数表达式E =A∧B,你的函数必须返回A = 0,B = 0,E = 0 | A = 0,B = 1,E = 0 | A = 1,B = 0,E = 0 | A = 1,B = 1,E = 1.

我不完全熟悉语法,所以我不知道如何返回列表.

标准库函数,代码重用.此外,您的括号用法和间距实际上是打击.

evaluate (V a) l =
    case lookup a l
      of Just x -> x
         Nothing -> error $ "Unbound variable: " ++ show a
-- same as
evaluate (V a) l = maybe (error $ "Unbound variable: " ++ show a) id $ lookup a l

evaluate (Negation a) l = not $ evaluate a l

evaluate (Implication a b) l = evaluate (Negation a `Disjunction` b) l

现在,你想要一个generateTruthTable？这很简单,只需获取布尔变量的所有可能状态,并将计算后的表达式添加到每个结尾.

generateTruthTable :: [Variable] -> LogicExpr -> [[(Variable, Bool)]]
generateTruthTable vs e = [l ++ [('E', evaluate e l)] | l <- allPossible vs]

如果只有你有一个函数来生成所有这些可能的状态.

allPossible :: [Variable] -> [[(Variable, Bool)]]

遵循我的功能直觉,这感觉它应该是一个catamorphism.毕竟,它确实需要查看列表中的所有内容,但返回不同结构的内容,并且可能会以简单的方式分解,因为这是一个介绍级别的CS类.(我不在乎课程编号是什么,这是介绍性的东西.)

allPossible = foldr step initial where
    step v ls = ???; initial = ???

现在,foldr :: (a -> b -> b) -> b -> [a] -> b所以前两个参数必须是step :: a -> b -> b和initial :: b.现在,allPossible :: [Variable] -> [[(Variable, Bool)]] = foldr step initial :: [a] -> b.嗯,这必须意味着a = Variable和b = [[(Variable, Bool)]].这是什么意思为step和initial？

    step :: Variable -> [[(Variable, Bool)]] -> [[(Variable, Bool)]]
    initial :: [[(Variable, Bool)]]

有趣.不知何故,需要step从变量状态列表中获取一种方法并向其添加单个变量,并且某些initial列表根本没有变量.

如果你的思想已经设法"点击"到函数式编程范例中,这应该是绰绰有余的.如果没有,那么无论你在这里收到什么指令,你在任务到期时都会在几个小时内搞砸.祝你好运,如果在任务到期后你仍然被困住,你应该问你的教授,或者在这里问一个非紧急的问题.

如果您对语言存在基本的可用性问题("语法是什么","运行时语义是什么","是否存在xxx的预先存在的功能"等):

Haskell 98语言和库是基本语言和库的可自由使用的规范定义.Haskell wiki上提供了更多链接.

有关98之后的语言扩展,请参阅GHC文档.

GHC,Hugs和其他现代Haskell实现还提供了比Haskell 98中指定的更丰富的标准库.层次库的完整文档也可在线获得.

Hoogλe是扩展Haskell标准库的专用搜索引擎. Hayoo!类似但也涵盖了HackageDB,这是一个远远超出标准发行版的Haskell库集合.

我希望您的课程提供类似的资源,但如果没有,上述所有内容都可以从Google搜索中轻松找到.

如果有适当的引用,任何值得拥有自己的盐的程序员都应该能够在几个小时内获取任何新语言的语法,并在几天内对运行时有一个合理的了解.当然,掌握一种新的范式可能需要很长时间,让学生达到相同的标准是不公平的,但这就是课程的目的.

关于Stack Overflow上更高级别问题的问题可能会引起更少的答案,但它们也会被提供更少的暴力:)家庭作业问题被归类为"我的工作对我来说!" 在大多数人的眼中.

扰流板

请不要作弊.但是,只是为了让您体验一下在Haskell中可以做多么棒的事情......

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
{-# LANGUAGE OverlappingInstances, PatternGuards #-}

module Expr (Ring(..), (=:>), Expr(..), vars, eval, evalAll) where

import Control.Monad.Error

infixl 5 =:>, :=>
infixl 6 +:, -:, :+, :-
infixl 7 *:, :*

class (Eq a) => Ring a where
    (+:) :: a -> a -> a; (-:) :: a -> a -> a; x -: y = x +: invert y
    (*:) :: a -> a -> a; invert :: a -> a; invert x = zero -: x
    zero :: a; one :: a
(=:>) :: (Ring a) => a -> a -> a
(=:>) = flip (-:)

instance (Num a) => Ring a where
    (+:) = (+); (-:) = (-); (*:) = (*)
    invert = negate; zero = 0; one = 1

instance Ring Bool where
    (+:) = (||); (*:) = (&&)
    invert = not; zero = False; one = True

data Expr a b
  = Expr a b :+ Expr a b | Expr a b :- Expr a b
  | Expr a b :* Expr a b | Expr a b :=> Expr a b
  | Invert (Expr a b) | Var a | Const b

paren :: ShowS -> ShowS
paren ss s = '(' : ss (')' : s)

instance (Show a, Show b) => Show (Expr a b) where
    showsPrec _ (Const c) = ('@':) . showsPrec 9 c
    showsPrec _ (Var v) = ('$':) . showsPrec 9 v
    showsPrec _ (Invert e) = ('!':) . showsPrec 9 e

    showsPrec n e@(a:=>b)
      | n > 5 = paren $ showsPrec 0 e
      | otherwise = showsPrec 7 a . ('=':) . ('>':) . showsPrec 5 b

    showsPrec n e@(a:*b)
      | n > 7 = paren $ showsPrec 0 e
      | otherwise = showsPrec 7 a . ('*':) . showsPrec 7 b

    showsPrec n e | n > 6 = paren $ showsPrec 0 e
    showsPrec _ (a:+b) = showsPrec 6 a . ('+':) . showsPrec 6 b
    showsPrec _ (a:-b) = showsPrec 6 a . ('-':) . showsPrec 6 b

vars :: (Eq a) => Expr a b -> [a]
vars (a:+b) = vars a ++ vars b
vars (a:-b) = vars a ++ vars b
vars (a:*b) = vars a ++ vars b
vars (a:=>b) = vars a ++ vars b
vars (Invert e) = vars e; vars (Var v) = [v]; vars _ = []

eval :: (Eq a, Show a, Ring b, Monad m) => [(a, b)] -> Expr a b -> m b
eval m (a:+b) = return (+:) `ap` eval m a `ap` eval m b
eval m (a:-b) = return (-:) `ap` eval m a `ap` eval m b
eval m (a:*b) = return (*:) `ap` eval m a `ap` eval m b
eval m (a:=>b) = return (=:>) `ap` eval m a `ap` eval m b
eval m (Invert e) = return invert `ap` eval m e
eval m (Var v)
  | Just c <- lookup v m = return c
  | otherwise = fail $ "Unbound variable: " ++ show v
eval _ (Const c) = return c

namedProduct :: [(a, [b])] -> [[(a, b)]]
namedProduct = foldr (\(v, cs) l -> concatMap (\c -> map ((v, c):) l) cs) [[]]

evalAll :: (Eq a, Show a, Ring b) => [b] -> a -> Expr a b -> [[(a, b)]]
evalAll range name e =
    [ vs ++ [(name, either error id $ eval vs e)]
    | vs <- namedProduct $ zip (vars e) (repeat range)
    ]

$ ghci
GHCi, version 6.10.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l Expr.hs
[1 of 1] Compiling Expr             ( Expr.hs, interpreted )
Ok, modules loaded: Expr.
*Expr> mapM_ print . evalAll [1..3] 'C' $ Var 'A' :* Var 'B'
Loading package mtl-1.1.0.2 ... linking ... done.
[('A',1),('B',1),('C',1)]
[('A',1),('B',2),('C',2)]
[('A',1),('B',3),('C',3)]
[('A',2),('B',1),('C',2)]
[('A',2),('B',2),('C',4)]
[('A',2),('B',3),('C',6)]
[('A',3),('B',1),('C',3)]
[('A',3),('B',2),('C',6)]
[('A',3),('B',3),('C',9)]
*Expr> let expr = Var 'A' :=> (Var 'B' :+ Var 'C') :* Var 'D'
*Expr> expr
$'A'=>($'B'+$'C')*$'D'
*Expr> mapM_ print $ evalAll [True, False] 'E' expr
[('A',True),('B',True),('C',True),('D',True),('E',True)]
[('A',True),('B',True),('C',True),('D',False),('E',False)]
[('A',True),('B',True),('C',False),('D',True),('E',True)]
[('A',True),('B',True),('C',False),('D',False),('E',False)]
[('A',True),('B',False),('C',True),('D',True),('E',True)]
[('A',True),('B',False),('C',True),('D',False),('E',False)]
[('A',True),('B',False),('C',False),('D',True),('E',False)]
[('A',True),('B',False),('C',False),('D',False),('E',False)]
[('A',False),('B',True),('C',True),('D',True),('E',True)]
[('A',False),('B',True),('C',True),('D',False),('E',True)]
[('A',False),('B',True),('C',False),('D',True),('E',True)]
[('A',False),('B',True),('C',False),('D',False),('E',True)]
[('A',False),('B',False),('C',True),('D',True),('E',True)]
[('A',False),('B',False),('C',True),('D',False),('E',True)]
[('A',False),('B',False),('C',False),('D',True),('E',True)]
[('A',False),('B',False),('C',False),('D',False),('E',True)]