更好的辦法來解決這個[INT] - >內部 - >內部

這裏是我在工作一個樣本問題：更好的辦法來解決這個[INT] - >內部 - >內部

示例輸入：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

解決此功能的任何更好的方法（可能使用任何內置的高階函數）？

來源

2013-09-26 Sibi

只是想象*你有一個更高階的函數可以幫助解決這個問題。那個更高階的函數會做什麼？你能告訴我們你將如何使用它來解決問題嗎？ –

而不是一個評論的問題：解決這個問題的最佳方法是TS提供的算法嗎？我的意思是，所有答案都要貴得多，不是嗎？ – kaan

@kaan TS是什麼意思？ – Sibi

如何

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由safe提供。實現（f _ (x:_) = x; f x _ = x）很簡單，但安全軟件包中有許多有用的功能，所以最好檢查一下。

它將列表總結到每個點，並找到大於time的第一個發生次數。 scanl是一個有用的函數，其行爲類似於foldl，但保留中間結果和zip將兩個列表拉入到元組列表中。然後，我們只需使用fmap和maybe來操縱Maybe (Integer, Integer)即可獲得我們的結果。

默認爲0喜歡你的，但我喜歡這樣簡單地去Maybe Integer從用戶的角度來看更好，讓這個簡單的刪除maybe 0 id版本。

來源

2013-09-26 23:40:25 jozefg

您可能會喜歡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-27 00:57:35

這是冗長，我不一定建議寫這樣如此簡單的功能（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-27 01:04:50 jtobin

在這種特殊情況下，不太需要別人荏苒建議：

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

這裏scanl1會產生滾動列表列表xs的總和，從0開始。因此，tails將生成一個列表，其中至少有一個列表具有非空的兩個元素xs。模式匹配(x:y:_)從滾動和的每個尾部中提取兩個元素，因此實際上它列舉了滾動和的列表中的相鄰元素對。根據條件進行過濾，我們重建列表的一部分，第一個元素的第一個元素產生大於time的滾動總和。然後按照前面建議的那樣使用headDef 0，或者附加一個[0]，以便head總是返回一些內容。

來源

2013-09-27 09:15:43

如果你想保持可讀性，我會堅持使用你當前的解決方案。這很容易理解，並沒有做錯任何事情。

僅僅因爲你可以使其變成一個行掃描地圖倍的突變並不意味着你應該！

來源

2013-09-27 09:29:08 Tetigi

更好的辦法來解決這個[INT] - >內部 - >內部

回答

相關問題