Как вы находите все подпоследовательности списка?

Ответ 1

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

subsequences [1,2,3]
>>> [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Если вы хотите узнать, как это реализовано, вы можете проверить исходный код который доступен на Hackage.

В этом случае это:

subsequences            :: [a] -> [[a]]
subsequences xs         =  [] : nonEmptySubsequences xs

nonEmptySubsequences         :: [a] -> [[a]]
nonEmptySubsequences []      =  []
nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
  where f ys r = ys : (x : ys) : r

Ответ 2

Еще одно интересное решение:

filterM (const [True,False]) [1,2,3]

Я читал это следующим образом: Верните возможные комбинации включения или отсутствия элемента списка. Это объяснение может не использовать правильную терминологию, но это то, как я интуитивно понимаю это. const оценивает [True,False] для каждого элемента, поэтому каждый элемент включен или не включен в результат. Используя filterM, предикат здесь находится в монаде списка, поэтому мы получаем список возможных результатов.

Ответ 3

Ответ Ezra охватывает все подпоследовательности, но если вы просто хотите непрерывные подпоследовательности, вы можете использовать:

import Data.List
continuousSubSeqs = filter (not . null) . concatMap inits . tails

I. Вы получаете

Prelude Data.List> continuousSubSeqs "asdf"
["a","as","asd","asdf","s","sd","sdf","d","df","f"]

Вышеупомянутое может быть записано как понимание списка:

import Data.List
continuousSubSeqs ls = [t | i <- inits ls, t <- tails i, not $ null t]

Ответ 4

Мне очень нравится ответ @danlei за его выразительность (если вы понимаете недетерминизм, введенный списками). Но для этого вам не нужны Монады. Существует прикладное решение, которое также имеет эту выразительность, возвращая результаты в точно таком же порядке, как решение на основе foldr в библиотеке Data.List.

subs [] = [[]]
subs (x:xs) = subs xs <**> [id, (x :)]

Для меня, как только вы понимаете, как списки обеспечивают недетерминизм (для которых они намного более мощные и полезные, чем они являются простой структурой данных), это становится более понятным, чем реализация foldr.

Он имеет две другие интересные функции по сравнению с библиотечным кодом:

• Просто изменить его, чтобы заменить : на любую моноидальную функцию (или сделать ее общей, чтобы она могла работать с любым моноидом).
• Также легко изменить его для работы с любым складным, для которого есть также моноидный экземпляр (хотя любой складной имеет toList, так что незначительный).

(Конечно, реализация Data.List, используя foldr, позволяет избежать внешних зависимостей)

Например...

xorSubs [] = [0]
xorSubs (x:xs) = xorSubs xs <**> [id, xor x]

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

Так как 0 будет mempty для моноидного экземпляра xor, вам не составит труда увидеть, как вы могли бы переписать его как

msubs :: Monoid a => [a] -> [a]