1

ここに私が取り組んでいるサンプルの問題があります:

入力例: test [4, 1, 5, 6] 6return5

私はこの関数を使用してこれを解決しています：

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。のように動作しますが、中間結果を保持し、2 つのリストをタプルのリストに圧縮scanlする便利な関数です。次に、 and を使用して を操作し、結果を取得します。foldlzipfmapmaybeMaybe (Integer, Integer)

Maybe Integerこれはあなたのようにデフォルトで 0 ですが、ユーザーの観点から単純に改善されるバージョンが好きです。これを取得するには、 maybe 0 id.

于 2013-09-26T23:40:25.833 に答える
1

読みやすさを維持したい場合は、現在のソリューションに固執します。わかりやすいですし、間違ったことはしていません。

1 行のスキャン マップ フォールド ミュータントにできるからといって、そうすべきだという意味ではありません。

于 2013-09-27T09:29:08.977 に答える
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

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 に答える