1

下面是我在 Curry 中的第一个程序。它打印达到所需解决方案所需的步骤序列（穿过关闭的门）。

Evaluating expression: main
Done
(Just [Open,Walk,Close])

我怎样才能让它在寻找时终止Impossible？我正在使用 Kics2 0.3.1。

import List
import AllSolutions
import IO
import ReadShowTerm
import Constraint

data State = Opened | Closed | Outside | Done | Impossible
data Action = Open | Walk | Close

e Open Closed = Opened
e Walk Opened = Outside
e Close Outside = Done

solution target | foldl (flip e) Closed actions =:= target & length actions <: 4  = actions
   where actions free

main = do
  target <- getContents
  getOneValue (solution $ readTerm target) >>= print
4

1 回答 1

0

在 的情况下Done，您使用 修剪搜索空间getOneValue。也就是说，当找到第一个结果时，函数不会为自由变量生成更多的可能性actions。但是，当没有解决方案时，例如 的情况Impossible，使用getOneValue无法修剪搜索空间，因为它会继续寻找第一个解决方案。实际上，如果您搜索所有解决方案而不是仅搜索第一个解决方案，那么即使另一个调用在找到解决方案后也不会终止。

为了获得终止版本，您可以尝试以下定义solution.

solution target | foldl (flip e) Closed (take 4 actions) =:= target = actions
   where actions free

这样搜索空间实际上被修剪了，因为take它只评估列表的前四个 cons 构造函数。相反，length导致列表的所有构造函数的求值计算长度。因为它评估整个列表，所以自由变量actions生成越来越多的列表，因为自由变量的非确定性可能性的生成是由对自由变量的评估驱动的。

限制 Curry 程序的搜索空间可能非常困难，因为您必须对评估进行推理。例如，如果您使用 peano 数字而不是原始整数，您也会得到一个终止程序。Peano更准确地说，您可以使用数字定义以下函数。

data Peano = Zero | Succ Peano

fourP :: Peano
fourP = Succ (Succ (Succ (Succ Zero)))

lengthP :: [a] -> Peano
lengthP [] = Zero
lengthP (_:xs) = Succ (lengthP xs)

lessP :: Peano -> Peano -> Success
lessP Zero     (Succ _) = success
lessP (Succ x) (Succ y) = lessP x y

通过这些功能，您可以获得如下的终止版本。

solution target | lessP (lengthP actions) fourP & foldl (flip e) Closed actions =:= target = actions
   where actions free

但是，请注意，您必须首先检查列表的长度，因为&在评估方面存在左偏。也就是说，如果它的第一个参数失败，它不会评估它的第二个参数。如果我们切换 的参数&，条件将首先检查动作列表是否产生状态Closed，然后检查其长度。也就是说，我们不再使用长度来修剪搜索空间。

于 2014-07-06T18:19:14.053 回答