Учитывая список, как я могу выполнить некоторые преобразования только в подсписках, каждые два элемента которых удовлетворяют двоичному предикату?

Question

(В моем фактическом случае использования у меня есть список типа [SomeType], SomeTypeналичие конечного числа конструкторов, все нулевые; в дальнейшем я буду использовать String вместо [SomeType] и использовать только 4 Chars, чтобы немного упростить.)

У меня есть такой список "aaassddddfaaaffddsssadddssdffsdf" где каждый элемент может быть одним из 'a', 's', 'd', 'f', и я хочу произвести дополнительную обработку каждой непрерывной последовательности неas, скажем, переворачивая их в верхний регистр и меняя последовательность на обратную, таким образом получая "aaaFDDDDSSaaaSSSDDFFaFDSFFDSSDDD". (Я добавил требование реверсирования, чтобы прояснить, что обработка включает в себя все смежные не 'a'-s в то же время.)

Чтобы включить каждый суб-String верхний регистр, я могу использовать это:

func :: String -> String
func = reverse . map Data.Char.toUpper

Но как мне запустить это func только на суб-Strings не-'a'с?

Моя первая мысль, что Data.List.groupBy может быть полезным, и общее решение может быть таким:

concat $ map (\x -> if head x == 'a' then x else func x)
       $ Data.List.groupBy ((==) `on` (== 'a')) "aaassddddfaaaffddsssadddssdffsdf"

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

Я ищу советы, как мне лучше всего выполнить эту небольшую задачу.

Об ответах

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

Answer 1

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

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Arrow ((&&&))
import Data.Function (on)
import Data.Monoid (First(..))

mapSegmentsWhere
  :: forall a. (a -> Bool) -> ([a] -> [a]) -> [a] -> [a]
mapSegmentsWhere p f
  = concatMap (applyMatching . sequenceA)  -- [a]
  . groupBy ((==) `on` fst)                -- [[(First Bool, a)]]
  . map (First . Just . p &&& id)          -- [(First Bool, a)]
  where
    applyMatching :: (First Bool, [a]) -> [a]
    applyMatching (First (Just matching), xs)
      = applyIf matching f xs

    applyIf :: forall a. Bool -> (a -> a) -> a -> a
    applyIf condition f
      | condition = f
      | otherwise = id

Пример использования:

> mapSegmentsWhere (/= 'a') (reverse . map toUpper) "aaassddddfaaaffddsssadddssdffsdf"
"aaaFDDDDSSaaaSSSDDFFaFDSFFDSSDDD"

Здесь я использую First моноид с sequenceA объединить списки смежных совпадающих элементов из [(Bool, a)] к (Bool, [a]), но вы также можете использовать что-то вроде map (fst . head &&& map snd). Вы также можете пропустить ScopedTypeVariablesесли вы не хотите писать подписи типа; Я просто включил их для ясности.

Answer 2

Если нам нужно помнить разницу между 'a's и остальные, давайте поместим их в разные ветки Either. Фактически, теперь, когда мы находимся, давайте определим новый тип:

