在使用具有保证值的find时，正确的解决方案是什么

Question

在Haskell中，find被设计为作为Maybe求值，因为当扫描列表中与谓词匹配的元素时，它可能会失败。但是，请考虑以下内容：

factorize n | isPrime n = [n]
| otherwise = m : factorize (n `div` m)
where m = find ((==0) . (n `mod`)) [2..]

这里的find在任何情况下都会清楚地找到一个值，假设我们只命中大于2的整数。如果一个数字不是素数，那么它在无限列表[2..]中的某个地方有一个因子。但当然，Haskell不知道这一点，他仍然会抱怨使用了"也许"。这里的解决方案是什么？

1. 使用带有一些伪默认值的fromMaybe来提取内部值。永远不会使用默认值
2. 使用类似head . dropWhile的东西作为一种"不安全的发现">
3. 将Maybes一直向上冒泡，并将因子作为Maybes列表返回
4. 告诉哈斯克尔"看，数学证明了，这是安全的，相信我。">

1和2很臭，3很麻烦，给不应该存在的函数添加了故障状态，我不知道4是否存在。这里的最佳解决方案是什么？

编辑：上面的选项列表是不完整的，没有提到fromJust，它接受一个Just并返回其中的值，并在给定Nothing时抛出错误。我想这显然是我问题的简短答案，直到我读到这里的答案和评论，我才意识到它的存在。然而，在下面的回答中，关于安全性和故障状态，仍然有一些好的观点。

Answer 1

使用fromMaybe(或fromJust((选项1(是"；告诉哈斯克尔"相信我"；(备选方案4(。

什么是臭的，正是要说"；相信我"；，因为程序员不值得信任。强类型语言的用户更喜欢在类型系统中编码不变量，这样它们就可以自动强制执行。然而，算术是编程中一个臭名昭著的方面，主流类型的系统还没有准备好处理它，所以你必须在无法访问的情况下抛出错误。依赖/精化类型(参见Liquid Haskell(是一种技术，它可以让您对语言的类型系统中的算术进行推理。

Answer 2

解决方案1可以工作，但它是唯一的。

解决方案2/4将使用fromJust或模式匹配：

factorize n | isPrime n = [n]
| otherwise = m : factorize (n div m)
where m = fromJust $ find ((==0) . (n `mod`)) [2..] -- trust me, if a number is not prime, then it has a factor somewhere

factorize n | isPrime n = [n]
| otherwise = m : factorize (n div m)
where (Just m) = find ((==0) . (n `mod`)) [2..] -- trust me, if a number is not prime, then it has a factor somewhere

评论有点重要，要向读者指出这是安全的，永远不会引起异常。但是，没有办法告诉Haskell，如果发生Nothing，它仍然会生成抛出异常的代码。

你需要自己证明它的正确性。你可能会注意到它实际上是错误的——试试factorize 1！

这里的最佳解决方案是什么？

首先不要重复工作。isPrime还将尝试查找一个因子，如果找到了，则返回False，如果没有找到，则返回True。在isPrime n返回False的情况下，不要试图再次查找因子，而是使用刚才搜索的因子！

-- TODO: prove that the returned factor is actually prime
-- TODO: optimise by using [2..(floor $ sqrt $ fromIntegral n)]
findPrimeFactor :: Integer -> Maybe Integer
findPrimeFactor n = find ((==0) . (n `mod`)) [2..n-1]
factorize 1 = []
factorize n = case findPrimeFactor n of
Nothing -> [n]
Just m  -> m : factorize (n div m)
isPrime 1 = False
isPrime n = case findPrimeFactor n of
Nothing -> True
Just _  -> False

或者

-- TODO: prove that the returned number is actually prime
findPrimeFactor :: Integer -> Maybe Integer
findPrimeFactor n = find ((==0) . (n `mod`)) [2..n]
--                                               ^ note the difference
factorize n = case findPrimeFactor n of
Nothing -> []
Just m  -> m : factorize (n div m)
isPrime n = (Just n) == findPrimeFactor n