Получить все разбиения строк

Question

Допустим, у меня есть строка:

"abc7de7f77ghij7"

Я хочу разбить ее на подстроку, 7 в данном случае, и получить все разделения слева и справа:

[ ("abc", "de7f77ghij7")
, ("abc7de", "f77ghij7")
, ("abc7de7f", "7ghij7")
, ("abc7de7f7", "ghij7")
, ("abc7de7f77ghij", "")
]

Пример реализации:

{-# LANGUAGE OverloadedStrings #-}

module StrSplits where

import qualified Data.Text as T

splits :: T.Text -> T.Text -> [(T.Text, T.Text)]
splits d s =
  let run a l r  =
        case T.breakOn d r of
          (x, "") -> reverse a
          (x, y)  ->
            let
                rn = T.drop (T.length d) y
                an = (T.append l x, rn) : a
                ln = l `T.append` x `T.append` d
            in run an ln rn
  in run [] "" s

main = do
  print $ splits "7" "abc7de7f77ghij7"
  print $ splits "8" "abc7de7f77ghij7"

с ожидаемым результатом:

[("abc","de7f77ghij7"),("abc7de","f77ghij7"),("abc7de7f","7ghij7"),("abc7de7f7","ghij7"),("abc7de7f77ghij","")]
[]

Мне не очень нравится ручная рекурсия и let / case / let вложение . Если мне кажется, что это не очень хорошо, то есть ли лучший способ написать это?

Есть ли в Haskell общий подход к решению подобных проблем, подобный тому, как может быть рекурсия заменены на fmap и fold s?

Answer 1

Вот безиндексный.

import Data.List (isPrefixOf, unfoldr)

type ListZipper a = ([a],[a])

moveRight :: ListZipper a -> Maybe (ListZipper a)
moveRight (_, []) = Nothing
moveRight (ls, r:rs) = Just (r:ls, rs)

-- As Data.List.iterate, but generates a finite list ended by Nothing.
unfoldr' :: (a -> Maybe a) -> a -> [a]
unfoldr' f = unfoldr (\x -> (,) x <$> f x)

-- Get all ways to split a list with nonempty suffix
-- Prefix is reversed for efficiency
-- [1,2,3] -> [([],[1,2,3]), ([1],[2,3]), ([2,1],[3])]
splits :: [a] -> [([a],[a])]
splits xs = unfoldr' moveRight ([], xs)

-- This is the function you want.
splitsOn :: (Eq a) => [a] -> [a] -> [([a],[a])]
splitsOn sub xs = [(reverse l, drop (length sub) r) | (l, r) <- splits xs, sub `isPrefixOf` r]

Попробуйте онлайн!

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

Answer 2

Как насчет этого?

import Data.Bifunctor (bimap)

splits' :: T.Text -> T.Text -> [(T.Text, T.Text)]
splits' delimiter string = mkSplit <$> [1..numSplits]
  where
    sections  = T.splitOn delimiter string
    numSplits = length sections - 1
    mkSplit n = bimap (T.intercalate delimiter) (T.intercalate delimiter) $ splitAt n sections

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

Однако не самый эффективный. Вероятно, вы можете сделать что-то подобное с indices из Data.Text.Internal.Search, если хотите, чтобы это было быстро. В этом случае вам не нужно будет выполнять дополнительное повторное соединение. Я не экспериментировал с этим, так как не понимал, что возвращает функция.