1

这是我正在处理的示例问题：

示例输入：test [4, 1, 5, 6] 6返回5

我正在使用此功能解决此问题：

test :: [Int] -> Int -> Int
test [] _ = 0
test (x:xs) time = if (time - x) < 0
                   then x
                   else test xs $ time - x

有什么更好的方法来解决这个函数（可能使用任何内置的高阶函数）？

4

5 回答 5

2

怎么样

test xs time = maybe 0 id . fmap snd . find ((>time) . fst) $ zip sums xs
   where sums =  scanl1 (+) xs

或等效地与含糖的列表理解

 test xs time = headDef 0 $ [v | (s, v) <- zip sums xs, s > time]
      where sums = scanl1 (+) xs

headDef由安全提供。实现 ( f _ (x:_) = x; f x _ = x) 很简单，但安全包有很多有用的功能，所以最好检查一下。

它将列表汇总到每个点并找到大于 的第一个出现time。scanl是一个有用的函数，它的行为类似于foldl但保留中间结果并将zip两个列表压缩到一个元组列表中。然后我们只需使用fmapandmaybe来操作Maybe (Integer, Integer)来获得我们的结果。

这默认为 0 就像你的一样，但我喜欢Maybe Integer从用户的角度来看更好的版本，只需删除maybe 0 id.

于 2013-09-26T23:40:25.833 回答
1

你可能会喜欢scanl和它的近亲，scanl1. 例如：

test_ xs time = [curr | (curr, tot) <- zip xs (scanl1 (+) xs), tot > time]

这会找到运行总和大于 的所有位置time。然后你可以像这样选择第一个（或0）：

safeHead def xs = head (xs ++ [def])
test xs time = safeHead 0 (test_ xs time)
于 2013-09-27T00:57:35.583 回答
1

这很冗长，我不一定建议编写这样一个简单的函数（IMO 模式匹配和递归非常清楚）。但是，这是一个非常声明性的管道：

import Control.Error
import Data.List

deadline :: (Num a, Ord a) => a -> [a] -> a
deadline time = fromMaybe 0 . findDeadline time

findDeadline :: (Num a, Ord a) => a -> [a] -> Maybe a
findDeadline time xs = decayWithDifferences time xs
                   >>= findIndex (< 0)
                   >>= atMay xs

decayWithDifferences :: Num b => b -> [b] -> Maybe [b]
decayWithDifferences time = tailMay . scanl (-) time

-- > deadline 6 [4, 1, 5, 6]
-- 5

这稍微记录了代码，原则上让您测试得更好一些，尽管 IMO 这些函数或多或少属于“明显正确”的类别。

您可以验证它是否与您的实现匹配：

import Test.QuickCheck

prop_equality :: [Int] -> Int -> Bool
prop_equality time xs = test xs time == deadline time xs

-- > quickCheck prop_equality
-- +++ OK, passed 100 tests.
于 2013-09-27T01:04:50.720 回答
1

在这种特殊情况下，其他人建议的压缩不是很有必要：

test xs time = head $ [y-x | (x:y:_) <- tails $ scanl1 (+) $ 0:xs, y > time]++[0]

此处scanl1将生成 list 的滚动总和列表xs，从 0 开始。因此，tails将生成一个列表，其中至少有一个包含两个非空元素的列表xs。模式匹配(x:y:_)从滚动和的每个尾部提取两个元素，因此实际上它枚举了滚动和列表中的相邻元素对。根据条件过滤，我们重构列表的一部分，该部分从产生大于 的滚动和的第一个元素开始time。然后headDef 0按照之前的建议使用，或者附加一个[0]，这样head总是返回一些东西。

于 2013-09-27T09:15:43.843 回答
1

如果您想保持可读性，我会坚持使用您当前的解决方案。这很容易理解，并且没有做错任何事情。

仅仅因为您可以将其制成单行扫描地图折叠突变体并不意味着您应该这样做！

于 2013-09-27T09:29:08.977 回答