haskell - 找出多个互斥的、可能不终止的 Bool 中的哪一个是 True

Question

(较长的问题，具体问题在底部)

我正在从事一个处理可数类型子集的业余项目，我想找出特定值属于哪个(可能无限)“集合”。

所以，我有许多互斥的、可能没有终止的 Bool 值(在我的例子中，是给定值的集合的特征值)，这样:

• 恰好其中一个将在有限时间内评估为True。
• 其余的将在有限时间内评估为False，否则它们的计算将不会终止。

我的目标是找出其中哪一个返回 True。

最适合我需要的类型签名是(我认为!)

decide :: [(Bool, b)] -> b

(但我对这里的建议持开放态度；我可以在稍后阶段进行 b 查找，比如说，如果 Int 工作得更好)。

道德上的 decide 应该等同于 snd 。 (\[x] -> x) 。 filter fst，如果所有计算都终止(如果 \[x] -> x 爆炸，那是我宁愿早点看到的程序员错误)。

这是所需行为的示例(我故意不在示例中使用 even 和 odd，因为我正在使用的集合的指标函数可能永远不会返回 False!):

type Natural = Integer
isNatural :: Integer -> Bool
isNatural = (>= 0)

evenOnNatural :: Natural -> Maybe Boolean
evenOnNatural x = decide [( x `elem` [0,2..],     Just True),
                          ( x `elem` [1,3..],     Just False),
                          ( not . isNatural $ x , Nothing)]

-- evenOnNatural 2 should be Just True
-- evenOnNatural 3 should be Just False
-- evenOnNatural (-1) should be Nothing (as it is outside the 'domain')

---

我拼凑了以下代码，它完成了我想要的这个示例(并且可以作为引用实现):

import Control.Monad(when)
import Control.Concurrent(forkIO,killThread)
import Control.Concurrent.MVar
import System.IO.Unsafe(unsafePerformIO) -- Oh dear!

decide :: [(Bool, a)] -> a
decide xs = unsafePerformIO $ do
    mv <- newEmptyMVar
    let actions = map (\(b,val) -> when b (putMVar mv val)) xs 
    threadIds <- mapM forkIO actions
    result <- takeMVar mv
    mapM_ killThread threadIds -- probably wrong, doesn't kill subthreads
    return result

我正在考虑使用 Data.Unamb的 unambs 和 assuming 组合子如下所示:

decide' :: [(Bool, a)] -> a
decide' = unambs . map (uncurry assuming)

肯定看起来好多了!我确定 Conal Elliott是一个比我更好的程序员:-)

但在此之前，我想回答以下问题:

• decide 是否已在 Haskell 平台中可用或可通过 Haskell 平台实现？
• unambs 的解决方案在互斥性方面是否具有我想要的行为？
• 还有其他我应该注意的重要问题吗？

[我意识到这个问题的形式不太具体，在 Programmers SE 或 Code Review SE 上可能会更好；我试图以明确(哈!)可回答的方式来表述它。 ]

Answer 1

我认为，您所描述的对应于此处的 Searchable 类:https://hackage.haskell.org/package/countable

这里描述了这个很酷的技巧:http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/

这里有一些关于进一步研究的幻灯片:http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf