Haskell: добавить вывод функции в список до определенной длины

Question

Я хочу написать функцию, которая принимает список и создает подмножество этого списка определенной длины на основе выходных данных функции.

Если бы меня просто интересовали первые 50 элементов отсортированного списка xs, я бы использовал fst (splitAt 50 (sort xs)).

Однако проблема в том, что элементы в моем списке зависят от других элементов втот же список.Если я выберу элемент p, тогда я ДОЛЖЕН также выбрать элементы q и r, даже если их нет в первых 50 элементах моего списка.Я использую функцию finderFunc, которая берет элемент a из списка xs и возвращает список с элементом a и всеми его необходимыми элементами.finderFunc работает отлично.Теперь задача состоит в том, чтобы написать функцию, которая создает список, общая длина которого равна 50, на основе нескольких выходных данных finderFunc.

Вот моя попытка:

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

Я понимаю, чтоПриведенные выше операторы if в некоторых случаях не дают мне список из точно 50 элементов.Это не главная проблема, прямо сейчас.Проблема в том, что моя функция finish не работает вообще, как я ожидал.Он не только создает дубликаты элементов в выходном списке, но иногда намного превышает общее количество элементов, которые я хочу иметь в списке.

Как это написано, я обычно называю его пустымlist, например: finish xs [], так что список, на котором он построен, начинается как пустой список.

Answer 1

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

Возможно, проблема здесь ... в рекурсивном вызове newrs станет fs.Поэтому при следующем рекурсивном вызове он проверит, является ли newrs < 50, но вы хотите проверить общую накопленную вами длину (включая «старый» fs).

Так что вы можетехотите изменить свой код, чтобы рекурсивный вызов был finish newps (fs ++ newrs).

Answer 2

Я понимаю, что не ясно изложил свою проблему.Мне нужна была функция, которая взяла список ps и вернула подсписок fs из ps.Кроме того, у элементов в ps есть предпосылки, которые являются другими элементами в ps.Таким образом, при добавлении элемента a в список fs функция также должна добавить все предварительные условия a к fs.Хитрость заключается в том, что в fs не добавляются дубликаты.Различные элементы в ps могут иметь перекрывающиеся предпосылки, но fs должен быть списком отдельных элементов.

Это, наконец, сработало для меня:

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

Ключевое отличие от вышеупомянутой функции заключается в том, что яя не пересылаю newfs в рекурсию функции, я пересылаю (fs ++ newfs).

Answer 3

Это очень распространенный сценарий использования аккумуляторов. Обычное решение - определить

finish1 fs = finish [] fs

Если финиш полезен только как часть финиша1, вы можете сделать это так:

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

См. Аккумуляторы в haskell для получения информации о связанной проблеме при рекурсивной реализации факториальной функции.

Что касается ограничения длины до 50 элементов, вы можете создать длинный список, а затем взять 50 первых его элементов, используя функцию take. Из-за особого порядка эвакуации в Haskell он эффективен.