在Haskell中找到最大的n，使n！<k，使用foldl和一个无穷级数

Question

这似乎很简单，在标题中说明，但我有困难，编码它。我在找最大的n，这样n！

以下是我尝试过的：

func1 = foldl (*) 1 [1..] . takeWhile (\x -> x < (read "1e100" :: Scientific ))

func2 = (\x -> foldl (*) 1 [1..x] . takeWhile (x < (read "1e100" :: Scientific )))

func3 = do
        forM_ [1..] $ \x -> do
            let y = foldl (*) 1 [1..x]
            when y >= (read "1e100" :: Scientific ) $
                putStrLn x
                return ()

func4 k = let nfac = foldl (*) 1 [1..n]
              where nfac > k
-- func4 (read "1e100" :: Scientific )

我正在使用Data.Scientific库，因为k通常是很大的。

用什么惯用的方式正确地表达这句话呢？

Answer 1

简短回答：将程序划分为每个函数，每个函数执行一个专用任务。

我们可以首先定义一个函数来计算阶乘：

fact :: (Num a, Enum a) => a -> a
fact x = foldl (*) 1 [1..x]

现在我们可以生成一个2元组的列表，其中第一项是i，第二项是i!。

facts :: (Num a, Enum a) => [(a, a)]
facts = map (\i -> (i, fact i)) [1..]

现在，我们可以使用一个takeWhile来过滤这个列表，只返回第二个条目(因此i! )小于n的元组。

factsless :: (Num a, Enum a) => a -> [(a, a)]
factsless n = takeWhile (\(_, fi) -> fi < n) facts

现在我们可以使用last来获取这个列表的最后一个元组，然后使用fst获得相应的i。

solution :: (Num a, Enum a) => a -> a
solution n = fst (last (factsless n))

考虑到n很大，只有Integer才能表示这个数字。因此，为Integer使用a可能更安全，因为否则就有可能使小于check的操作永远不会失败，因此会发生溢出。

例如：

Prelude> solution 2
1
Prelude> solution 3
2
Prelude> solution 4
2
Prelude> solution 5
2
Prelude> solution 6
2
Prelude> solution 7
3
Prelude> solution 10
3
Prelude> solution 100
4
Prelude> solution 10000
7 
Prelude> solution (10^100)
69 

由于阶乘是积分，所以最好避免浮点数，通常整数会更精确、更紧凑、更有效。

Optimizations

我们可以通过生成无限列表(例如使用scanl )来提高计算阶乘的性能。

facts :: (Num a, Enum a, Num b, Enum b) => [(a, b)]
facts = zip [1..] (scanl (*) 1 [2..])

其他优化是可能的，但我将此作为练习。

Answer 2

用扫描代替折叠，并将其结果通过takeWhile ...。然后对其进行索引并获取一个last！

但是，首先解开read，将其转化为一个普通的参数值。对于您正在实现的算法来说，它从何而来并不重要。因此

factProblem :: Integer -> Int
factProblem k = -- fst . last . zip [0..] 
                pred . length
                   . takeWhile (< k) . scanl (*) 1 $ [1..]

main :: IO ()
main = getLine >>= print . factProblem . read