Haskell：有条件地打破循环

Question

I want to break a loop in a situation like this:

import Data.Maybe (fromJust, isJust, Maybe(Just))

tryCombination :: Int -> Int -> Maybe String
tryCombination x y 
               | x * y == 20 = Just "Okay"
               | otherwise = Nothing

result :: [String]
result = map (fromJust) $ 
    filter (isJust) [tryCombination x y | x <- [1..5], y <- [1..5]]

main = putStrLn $ unlines $result

假设"tryCombination"像这个例子一样更加复杂。它消耗了大量的CPU资源，而且不是评估25种可能性，而是26^3种可能性。

当"tryCombination"找到给定组合的解决方案时，它返回"Just"，否则返回"Nothing"。我如何在第一个发现的解决方案上立即打破循环？

- Hennes

---

顺便说一句，map fromJust . filter isJust 是来自 Data.Maybe 的 catMaybes。 - Reid Barton

Answer 1

简单解决方案：find和join

看起来你正在寻找Data.List.find。 find有类型签名

find :: (a -> Bool) -> [a] -> Maybe a

所以你可以这样做

result :: Maybe (Maybe String)
result = find isJust [tryCombination x y | x <- [1..5], y <- [1..5]]

或者，如果你不想要一个 Maybe (Maybe String)（为什么呢？），你可以使用 Control.Monad.join 将它们折叠在一起，其签名为

join :: Maybe (Maybe a) -> Maybe a

为了让你拥有

result :: Maybe String
result = join $ find isJust [tryCombination x y | x <- [1..5], y <- [1..5]]

---

更高级的解决方案：asum

如果你想要一个略微更高级的解决方案，可以使用Data.Foldable.asum，它具有以下签名：

asum :: [Maybe a] -> Maybe a

它的作用是从许多选项中选择第一个Just值。它通过使用Maybe的Alternative实例来实现。 Maybe的Alternative实例的工作方式如下：（导入Control.Applicative以访问<|>运算符）

λ> Nothing <|> Nothing
Nothing
λ> Nothing <|> Just "world"
Just "world"
λ> Just "hello" <|> Just "world"
Just "hello"

换句话说，它从两个备选项中选择第一个Just值。想象一下在列表的每个元素之间放置<|>，这样就可以理解它的作用。

[Nothing, Nothing, Just "okay", Nothing, Nothing, Nothing, Just "okay"]

被转换为

Nothing <|> Nothing <|> Just "okay" <|> Nothing <|> Nothing <|> Nothing <|> Just "okay"

这正是asum函数所做的事情！由于<|>是短路运算，它只会计算到第一个Just值。因此，你的函数将变得非常简单。

result :: Maybe String
result = asum [tryCombination x y | x <- [1..5], y <- [1..5]]

为什么你想要这种更高级的解决方案呢？不仅代码更短；一旦你知道习惯用语（即当你熟悉 Alternative 和 asum 时），通过阅读代码的前几个字符就能更清楚地了解该函数的作用。

- kqr

---

非常感谢。运行得很好！ - Hennes

@Hennes 添加了第二部分，提供了另一种解决方案（嘿，明白双关语吗？）。如果这个解决方案超出了你的能力范围，也许你不想立即使用它，但它可能是一个有趣（或折磨人的）阅读体验。 :) - kqr

Answer 2

要回答你的问题，find函数是你需要的。在获得 Maybe (Maybe String) 后，你可以使用 join 将其转换为 Maybe String。

虽然 find 更加优雅、易读且仅执行所需操作，但是我并不确定你在问题中提供的代码效率低下。懒惰求值可能会处理并计算所需的内容（仍可能消耗额外的内存）。如果你有兴趣，请尝试进行基准测试。

- zudov

Answer 3

懒惰求值在这种情况下非常有用。通过调用unlines，您正在请求“循环”的所有输出¹，因此显然它无法在第一次成功的tryCombination后停止。但是，如果您只需要一个匹配项，请使用Data.Maybe中的listToMaybe函数；如果根本没有匹配项，则它将将您的列表转换为Nothing，否则将返回第一个找到的匹配项。

懒惰意味着列表中的结果仅在需要时进行评估；如果您从未要求列表的任何其他元素，则生成它们所需的计算（甚至查看列表中是否还有更多元素）将永远不会运行！

这意味着您通常不必像在命令式语言中那样"打破循环"。您可以将完整的“循环”编写为列表生成器，而使用者可以独立地决定他们需要多少内容。这个想法的极端案例是Haskell可以轻松生成甚至过滤无限列表；它只会运行足够的生成代码来产生您稍后检查的恰好数量的元素。

---

¹ 实际上，即使unlines也会产生惰性字符串，因此如果您只读取结果连接字符串的第一行，则仍然可以提前“中断循环”！但是在此处您打印了整个字符串。

- Ben

---

这是最基础和最重要的答案，楼主应该从这里开始。 - Reid Barton

Answer 4

你所寻找的评估策略正是MonadPlus 的Maybe实例的目的。特别地，有一个函数msum，其类型在此情况下专门化为：

msum :: [Maybe a] -> Maybe a

直观地说，这个版本的msum接受一个可能失败的计算列表，依次执行它们，直到第一个计算成功并返回相应的结果。因此，result将变为

result :: Maybe String
result = msum [tryCombination x y | x <- [1..5], y <- [1..5]]

此外，通过将Maybe泛化为MonadPlus的任何实例，您可以使代码在某种程度上不关注具体的求值策略。

tryCombination :: MonadPlus m => Int -> Int -> m (Int,Int)
-- For the sake of illustration I changed to a more verbose result than "Okay".
tryCombination x y 
    | x * y == 20 = return (x,y) -- `return` specializes to `Just`.
    | otherwise   = mzero        -- `mzero` specializes to `Nothing`.

result :: MonadPlus m => m (Int,Int)
result = msum [tryCombination x y | x <- [1..5], y <- [1..5]]

为了获得所需的行为，请运行以下内容：

*Main> result :: Maybe (Int,Int)
Just (4,5)

然而，如果您决定不仅需要第一个组合，而是所有组合，请使用MonadPlus的[]实例：

*Main> result :: [(Int,Int)]
[(4,5),(5,4)]

我希望这可以在概念层面上提供更多帮助，而不仅仅是提供解决方案。

PS：我刚刚注意到，MonadPlus和msum在这个目的上确实有点太严格了，Alternative和asum就足够了。

- Martin Huschenbett