list - Haskell 自引用列表终止

Question

编辑:见 this followup question 这简化了我在这里试图确定的问题，并要求对 GHC 修改提案提供意见。

所以我试图编写一个通用的广度优先搜索功能并提出以下内容:

bfs :: (a -> Bool) -> (a -> [a]) -> [a] -> Maybe a
bfs predf expandf xs = find predf bfsList
    where bfsList = xs ++ concatMap expandf bfsList

我认为这很优雅，但是在不存在的情况下它会永远阻塞。

在所有条款都扩展为 []之后, concatMap永远不会返回另一个项目，所以 concatMap正在阻塞等待来自自身的另一个项目？ Haskell 是否可以变得足够聪明以实现列表生成被阻止读取自引用并终止列表？

我能想到的最好的替代品并不那么优雅，因为我必须自己处理终止案例:

    where bfsList = concat.takeWhile (not.null) $ iterate (concatMap expandf) xs

对于具体示例，第一个搜索以成功终止，第二个搜索阻塞:

bfs (==3) (\x -> if x<1 then [] else [x/2, x/5]) [5, 3*2**8]
bfs (==3) (\x -> if x<1 then [] else [x/2, x/5]) [5, 2**8]

Answer 1

编辑添加注释来解释我的 bfs'解决方法如下。

您的问题的措辞方式(“Haskell 是否足够聪明”)，听起来您认为计算的正确值如下:

bfs (\x -> False) (\x -> []) []

鉴于您对 bfs 的原始定义应该是 Nothing ，而 Haskell 只是未能找到正确的答案。

但是，上述计算的正确值是底部。代入 bfs的定义(并简化 [] ++ 表达式)，上述计算等于:

find (\x -> False) bfsList
   where bfsList = concatMap (\x -> []) bfsList

正在评估 find需要确定是否 bfsList是否为空，因此必须强制弱头正常形式。这种强制要求评估 concatMap表达式，它也必须确定是否 bfsList是否为空，强制它为 WHNF。这个强制循环意味着 bfsList是底部，因此 find 也是如此.

Haskell 在检测循环和给出错误方面可能更聪明，但返回 [] 是不正确的。 .

最终，这与发生的事情相同:

foo = case foo of [] -> []

这也无限循环。 Haskell 的语义暗示这个 case构造必须强制 foo ，并强制 foo需要强制 foo ，所以结果是底部。确实，如果我们将此定义视为一个等式，那么将 foo = [] 代入会“满足”它，但这不是 Haskell 语义的工作方式，原因相同:

bar = bar

没有值(value) 1或 "awesome" ，即使这些值满足它作为“方程”。

因此，您的问题的答案是，不，无法更改此行为以便在不从根本上改变 Haskell 语义的情况下返回空列表。

此外，作为一个看起来很漂亮的替代方案——即使有明确的终止条件——也许可以考虑:

bfs' :: (a -> Bool) -> (a -> [a]) -> [a] -> Maybe a
bfs' predf expandf = look
  where look [] = Nothing
        look xs = find predf xs <|> look (concatMap expandf xs)

这使用 Alternative Maybe 的实例，这真的非常简单:

Just x  <|> ...     -- yields `Just x`
Nothing <|> Just y  -- yields `Just y`
Nothing <|> Nothing -- yields `Nothing` (doesn't happen above)

所以 look检查当前值集 xs与 find ，如果失败并返回 Nothing ，它递归地查看它们的扩展。

作为一个让终止条件看起来不那么明确的愚蠢例子，这里是它的双 monad(可能在隐式阅读器中)版本使用 listToMaybe作为终结者! (不推荐在实际代码中使用。)

bfs'' :: (a -> Bool) -> (a -> [a]) -> [a] -> Maybe a
bfs'' predf expandf = look
  where look = listToMaybe *>* find predf *|* (look . concatMap expandf)

        (*>*) = liftM2 (>>)
        (*|*) = liftM2 (<|>)
        infixl 1 *>*
        infixl 3 *|*

这是如何运作的？嗯，这是个笑话。作为提示， look 的定义是相同的:

  where look xs = listToMaybe xs >> 
                  (find predf xs <|> look (concatMap expandf xs))