Haskell 函数构造

Question

我正在学习 Haskell，并遇到了一个奇怪的问题。我有一个很长的表达式，我需要将其分成小表达式并记录它们。我已经设法解决了该部分，但我不明白为什么我不能将 (Const Bool) 的详细信息添加到所有详细信息中。

module MonadicInterpreterLog where

import Test.HUnit (runTestTT,Test(TestLabel,TestList),(~?=))

import Control.Monad 
import Control.Applicative hiding (Const)

-- Simple Boolean expressions
data Expr = Const Bool | And Expr Expr | Or Expr Expr
  deriving (Eq, Show, Read)

sample1 = And (Const True) (Or (Const False) (Const True))
sample2 = And (Or (Const False) (Const True)) (And (Const False) (Const True))

eval' :: Expr -> [Expr] -> (Bool, [Expr])
eval' (Const b) es = (b, Const b : es)
eval' (And e1 e2) es = (checkValue e1 && checkValue e2, And e1 e2 : e1 : e2 : es)
eval' (Or e1 e2) es = (checkValue e1 || checkValue e2, Or e1 e2 : e1 : e2 : es)

checkValue :: Expr -> Bool
checkValue (Const b) = b
checkValue (And e1 e2) = checkValue e1 && checkValue e2
checkValue (Or e1 e2) = checkValue e1 || checkValue e2



main :: IO ()
main = do
    testresults <- runTestTT tests
    print testresults

testlog1, testlog2 :: [Expr]
testlog1 = [(And (Const True) (Or (Const False) (Const True))),
        (Const True),
        (Or (Const False) (Const True)),
        (Const False),
        (Const True)]
testlog2 = [(And (Or (Const False) (Const True)) (And (Const False) (Const True))),
             (Or (Const False) (Const True)),
             (Const False),
             (Const True),
             (And (Const False) (Const True)),
             (Const False),
             (Const True)]

-- | List of tests for 'parseScore'.
tests :: Test
tests = TestLabel "MonadicInterpreterLog" (TestList [
    eval' sample1 [] ~?= (True,testlog1),
    eval' sample2 [] ~?= (False,testlog2)
    ])

我收到的错误消息:

MonadicInterpreterLog.hs:96 
expected: (True,[And (Const True) (Or (Const False) (Const True)),Const True,Or (Const False) (Const True),Const False,Const True])
but got: (True,[And (Const True) (Or (Const False) (Const True)),Const True,Or (Const False) (Const True)]) 

正如您所见，(Const Bool) 部分丢失了。我做错了什么？预先感谢您

Answer 1

虽然 checkValue 是递归的，但 eval' 却不是。我们可以用一个更小的例子来展示这一点:

true   = Const True
small1 = And true $ And true $ And true true

ghci> eval' small1
(True,[
 And (Const True) (And (Const True) (And (Const True) (Const True))), -- level 1
 Const True, And (Const True) (And (Const True) (Const True))         -- level 2
  -- other levels missing
 ])

您必须在 es1 和 es2 上递归应用 eval'。更好的是，让 eval 实际完全评估表达式:

eval :: Expr -> (Bool, [Expr])
eval expr = case expr of
    Const b   -> (b, [expr])
    And e1 e2 -> evalWith (&&) e1 e2
    Or  e1 e2 -> evalWith (||) e1 e2 
  where
    evalWith op e1 e2 = 
      let (b1, es1') = eval e1
          (b2, es2') = eval e2
      in (b1 `op` b2, expr : (es1' ++ es2'))