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).

Answer 2

This is a very common scenario of using accumulators. The usual solution is to define

finish1 fs = finish [] fs

If finish is only useful as a part of finish1, you can do like this:

finish fs = finish1 [] fs where
    finish1 :: [a] -> [a] -> [a]
    --This is the base case, which adds nothing to the final list
    finish1 [] fs = []
    --The function is recursive, so the fs variable is necessary so that finish 
    --  can forward the incomplete list to itself.
    finish1 ps fs = ...

See Accumulators in haskell for a related problem when implementing factorial function recursively.

As for limiting length to 50 elements, you can construct a long list and then take 50 first elements of it using take function. Because of Haskell's specific eveluation order it is efficient.

Answer 3

I realize I did not state my problem clearly. I needed a function which took a list ps and returned a sublist fs of ps. Furthermore, elements in ps have prerequisites, which are other elements in ps. So, when adding element a to the list fs, the function must also add all of a's prerequisites to fs. The trick bit is making sure that no duplicates are added to fs. Different elements in ps can have overlapping prerequisites, but fs should be a list of distinct elements.

This finally worked for me:

finish :: [a] -> [a] -> [a]
finish ps fs
    | length fs < 50 && length (fs ++ newfs) <= n = finish newps (fs ++ newfs) n
    --If adding a new perk and its prerequisites will bring me over the limit, then ignore it and move to the next perk
    | length fs < 50 && length (fs ++ newfs) > n = finish (tail (reverse (sort ps))) fs n
    | otherwise = fs
    where
        --This is the interesting value of the given list ps
        inter = maximum ps
        --A list of all values which might be useful for 
        maybeNewfs = perkAndPreqs inter
        --Whittle that list down to a list of distinctly new elements
        newfs = filter (`notElem` fs) maybeNewfs
        --Now remove all items added to fs from the candidate list
        newps = filter (`notElem` maybeNewfs) ps

The key difference from the above function is that I am not forwarding newfs to the recursion of the function, I am forwarding (fs ++ newfs).