{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE ViewPatterns #-}

import Data.Bifoldable
import Data.Char
import Data.List

newtype Bunched a b = Bunched [Either a b] deriving (Functor, Foldable)

instance Bifunctor Bunched where
  bimap f g (Bunched b) = Bunched (fmap (bimap f g) b)

instance Bifoldable Bunched where
  bifoldMap f g (Bunched b) = mconcat (fmap (bifoldMap f g) b)

fmap позволит поработать без разделителей. fold вернет конкатенацию разделителей, bifold вернет конкатенацию всего. Конечно, мы могли бы определить отдельные функции, не связанные с Foldable и Bifoldable, но зачем избегать уже существующих абстракций?

Чтобы разделить список, мы можем использовать unfoldr который поочередно ищет as и не-as с span функция:

splitty :: Char -> String -> Bunched String String
splitty c str = Bunched $ unfoldr step (True, str)
  where
    step (_, []) = Nothing
    step (True, span (== c) -> (as, ys)) = Just (Left as, (False, ys))
    step (False, span (/= c) -> (xs, ys)) = Just (Right xs, (True, ys))

Запускаем:

ghci> bifold . fmap func . splitty 'a' $ "aaassddddfaaaffddsssadddssdffsdf"
"aaaFDDDDSSaaaSSSDDFFaFDSFFDSSDDD"

---

Примечание: Bunched на самом деле то же самое, что Tannen [] Eitherиз пакета bifunctors, если вы не возражаете против дополнительной зависимости.

Answer 3

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

onRuns :: Monoid m => (a -> Bool) -> ([a] -> m) -> ([a] -> m) -> [a] -> m
onRuns p = go p (not . p) where
    go _ _ _ _ [] = mempty
    go p p' f f' xs = case span p xs of
        (ts, rest) -> f ts `mappend` go p' p f' f rest

Попробуйте в ghci:

Data.Char> onRuns ('a'==) id (reverse . map toUpper) "aaassddddfaaaffddsssadddssdffsdf"
"aaaFDDDDSSaaaSSSDDFFaFDSFFDSSDDD"

Answer 4

Мы можем делать то, что вы описываете, шаг за шагом, получая ясный простой минимальный код, который мы сможем легко прочитать и понять позже:

      foo :: (a -> Bool) -> ([a] -> [a]) -> [a] -> [a]
foo p f xs = [ a
         | g <- groupBy ((==) `on` fst) 
                      [(p x, x) | x <- xs]  -- [ (True, 'a'), ... ]
         , let (t:_, as) = unzip g          -- ( [True, ...], "aaa" )
         , a <- if t then as else (f as) ]  -- final concat

         -- unzip :: [(b, a)] -> ([b], [a])

Разбиваем список на одинаковые- p пролеты и распаковать каждую группу с помощью unzip. Пробуем:

      > foo (=='a') reverse "aaabcdeaa"
"aaaedcbaa"

Так что нет, используя == 'a' это избежать , и , следовательно , не особенно хорошо, представляя ненужное ограничение на ваш тип данных , когда все , что нам нужно это равенство на Booleans.

Answer 5

Вот простое решение - функция process ниже - для этого требуется только определить две функции isSpecial и func. Учитывая конструктор вашего типа SomeType, isSpecialопределяет, является ли он одним из тех конструкторов, которые образуют специальный подсписок. Функция funcэто тот, который вы указали в своем вопросе; он определяет, что должно происходить со специальными подсписками.

Код ниже предназначен для списков символов. Просто измени isSpecial и func чтобы он работал для ваших списков конструкторов.

isSpecial c = c /= 'a'
func = reverse . map toUpper

turn = map (\x -> ([x], isSpecial x)) 

amalgamate []  = []
amalgamate [x] = [x]
amalgamate ((xs, xflag) : (ys, yflag) : rest)
   | xflag /= yflag = (xs, xflag) : amalgamate ((ys, yflag) : rest)
   | otherwise      = amalgamate ((xs++ys, xflag) : rest)

work = map (\(xs, flag) -> if flag then func xs else xs)

process = concat . work . amalgamate . turn

Попробуем на вашем примере:

*Main> process "aaassddddfaaaffddsssadddssdffsdf"
"aaaFDDDDSSaaaSSSDDFFaFDSFFDSSDDD"
*Main> 

При применении одной функции за раз показаны предпринятые промежуточные шаги:

*Main> turn "aaassddddfaaaffddsssadddssdffsdf"
[("a",False),("a",False),("a",False),("s",True),("s",True),("d",True),
("d",True),("d",True),("d",True),("f",True),("a",False),("a",False),
("a",False),("f",True),("f",True),("d",True),("d",True),("s",True),
("s",True),("s",True),("a",False),("d",True),("d",True),("d",True),
("s",True),("s",True),("d",True),("f",True),("f",True),("s",True),
("d",True),("f",True)]
*Main> amalgamate it
[("aaa",False),("ssddddf",True),("aaa",False),("ffddsss",True),
("a",False),("dddssdffsdf",True)]
*Main> work it
["aaa","FDDDDSS","aaa","SSSDDFF","a","FDSFFDSSDDD"]
*Main> concat it
"aaaFDDDDSSaaaSSSDDFFaFDSFFDSSDDD"
*Main>