Haskell: Add Function Output to List Until Certain Length

Question

I want to write a function which takes a list and constructs a subset of that list of a certain length based on the output of a function.

If I were simply interested in the first 50 elements of the sorted list xs, then I would use fst (splitAt 50 (sort xs)).

However, the problem is that elements in my list rely on other elements in the same list. If I choose element p, then I MUST also choose elements q and r, even if they are not in the first 50 elements of my list. I am using a function finderFunc which takes an element a from the list xs and returns a list with the element a and all of its required elements. finderFunc works fine. Now, the challenge is to write a function which builds a list whose total length is 50 based on multiple outputs of finderFunc.

Here is my attempt at this:

finish :: [a] -> [a] -> [a]
--This is the base case, which adds nothing to the final list
finish [] fs = []
--The function is recursive, so the fs variable is necessary so that finish 
--  can forward the incomplete list to itself.
finish ps fs
    -- If the final list fs is too small, add elements to it
    | length fs < 50 && length (fs ++ newrs) <= 50 = fs ++ finish newps newrs
    -- If the length is met, then add nothing to the list and quit
    | length fs >= 50 = finish [] fs
    -- These guard statements are currently lacking, not the main problem
    | otherwise = finish [] fs
    where
        --Sort the candidate list
        sortedps = sort ps
        --(finderFunc a) returns a list of type [a] containing a and all the 
        --  elements which are required to go with it.  This is the interesting 
        --  bit.  rs is also a subset of the candidate list ps.
        rs = finderFunc (head sortedps)
        --Remove those elements which are already in the final list, because
        --  there can be overlap
        newrs = filter (`notElem` fs) rs
        --Remove the elements we will add to the list from the new list 
        --  of candidates
        newps = filter (`notElem` rs) ps

I realize that the above if statements will, in some cases, not give me a list of exactly 50 elements. This is not the main problem, right now. The problem is that my function finish does not work at all as I would expect it to. Not only does it produce duplicate elements in the output list, but it sometimes goes far above the total number of elements I want to have in the list.

The way this is written, I usually call it with an empty list, such as: finish xs [], so that the list it builds on starts as an empty list.

Answer 1

| length fs < 50 && length (fs ++ newrs) <= 50 = fs ++ finish newps newrs

Maybe the problem is here ... in the recursive call, newrs will become fs. So on the next recursive call, it will check whether newrs < 50, but you want to check for the total length you've accumulated so far (including the "old" fs).

So you might want to change your code that the recursive call is finish newps (fs ++ newrs).