2

我对 Polysemy 比较陌生，我正在努力思考如何NonDet正确使用。具体来说，假设我有这个计算

generate :: Member NonDet r => Sem r Int
generate = msum $ fmap pure [0..]

computation :: (Member NonDet r, Member (Final IO) r) => Sem r ()
computation = do
  n <- generate
  guard (n == 100)
  embedFinal $ print n

这是打印数字 100 的一种非常低效的方法，但它说明了我遇到的问题。现在，我只想在获得第一次成功的情况下运行此效果。也就是说，我想运行这个效果足够长的时间以“找到”数字 100 并打印它，然后我想停止。

我的第一次尝试

attempt1 :: IO ()
attempt1 = void . runFinal . runNonDet @[] $ computation

这个没有短路。它打印了 100，但随后永远挂起，再次寻找数字 100。那讲得通; 毕竟，我实际上并没有告诉它我只想要一个解决方案。所以让我们试试吧。

我的第二次尝试

runNonDetOnce :: Sem (NonDet ': r) a -> Sem r (Maybe a)
runNonDetOnce = fmap listToMaybe . runNonDet

attempt2 :: IO ()
attempt2 = void . runFinal . runNonDetOnce $ computation

我们在这里所做的只是丢弃列表头部以外的所有内容。可以理解的是，这并没有改变任何东西。Haskell 已经不在评估列表，因此丢弃未使用的值不会改变任何事情。就像attempt1，这个解决方案在打印 100 之后永远挂起。

我的第三次尝试

attempt3 :: IO ()
attempt3 = void . runFinal . runNonDetMaybe $ computation

所以我尝试使用runNonDetMaybe. 不幸的是，这个只是退出而不打印任何东西。弄清楚为什么要花一点时间，但我有一个理论。文件说

与 runNonDet 不同，如果第一个选项成功，使用 <|> 根本不会执行第二个分支。

所以它是贪婪的，并且在成功后不会回溯，基本上。因此，它像这样运行我的计算。

computation = do
  n <- generate        -- Ah yes, n = 0. Excellent!
  guard (n == 100)     -- Wait, 0 /= 100! Failure! We can't backtrack, so abort.
  embedFinal $ print n

非解决方案

在这个小例子中，我们可以稍微改变一下计算，就像这样

computation :: (Member NonDet r, Member (Final IO) r) => Sem r ()
computation = msum $ fmap (\n -> guard (n == 100) >> embedFinal (print n)) [0..]

因此，与其生成一个数字然后再检查它，我们只需移动generate到computation. 有了这个computation，attempt3成功了，因为我们可以在不回溯的情况下得到“正确”的答案。这在这个小例子中有效，但对于更大的代码库是不可行的。除非有人有一种很好的系统方法来避免回溯，否则我看不出有一种很好的方法可以将此解决方案推广到跨越大型程序中的多个文件的计算。

另一个非解决方案是使用IO.

computation :: (Member NonDet r, Member (Final IO) r) => Sem r ()
computation = do
  n <- generate
  guard (n == 100)
  embedFinal $ print n
  embedFinal $ exitSuccess

现在成功了，因为我们只是在成功后强行退出程序attempt1。attempt2但是，除了感觉非常草率之外，这也不能一概而论。我想在找到 100 后停止运行当前计算，而不是整个程序。

因此，总而言之，我希望使用 Polysemy 以某种方式运行上面第一个代码片段中给出的计算，这会导致它回溯（in NonDet）直到找到一个成功的值（在上面的示例中n = 100），然后停止运行影响并结束计算。我尝试深入研究runNonDetMaybeand co 的源代码，希望能够重现具有我想要的效果的类似于它的东西，但是我的多义词技能还没有达到理解那里发生的所有恶作剧Weaving的水平。decomp我希望这里比我更了解这个库的人可以为我指明正确的方向，NonDet以实现所需的效果。

4

1 回答 1

1

现在尝试1和尝试2成功了，因为我们只是在成功后强行退出程序。但是，除了感觉非常草率之外，这也不能一概而论。我想在找到 100 后停止运行当前计算，而不是整个程序。

而不是exitSuccess，一个密切相关的想法是抛出一个可以在解释器中捕获的异常。

于 2020-06-28T22:46:30.040 回答