List of tuples by taking the same index for an element in haskell-CodePudding

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?~~

CodePudding user response：

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.

CodePudding user response：

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]