最多可以放直的骰子数 (Haskell) [旧]

Question

这个问题涉及任意数量的骰子，每个骰子的面数都是任意的。然后我们找到可以放入顺子的最大骰子数，参见 Google's Code Jam explanation。我一直在尝试解决 Haskell 中的问题，我认为以下解决方案在算法上可行。但是做题速度不够快得满分，能不能优化一下？

import Data.List (sort)

getMaxStraight :: [Int] -> Int
getMaxStraight sides =
  foldl
    (\maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight)
    0
    (sort sides)

除此之外，我还编写了 Python 解决方案，它及时运行。怎么回事？

def solve(sides)
    sides = sorted(sides)
    max_straight = 0
    for side in sides:
        if side > max_straight:
            max_straight += 1
    return max_straight

编辑：此 post 已“恢复”到旧版本。可以找到 post 的更新版本 here

Answer 1

你在这里做的是构建一个大型表达式树，它将查找列表 [1, 2, 3, 4, 5, 6] 作为：

f (f (f (f (f (f 0 1) 2) 3) 4) 5) 6

与 f lambda 表达式 \maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight。因此，您将首先创建一个可能占用大量内存的大型表达式，然后对其求值。

作为 documentation on foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b says:

If you want an efficient strict left-fold, you probably want to use foldl' instead of foldl. The reason for this is that the latter does not force the inner results (e.g. z `f` x1 in the above example) before applying them to the operator (e.g. to (`f` x2)). This results in a thunk chain (n) elements long, which then must be evaluated from the outside-in.

通过使用 foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b, for each step, the result will be evaluated to Weak Head Normal Form (WHNF) ^{[haskell-wiki]}，这样你就可以避免创建一个大的 thunk。你可以这样实现：

import Data.Foldable(<strong>foldl'</strong>)

getMaxStraight :: [Int] -> Int
getMaxStraight sides =
  <strong>foldl'</strong>
    (\maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight)
    0
    (sort sides)

最多可以放直的骰子数 (Haskell) [旧]

Maximum number of dice that can be put straight (Haskell) [Old]

optimization

haskell