通过在haskell中获取相同的索引来列表

发布于 2025-02-12 12:02:14 字数 1002 浏览 0 评论 0原文

我一直在尝试解决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指出的那样 - 谢谢！）

如果有人可以帮助我更简洁，我也将不胜感激。我也是懒惰评估概念的新手，因此无法确定运行时的复杂性。帮助将不胜感激。

~~但是，我觉得这个代码仍然可以改进，尤其是：~~

将X中的X 带入该功能似乎确实很重要。因此，是否有一种方法可以使列表组成仅映射到相同的索引？
sumuntiln感觉真的冗长。是否有愚蠢的方法在Haskell 中做同样的方法？

~~最后，我对Haskell非常陌生，并且难以评估功能的时间和空间复杂性。有人可以帮我吗？~~

原文

I have been trying to solve the following problem in haskell:

Generate a list of tuples (n, s) where 0 ≤ n ≤ 100 and n mod 2 = 0,
and where s = sum(1..n) The output should be the list
[(0,0),(2,3),(4,10),...,(100,5050)] Source

I tried to solve the problem with following code:

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]]

However, this code does not give the expected result. (as @Guru Stron Pointed out- Thank you!)

I would also appreciate it if somebody could help me make this code more concise. I am also new to the concept of lazy evaluation, so am unable to determine the runtime complexity. Help will be appreciated.

~~However I feel like this code could still be improved upon, espically with:~~

take x in the function seems really inelegant. So Is there a way to have list comprhensions only map to the same index?
sumUntilN feels really verbose. Is there an idiomatic way to do the same in haskell?

Finally, I am extremely new to haskell and have trouble evaluating the time and space complexity of the function. Can somebody help me there?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

天涯沦落人 2025-02-19 12:02:14

sumOfNumsUptoN n = n * (n + 1) `div` 2

genListTupleSumUntilX :: Int -> [(Int, Int)]
genListTupleSumUntilX n = zip [0, 2 .. n] $ map sumOfNumsUptoN [0, 2 .. n]

这是列表大小的线性复杂性。

sumOfNumsUptoN n = n * (n + 1) `div` 2

genListTupleSumUntilX :: Int -> [(Int, Int)]
genListTupleSumUntilX n = zip [0, 2 .. n] $ map sumOfNumsUptoN [0, 2 .. n]

This is of linear complexity on the size of the list.

回复收藏 0 原文

苦行僧 2025-02-19 12:02:14

我要说的是，您过于编。要产生正确的输出，您可以使用简单的列表理解：

genListTupleSumUntilX :: Int -> [(Int,Int)]
genListTupleSumUntilX x = [(n, sum [1..n]) | n <- [0,2..x]]

请注意，此解决方案将重复重新计算相同的总和（即n + 1 element>元素总和实际上是n + 2 + 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]

I would say that you overcomplicate things. To produce correct output you can use simple list comprehension:

genListTupleSumUntilX :: Int -> [(Int,Int)]
genListTupleSumUntilX x = [(n, sum [1..n]) | n <- [0,2..x]]

Note that this solution will recalculate the same sums repeatedly (i.e for n+1 element sum is actually n + 2 + n + 1 + sumForNthElemnt, so you can potentially reuse the computation) which will lead to O(n^2) complexity, but for such relatively small n it is not a big issue. You can handle this using scanl function (though maybe there is more idiomatic approach for memoization):

genListTupleSumUntilX :: Int -> [(Int,Int)]
genListTupleSumUntilX 0 = []
genListTupleSumUntilX x = scanl (\ (prev, prevSum) curr -> (curr, prevSum + prev + 1 + curr)) (0,0) [2,4..x]

回复收藏 0 原文

~没有更多了~