0

---- 更新 2 ----

最後に、彼は私にそう言ったExists...</p>

皆さん、ありがとうございました。

- - アップデート - -

わかりました、私たちはそれを呼びますForsome

ex3: forsome x0::[False,True]. forsome x1::[0,1,2]. (x0 || (0 < x1))

（「forallとは何か」を追加したと言った人）：

the constructor says "forall x in blah" but it really means "for some x in blah". 

the formula is satisfied for some assignment of variables so it is satisfiable.

どうすればいいですか？ありがとう

- - オリジナル - -

式ex3があるとします

ex3: forall x0::[False,True]. forall x1::[0,1,2]. (x0 || (0 < x1)).

False最初は、 ex3は だと思います。なぜならx0 = False、x1 = 0式が (False || (0 < 0))しかし、ex3 はTrue、

"satisfiable ex3 is true because there is at least one combination from sets x0 and x1 which returns true. So as long as there is 1 valid solution in Forall, it is true."

それが正しいと仮定してください…</p>

同じレベルの組み合わせのグループを確認する必要があると思いますが、その方法がわかりません。「同じグループか」を判断するのは難しそうです。

これが私のコードです：

ファイル: Formula.hs

{-# LANGUAGE GADTs #-}

module Formula where

-- Datatype of formulas
-- --------------------

data Formula ts where
  Body   :: Term Bool                     -> Formula ()
  Forall :: Show a 
         => [a] -> (Term a -> Formula as) -> Formula (a, as)

data Term t where
  Con     :: t         -> Term t
  And     :: Term Bool -> Term Bool -> Term Bool
  Or      :: Term Bool -> Term Bool -> Term Bool
  Smaller :: Term Int  -> Term Int  -> Term Bool
  Plus    :: Term Int  -> Term Int  -> Term Int
  Name    :: String    -> Term t    -- to facilitate pretty printing

-- Pretty printing formulas
-- ------------------------

instance Show t => Show (Term t) where
  show (Con v)       = show v
  show (And p q)     = "(" ++ show p ++ " && " ++ show q ++ ")"
  show (Or p q)      = "(" ++ show p ++ " || " ++ show q ++ ")"
  show (Smaller n m) = "(" ++ show n ++ " < "  ++ show m ++ ")"
  show (Plus n m)    = "(" ++ show n ++ " + "  ++ show m ++ ")"
  show (Name name)   = name

instance Show (Formula ts) where
  show = show' ['x' : show i | i <- [0..]]
    where
      show' :: [String] -> Formula ts' -> String
      show' ns     (Body body)   = show body
      show' (n:ns) (Forall vs p) = "forall " ++ n ++ "::" ++ show vs ++ ". " ++ show' ns (p (Name n))


-- Example formulas
-- ----------------

ex1 :: Formula ()
ex1 = Body (Con True)

ex2 :: Formula (Int, ())
ex2 = Forall [1..10] $ \n ->
        Body $ n `Smaller` (n `Plus` Con 1)

ex3 :: Formula (Bool, (Int, ()))
ex3 = Forall [False, True] $ \p -> 
      Forall [0..2] $ \n -> 
        Body $ p `Or` (Con 0 `Smaller` n)

wrongFormula :: Formula (Int, ())
wrongFormula = Forall [0..4] $ \n ->
                 Body $ n `Smaller` (Con 0)

ファイル: Solver.hs

{-# LANGUAGE GADTs #-}

module Solver where

import Formula


-- Evaluating terms
-- ----------------

eval :: Term t -> t
eval (Con     v)   = v
eval (And     p q) = eval p && eval q
eval (Or      p q) = eval p || eval q
eval (Smaller n m) = eval n <  eval m
eval (Plus    n m) = eval n +  eval m
eval (Name    _)   = error "eval: Name"


-- Checking formulas
-- -----------------

satisfiable :: Formula ts -> Bool
satisfiable (Body body)    = eval body
-- FIXME wrong implement
--satisfiable (Forall xs f) = helper f xs
--  where helper :: (Term a -> Formula t) -> [a] -> Bool
--        helper fn (a:as) = (satisfiable $ (fn . Con) a) && (helper fn as)
--        helper _ []     = True

任意の提案をいただければ幸いです。

4

1 に答える 1

1

Existsこれはではなくを表すというダニエルの意見に同意しForallますが、そのように解釈したい場合は、 と に変更するだけ&&です。||TrueFalse

または、さらに良いことに、Prelude 関数を使用します。

all :: (a -> Bool) -> [a] -> Bool  -- is predicate true for all elements?
any :: (a -> Bool) -> [a] -> Bool  -- is predicate true for any element?

既存の実装を次のように書くことができます

satisfiable (Forall xs f) = all (satisfiable . f . Con) xs

変更するには、 を に変更するだけallですany。

于 2012-04-23T08:50:41.180 に答える