Generating lists-CodePudding

I would really appreciate it if someone could help me with this task.

Let two lists of integers xs and ys be given in ascending order. Define a function

generate :: [Int] -> [Int] -> [[Int]]

that returns all possible lists of numbers in ascending order for which the first element is from xs, the second element is from ys, etc. Necessarily the last element of each of these lists is a number from the ys list.

Examples:

generate [10, 15, 25] [1, 5, 20, 30] == [[10, 20], [10, 30], [15, 20], [15, 30], [25, 30], [10, 20, 25, 30], [15, 20, 25, 30]]

This is what i've done so far but doesn't work for all cases.

generate :: [Int] -> [Int] -> [[Int]]
generate [] [] = [[]]
generate xs ys = nub $ twos xs ys    processMore xs ys
  where
    twos xs ys = [[x, y] | x <- xs, y <- ys, x < y]
    more [] _ = []
    more _ [] = []
    more (x : xs) (y : ys)
      | x < y = x : y : more (filter (> y) xs) ys
      | otherwise = more (x : xs) ys
    processMore [] _ = []
    processMore xs ys = more xs ys : processMore (tail xs) ys

For the above example it works fine, however for this one:

-- this is what i SHOULD get
generate [1, 5, 8] [2, 6, 67] == [[1, 2], [1, 6], [1, 67], [5, 6], [5, 67], [8, 67], [1, 2, 5, 6, 8, 67], [5, 6, 8, 67], [1, 2, 5, 67], [1, 6, 8, 67], [1, 2, 8, 67], [1, 2, 5, 6]]


-- But this is what i actually get( and the problem comes from the processMore, but don't know how to fix it):
generate [1, 5, 8] [2, 6, 67] -> [[1,2],[1,6],[1,67],[5,6],[5,67],[8,67],[1,2,5,6,8,67],[5,6,8,67],[8,67]] -- this is what i get

CodePudding user response：

I haven't spotted the bug in your code, But I think there is a better approach. You can think the problem as having building blocks of pairs (in your code the twos function). Then, construct bigger lists out of those blocks until you can't do it any more.

As an example

xs = [10, 15, 25] 
ys = [20, 30]
building_blocks = [(10,20), (10,30), (15, 20), (15,30), (25, 30)] -- notice this is a list of pairs not a list of list

-- The first iteration is just the list of building blocks
[[10,20], [10,30], [15, 20], [15,30], [25, 30]]

-- The second iteration we need to take the previous result and add more building blocks. 
-- The adding condition is that the last elem of the list must be less than the head
-- of the building block.

   [[10,20], [10,30], [15,20], [15,30], [25,30]] -- comming from first iter
   [[10,20,25,30], [15,20,25,30]]                -- from second iteration.

-- We need to continue taking the result of the previous iter and adding building blocks
-- until no more blocks can't be added.
   [[10,20], [10,30], [15,20], [15,30], [25,30]] -- comming from first iter
   [[10,20,25,30], [15,20,25,30]]                -- from second iteration.
   []                                            -- from third iter

Using this perspective we can write the code

-- This is an auxiliary function which given a list of list
-- and a list of building blocks, it returns the list of lists
-- expanded by the blocks.
addBuildingBlock :: [[Int]] -> [(Int, Int)] -> [[Int]]
addBuildingBlock xss ps = 
  [xs    [a,b] | xs <- xss, (a, b) <- ps, last xs < a]

generate :: [Int] -> [Int] -> [[Int]]
generate xs ys = recursive initial_pairs
  where
    -- The building blocks as pairs
    building_blocks = [(x,y) | x <- xs , y <- ys, x < y]
    -- The initial pairs which are the same as the building blocks
    initial_pairs = [[x,y] | x <- xs , y <- ys, x < y]
    -- the recursive call. Keep adding blocks until you can't
    -- left as and exercise
    recursive :: [[Int]] -> [[Int]]
    recursive l = 
     let longer = addBuildingBlock l building_blocks -- The list which is the last iteration elongated by all the building blocks
     in case longer of
          [] -> undefined
          _  -> undefined

CodePudding user response：

Here is an approach that I like. Rather than scanning through both lists up front to find valid pairs, I like to think of it as iterating through the lists, at each point choosing "should I include this element, or skip it?" Because we can either skip it or include it, I use (<|>), the choice operator from Alternative, to indicate choice. For lists this is equivalent to ( ), but I think it better portrays the algorithm as choosing.

generate :: [Int] -> [Int] -> [[Int]]
generate [] _ = []
generate (x : xs) ys = useFirstX <|> skipFirstX
  where skipFirstX = generate xs ys
        useFirstX = chooseY (dropWhile (<= x) ys)
        chooseY [] = []
        chooseY (y : ys) = useFirstY <|> skipFirstY
          where skipFirstY = findY ys
                useFirstY = ([x, y]   ) <$> ([] : generate (dropWhile (<= y) xs) ys)

If xs is empty, we can't produce any pairs. If it's not empty, we can either skip the first x or use it. To use it, throw away all the ys smaller than it, and then choose one.

To choose a y is equally simple. If ys is empty, we can't choose one, so we produce nothing. Otherwise, we know all the elements in ys are larger than the x we chose, so we can freely choose any y. Skipping the first y is easy: just throw it away and keep going.

Choosing the first y is the only complicated line in this solution. We chose an x and a y, so we know every solution will have to start with [x, y]. Thus we prepend that list to all the recursive solutions. What are the recursive solutions? Well, we could stop here ([]), or we could keep going, by calling generate xs ys again, after throwing away the xs that are less than the y we chose to use.