Преобразуйте строку в список подстрок, описывающих последовательности

Question

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

Из этой строки "123456789" я бы хотел получить список, подобный так:

["123", "234, "345, ..., "789", "891", "912"]

На данный момент у меня есть только функция, которая разбивает строку на список n частей этой строки:

splitList :: Int -> [a] -> [[a]]
splitList _ [] = []
splitList n xs = as : splitList n bs
    where (as,bs) = splitAt n xs

Answer 1

Я бы сделал это следующим образом:

import Data.List
splitList n xs = zipWith const chunks xs where
    chunks = map (take n) . tails . cycle $ xs

Это должно иметь сложность O (m * n), где m - длина xs, а n - размер каждого куска;наивно кажется, что это должно быть трудно сделать лучше, так как это размер вывода.Он также аккуратно обрабатывает ряд неловких крайних случаев, включая разумную работу с бесконечными входами в список.

Если вы раньше не видели трюк zipWith const, это определенно стоит добавить в ваш арсенал.Это позволяет вам делать примерно то же самое, что и take (length xs) ys, но без фактического вычисления length xs заранее.

Answer 2

splitList :: Int -> [a] -> [[a]]
splitList n xs = zipWith const (map (take n) . tails . cycle $ xs) xs

-- splitList n = zipWith const =<< map (take n) . tails . cycle

-- splitList n = map (take n) . tails . cycle >>= zipWith const

делает работу, а также работает с бесконечным вводом, то есть правильно ленив.

zipWith const используется вместо length и take, считая элементы списка вместо чисел.

Бессмысленные варианты даже читабельны / немного освещают то, что здесь происходит.

(забыл упомянуть, tails из Data.List).

Answer 3

Я бы просто использовал комбинацию take и drop с пониманием списка:

splitList :: Int -> [a] -> [[a]]
splitList n xs = [take n $ drop i $ xs ++ xs | i <- [0..(length xs - 1)]]

(xs ++ xs только для того, чтобы получить «циклический» эффект, его можно настроить, чтобы добавить только первые (n-1) элементы, но я считаю, что лень Хаскелла должна означать, что при этом не происходит потери эффективности) вот так)