Using foldr on a list of infinite lists-CodePudding

I am trying to write a function in Haskell, that does the following: You input a list of integers, for these integers, using map, there is a function applied to them that returns an infinite list of these integers. Then, I want to apply foldr to the list of lists, using union, so that the result will be the union of those lists in the list.

Now the problem is that when I do for example take 10 'function' [1,2], it will first calculate the infinite list for 1, and because it is an infinite list, it will never do this for 2. So then it returns only the first 10 elements of this infinite list of the first elements in the input list, with union applied to it, which is just the same list.

My question is: is there a way to create the infinite lists for all the elements in the input list at the same time, so that when I do take 10 'function' [1,2] for example, it will return the first 10 elements of the union of the infinite lists for 1 and 2. (I don't know the number of elements in the input list)

This is my code, to make it clearer:

pow :: Integer -> [Integer]
pow n = map (^n) [1, 2..]

function :: [Integer] -> [Integer]
function xs = foldr union [] (map pow xs)

CodePudding user response：

The union function works on arbitrary lists and removes duplicates, so it must first evaluate one of its arguments completely before it can continue with the other argument.

I think you want to explicitly introduce the assumption that your lists are sorted, then you can write an efficient function that merges (like the merge in a merge sort) the input lists and computes the union without needing to evaluate one of the lists before the other.

I don't know if such a merge function exists in a library, but you can pretty easily define it yourself:

-- | Computes the union of two sorted lists
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y    = x : merge (dropWhile (== x) xs) (dropWhile (== x) (y:ys))
  | otherwise = y : merge (x:xs) (dropWhile (== y) ys)

Then your original fold with this new merge function should behave as desired:

ghci> pow n = map (^n) [1..]
ghci> function xs = foldr merge [] (map pow xs)
ghci> take 10 (function [2,3])
[1,4,8,9,16,25,27,36,49,64]

CodePudding user response：

If you intend the input and output lists to be sorted, check out data-ordlist. If you just want all the elements but don't care what order, try concat . transpose.