7

我正在尝试为给定的布尔表达式生成一个真值表。我可以通过创建一个新的数据类型 BoolExpr 来做到这一点，但我想用一个匿名函数来做到这一点。它应该像这样工作：

> tTable (\x y -> not (x || y))
output:
F F | T
F T | F
T F | F
T T | F

我的做法：

tbl p = [(uncurry p) tuple | tuple <- allval]
        where allval=[(x,y) | x <- [False,True], y <- [False,True]]

这有效，但仅适用于 2 个参数。我想为任意数量的参数做这件事。所以我想我会做一个从列表中获取参数的函数：

argsFromList f []     = f
argsFromList f (x:xs) = argsFromList (f x) xs

这不起作用：

 Occurs check: cannot construct the infinite type: t = t1 -> t
   Expected type: t -> [t1] -> t1 -> t
   Inferred type: (t1 -> t) -> [t1] -> t1 -> t
 In the expression: argsFromList (f x) xs

我不明白这里有什么问题。如果有人能指出我正确的方向或发布链接，我将不胜感激。

4

3 回答 3

13

如果您想为具有任意数量参数的布尔函数构建一个真值表，您正在创建一个必须适用于多种类型的函数，因此您必须使用类型类：

{-# LANGUAGE FlexibleInstances #-}

class TruthTable a where
  truthTable :: a -> [([Bool], Bool)]

instance TruthTable Bool where
  truthTable b = [([], b)]

instance TruthTable a => TruthTable (Bool -> a) where
  truthTable f = [ (True  : inps, out) | (inps, out) <- truthTable (f True)] ++ 
                 [ (False : inps, out) | (inps, out) <- truthTable (f False)]

例如：

*Main> mapM_ print $ truthTable (&&)
([True,True],True)
([True,False],False)
([False,True],False)
([False,False],False)
于 2011-12-12T17:59:13.680 回答
4

这里的问题是您正尝试使用不同类型的递归步骤递归调用函数。考虑定义：

argsFromList f []     = f
argsFromList f (x:xs) = argsFromList (f x) xs

让我们尝试自己推断类型。我们可以立即看到，第一个参数f应该是至少一个参数的函数，第二个参数(x:xs)是一个列表，并且列表元素应该与第一个参数的类型相同f。在第一种情况下，参数f被返回，因此最终的返回类型必须与第一个参数相同。所以我们从这个开始：

argsFromList :: (a -> ?) -> [a] -> (a -> ?)

要找到未知类型?，我们可以查看第二种情况，它由递归调用组成。参数xs是相同的列表类型，并且参数(f x)具有 type ?。由于它被用作递归调用中的第一个参数，它具有 type (a -> ?)，我们现在可以得出结论，?它与(a -> ?)which 的类型相同，因此与 which 的类型相同，(a -> (a -> ?))因此与 which is 的类型相同(a -> (a -> (a -> ?)))……哎呀。

当然，那将是“无限类型”。

如果您想对使用可变数量的单一类型参数的函数执行此操作，您可能希望使用接受值列表而不是单个参数的函数。否则，您将不得不单独编写每个版本，或者使用一些涉及高级语言功能的神秘技巧，在这样的简单案例中，这两种方法都没有吸引力。

于 2011-12-12T17:26:40.503 回答
2

你所要求的根本不是微不足道的。Haskell 无法轻松处理应用具有可变数量参数的函数的函数。例如，来自不同数量的参数（, , , ...）的zip 函数有不同的变体。Data.List同样，在里面有, , , ...zipzip3zip4Control.MonadliftMliftM2liftM3

基本上，您可以分配给具有未知数量参数的函数的最通用类型是a -> b; 一位真值函数是Bool -> Bool(a = Bool, b = Bool)，两位真值函数是Bool -> (Bool -> Bool)(a = Bool, b = Bool -> Bool)，三位真值函数是 (a Bool -> (Bool -> (Bool -> Bool))= , Boolb = Bool -> (Bool -> Bool))，依此类推。但是没有简单的方法可以查看传入的函数以了解初始箭头右侧的类型是什么。

一种可行的解决方案涉及使用类型类为每个参数函数类型定义真值表生成器函数的单独实例。Sjoerd Visscher 在此线程中的回答是通过使用递归实例定义（注意递归TruthTable a => TruthTable (Bool -> a)声明）对所有函数大小执行此操作。可能还有其他解决方案可以使用Applicative类型类构建。

于 2011-12-12T19:43:08.683 回答