dan*_*tin 9 algorithm search logic haskell
在没有实现嵌入式逻辑编程语言的情况下,是否有可扩展,有效的方法在Haskell中编写存在语句？通常,当我实现算法时,我想表达存在量化的一阶语句,如
?x.?y.x,y ? xs ? x ? y ? p x y
哪里?在列表上重载.如果我赶时间,我可能会写出看起来很像的明显代码
find p [] = False
find p (x:xs) = any (\y -> x /= y && (p x y || p y x)) xs || find p xs
要么
find p xs = or [ x /= y && (p x y || p y x) | x <- xs, y <- xs]
但是这种方法并不能很好地概括为返回多个arities的值或谓词或函数的查询.例如,即使是一个简单的陈述
?x.?y.x,y,z ? xs ? x ? y ? z ? f x y z = g x y z
需要编写另一个搜索程序.这意味着大量的样板代码.当然,类似Curry或Prolog实现缩小或解析引擎的语言允许程序员编写如下语句:
find(p,xs,z) = x ? xs & y ? xs & x =/= y & f x y =:= g x y =:= z
大量滥用表示法,它执行搜索并返回值.实施正式指定的算法时,这个问题经常出现,而且往往是由像功能组合解决了fmap,foldr和mapAccum,但主要是明确的递归.在Haskell中编写这样的代码是否有更通用,更高效,或者只是一般和富有表现力的方式？
有一个允许你转换的标准转换
?x ? xs : P
至
exists (\x -> P) xs
如果您需要出示证人,您可以使用find而不是exists.
在Haskell中进行这种抽象而不是逻辑语言的真正麻烦在于你必须将"Universe"集xs作为参数传递.我相信这就是你在标题中引用的"大惊小怪".
当然,如果您愿意,您可以将通用集(通过其搜索)填充到monad中.然后,您可以定义自己的版本exists或find使用monadic状态.为了提高效率,您可以尝试使用Control.Monad.Logic,但这可能会让您对Oleg的论文感到震惊.
无论如何,经典编码是用lambdas替换所有绑定结构,包括存在和通用量词,并继续进行适当的函数调用.我的经验是,这种编码甚至适用于具有大量结构的复杂嵌套查询,但它总是让人觉得笨重.
| 归档时间： |
|
| 查看次数： |
238 次 |
| 最近记录： |