Как мне вернуть список всех префиксов данного списка?

Question

Я хотел бы написать функцию только с использованием foldr, которая возвращает список всех префиксов данного списка. Поэтому, если список равен [4,5,6], я бы вернул [[],[4],[4,5],[4,5,6]]. Пока у меня есть

preFix :: [a] -> [[a]]
preFix x = foldr preFixHelp [[]] x

preFixHelp :: a -> [[a]] -> [[a]]
preFixHelp x acc = [x] : acc

, но это только возвращает [[4],[5],[6]]. Спасибо!

Answer 1

Уже есть функция, которая делает это в стандартных библиотеках: Data.List.inits

>>> inits "abc"
["","a","ab","abc"]

---

Если вы хотите по какой-то причине реализовать ее самостоятельно, и только используя fold (домашнюю работу?), способ думать об этом так: (1) все префиксы пустого списка - это список, содержащий только пустой список. Запишем это:

prefix [] = [[]]

(2) все префиксы списка, состоящего из заголовка x и хвоста xs, будут такими же, как и все префиксы xs, но с x перед каждым, плюс пустой список. Давайте запишем это:

prefix (x:xs) = [] : [x:pref | pref <- prefix xs]

Давайте проверим это:

>>> prefix [1,2,3]
[[], [1], [1, 2], [1, 2, 3]]

Пока все хорошо.

Теперь такой линейно-рекурсивный алгоритм может быть легко превращается в foldr, если вы заметили, что:

foldr f z [x0, x1, ... xn]   ==   f x0 (f x1 ... (f xn z)...)

(это прямо из документов )

Другими словами, каждый вызов функции получает «текущий» элемент списка в качестве первого параметра и результат предыдущего вызова функции в качестве второго параметра, и это как раз то, что нужно нашему рекурсивному случаю выше:

prefix (x:xs) = [] : [x:pref | pref <- prefix xs]
                      ^                ^^^^^^^^^
                      |                |       |
                   current element     +--- ---+
                                           |
                                          result of the previous call

Таким образом, мы можем легко перефразировать этот рекурсивный случай функция в терминах foldr, как это:

prefixFold :: [a] -> [[a]]
prefixFold = foldr go [[]]
    where
        go x previousResult = [] : [x:pref | pref <- previousResult]