我一直在嘗試在haskell中解決以下問題：
生成一個元組串列 (n, s)，其中 0 ≤ n ≤ 100 且 n mod 2 = 0，其中 s = sum(1..n) 輸出應該是串列 [(0,0),(2, 3),(4,10),...,(100,5050)]來源
我嘗試使用以下代碼解決問題：
genListTupleSumUntilX :: Int -> [(Int,Int)]
genListTupleSumUntilX x =
take x [(n, s) | n <- [1..x], s <- sumUntilN x]
where
sumUntilN :: Int -> [Int]
sumUntilN n
| n == 0 = []
| n == 1 = [1]
| otherwise = sumUntilN (n-1) [sum[1..n]]
但是，此代碼沒有給出預期的結果。（正如@Guru Stron 指出的那樣——謝謝！）
如果有人可以幫助我使這段代碼更簡潔，我也將不勝感激。我對惰性評估的概念也很陌生，因此無法確定運行時復雜性。幫助將不勝感激。
但是我覺得這段代碼仍然可以改進，特別是：
take x在功能上似乎真的很不雅。那么有沒有辦法讓串列理解只映射到同一個索引？sumUntilN感覺真的很啰嗦。在 haskell 中是否有慣用的方法來做同樣的事情？
最后，我對 haskell 非常陌生，無法評估函式的時間和空間復雜度。有人可以幫我嗎？
uj5u.com熱心網友回復：
sumOfNumsUptoN n = n * (n 1) `div` 2
genListTupleSumUntilX :: Int -> [(Int, Int)]
genListTupleSumUntilX n = zip [0, 2 .. n] $ map sumOfNumsUptoN [0, 2 .. n]
這在串列的大小上具有線性復雜性。
uj5u.com熱心網友回復：
我會說你把事情復雜化了。要產生正確的輸出，您可以使用簡單的串列推導：
genListTupleSumUntilX :: Int -> [(Int,Int)]
genListTupleSumUntilX x = [(n, sum [1..n]) | n <- [0,2..x]]
請注意，此解決方案將重復重新計算相同的總和（即n 1元素總和實際上是n 2 n 1 sumForNthElemnt，因此您可以潛在地重用計算），這將導致 O(n^2) 復雜度，但對于如此相對較小的n來說，這不是一個大問題。您可以使用scanl函式處理此問題（盡管可能有更多慣用的記憶方法）：
genListTupleSumUntilX :: Int -> [(Int,Int)]
genListTupleSumUntilX 0 = []
genListTupleSumUntilX x = scanl (\ (prev, prevSum) curr -> (curr, prevSum prev 1 curr)) (0,0) [2,4..x]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498197.html
上一篇：字串/陣列的列印能力