Haskell Add Function Return to List Until Certain Length
- by kienjakenobi
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.
