Удалить элементы n-1, n и n + 1 на основе условия для n в списке Haskell

Question

Так сказать, у меня есть список всех целых чисел от 2 до 20.

[2 .. 20] 

Я хочу, чтобы фильтровать по списку с помощью функции f x (или это предикат? Я не очень привык ко всем терминов, используемых в программировании на Haskell). Если элемент в позиции n равен true для этой функции f, я хочу удалить элементы в положениях n-1, n и n+1.

Пример: Допустим, что элемент в положении 4 в списке [2 .. 20], что составляет 6, равно верно и для функции f. Затем я хочу удалить элементы в позиции 3, 4 и 5, которые равны 5, 6 и 7 соответственно. Так что мой окончательный список будет выглядеть так:

[2,3,4,8,9,10,11,12,13,14,15,16,17,18,19,20] 

Я неопытный Haskell программист, просто играл для удовольствия. Я думал об использовании лямбда-функции в качестве предиката, но я не совсем уверен, как это сделать. Я также думал об использовании функции, такой как remove xs ys, которая удаляет все элементы в xs, что также является элементом ys, но я не уверен, как это сделать.

Любая помощь будет оценена!

EDIT: Я понял, что удаление обоих смежных элементов неверно, чтобы получить результат, который я хотел. Кроме того, может быть лучше просто изменить значение затронутых элементов (элементы в позициях n и n-1) до 0 или пометить их каким-либо другим способом, а не удалять их целиком. Причиной этого является то, что я хочу сохранить «удаление» элементов до тех пор, пока в списке больше не будет элементов, которые соответствуют предикату (и их предшествующим элементам). Я только хочу «удалить» их из Исходный список. Поскольку мой подход сильно изменился с первоначального вопроса, я отправлю новый, чтобы отразить мой новый подход. Я хочу поблагодарить вас за все ответы, и я многому научился из ваших ответов. Спасибо!

EDIT 2: Вот мой новый вопрос: Remove elements at positions n and n-1 in a Haskell list, when n fits a predicate

Answer 1

Вы можете просто шаблон матч на нескольких элементах и ​​применить фильтр к среднему.

eitherside :: (Int->Bool) -> [Int] -> [Int] 
eitherside f (i1:i2:i3:is) = if (f i2) 
    then eitherside f is 
    else i1 : (eitherside f (i2:i3:is)) 
eitherside f is = is 
*Main> eitherside (==4) [1..10] 
[1,2,6,7,8,9,10] 
*Main> eitherside (==5) [1..10] 
[1,2,3,7,8,9,10] 
*Main> eitherside (==6) [1..10] 
[1,2,3,4,8,9,10] 

не нравится это (мой оригинальный пост):

eitherside :: (Int->Bool) -> [Int] -> [Int] 
eitherside f (i1:i2:i3:is) = if (f i2) 
    then eitherside f is 
    else [i1,i2,i3] ++ (eitherside f is) 
eitherside f is = is 
*Main> eitherside (==5) [1..10] 
[1,2,3,7,8,9,10] 

Это плохо один случился работать на 5, но терпит неудачу за 6 потому что я пропущу его в «другой» отрасли.

Answer 2

Вот один подход, хотя я уверен, что есть более элегантные способы.

Подход состоит в том, чтобы сначала отобразить наш список [a] в список троек [(Maybe a, a, Maybe a)]. (Maybe вступает в игру, потому что в первом и последнем элементах отсутствует предшественник/преемник соответственно.)

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

preprocess :: [a] -> [(Maybe a, a, Maybe a)] 
preprocess xs = zip3 (beforeXs xs) xs (afterXs xs) 

beforeXs :: [a] -> [Maybe a] 
beforeXs xs = Nothing : (map Just xs) 

afterXs :: [a] -> [Maybe a] 
afterXs xs = concat [(map Just (tail xs)), [Nothing]] 

middle3 :: (a, b, c) -> b 
middle3 (_,x,_) = x 

myfilter :: (a -> Bool) -> [a] -> [a] 
myfilter f xs = map middle3 $ filter (not . adjacentF) (preprocess xs) 
    where 
     maybeF = maybe False f 
     adjacentF (x,y,z) = (maybeF x) || (f y) || (maybeF z) 

Это должно дать желаемые результаты в целом:

*Main> myfilter (==20) [1..20] 
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] 
*Main> myfilter (==1) [1..20] 
[3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] 
*Main> myfilter (==5) [1..20] 
[1,2,3,7,8,9,10,11,12,13,14,15,16,17,18,19,20] 
*Main> myfilter (\x -> x >= 12 && x <= 14) [1..20] 
[1,2,3,4,5,6,7,8,9,10,16,17,18,19,20] 
*Main> myfilter even [1..20] 
[] 

Answer 3

Мое решение, используя немного доморощенного реализацию списка молния:

-- List zipper (think of this as a standard library routine): 
data LZ a = LZ [a] a [a] deriving (Show) 

listToLZ :: [a] -> LZ a 
listToLZ (h:t) = LZ [] h t 

lzToList :: LZ a -> [a] 
lzToList (LZ l p r) = reverse l ++ p:r 

moveRight, remLeft, remRight, remHere :: LZ a -> LZ a 
moveRight (LZ l t (t':r)) = LZ (t:l) t' r 
remLeft (LZ l p r) = LZ (tail l) p r 
remRight (LZ l p r) = LZ l p (tail r) 
remHere (LZ l _ (p:r)) = LZ l p r 

-- And there's how one use this: 
-- <business code> 
traverse :: (a -> Bool) -> LZ a -> LZ a 
traverse _ a@(LZ _ _ []) = a 
traverse pr a@(LZ _ p _) 
    | pr p = traverse pr $ remHere $ remRight $ remLeft a 
    | True = traverse pr $ moveRight a 
-- </business code> 

main = let 
    l = [1..20] 
    l' = lzToList $ traverse (==4) $ listToLZ l 
in 
    print l' 

Выход:

[1,2,6,7,8,9,10,11,12,13,14,15 , 16,17,18,19,20]

Answer 4

Вот решение, которое получает Джобе сделано, хотя, возможно, не является наиболее эффективным:

f p l = map snd $ filter (flip notElem indices . fst) l' 
    where 
    indices = concat [[i - 1, i, i + 1] | (i, _) <- filter (p . snd) l'] 
    l' = zip [0..] l 

Или немного короче, используя findIndices из Data.List:

f p l = map snd $ filter (flip notElem indices . fst) $ zip [0..] l 
    where indices = concat [[i - 1, i, i + 1] | i <- findIndices p l] 

Тестирование:

*Main> f (\x -> x == 6 || x == 7) [2..20] 
[2,3,4,9,10,11,12,13,14,15,16,17,18,19,20] 

Answer 5

Вы можете перенести эту проблему и посмотреть на условия, при которых сохраняется элемент: который является что элемент в положении n сохраняется, если предикат False в положениях n-1, n a nd n+1.

Это указывает на следующий подход:

keep3 :: (a -> Bool) -> [a] -> [a] 
keep3 f xs = go xs bs 
    where b0 = map f xs 
     b1 = (tail b0) ++ [False] 
     b2 = False : b0 
     bs = zipWith (||) (zipWith (||) b0 b1) b2 
     go [] _ = [] 
     go (x:xs) (b:bs) = if (not b) then x : go xs bs else go xs bs 

Некоторые пояснительные точки:

• b0 представляет собой список, имеющие такую ​​же длину, что и список элементов которого п-ое значение является значением предиката, оцененного на n-м элементе списка.
• b1 такое же, как b0, но сдвинутое налево; поэтому его n-е значение является предикатом, оцененным на n+1-м элементе в списке
• b2 - это то же самое, что и b0, но сдвинуто вправо; поэтому его н-ое значение есть предикат оценивается на n-1 -го элемента списка
• bs является логическим или из списков b0, b1, b2 сделаны поэлементно и поэтому список булевых те же длины как xs. N-й элемент bs определяет, должен ли поддерживаться n-й элемент xs.
• Обратите внимание, что предикат оценивается только один раз для каждого элемента списка xs. Также я думаю, что граничные случаи обрабатываются правильно.

Answer 6

Один из способов приблизиться к этому - уловить идею окрестности элемента в списке.

-- A neighborhood of a point in a list 
data Neighborhood a = Neighborhood { 
    predecessors :: ![a], 
    point :: !a, 
    successors :: ![a] 
} deriving Show 

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

-- On long lists or infinite stream, this will leak memory (it keeps all the predecessors in memory) 
neighborhoods :: [a] -> [Neighborhood a] 
neighborhoods = neighborhoods' [] 
    where 
     neighborhoods' _ [] = [] 
     neighborhoods' ps (x:ss) = (Neighborhood ps x ss):(neighborhoods' (x:ps) ss) 

Эти районы будут включать в себя все предшественники и преемники каждого элемента списка. Удобно будет учесть меньшую окрестность within небольшой радиус каждой окрестности. Также будет удобно иметь enumerate окрестности. (Определение interleave находится ниже, он посещает списки в чередующемся порядке.)

within :: Int -> Neighborhood a -> Neighborhood a 
within r n = Neighborhood (take r . predecessors $ n) (point n) (take r . successors $ n) 

enumerate :: Neighborhood a -> [a] 
enumerate n = (point n):(interleave (successors n) (predecessors n)) 

Теперь мы можем легко спросить за то, что мы хотим - те элементы, окрестность радиуса 1 не содержит недопустимую величину. (pows и log2 определены ниже /)

main = do 
    let disallowed = \x -> x == pow2s !! log2 x 
    print . map point . filter (not . any disallowed . enumerate . within 1) . neighborhoods $ [2..20] 

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

neighborhoodsRadius n = map (within n) . neighborhoods 

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

Вот полный код работает:

module Main (
    pow2s, 
    log2, 
    main, 

    interleave, 
    Neighborhood (..), 
    within, 
    enumerate, 
    neighborhoods, 
    neighborhoodsRadius, 
) where 

import qualified Data.Sequence as Seq 
import Data.Sequence ((<|)) 
import Data.Foldable (toList) 

-- Interleave lists 
interleave :: [a] -> [a] -> [a] 
interleave [] ys = ys 
interleave (x:xs) ys = x:(interleave ys xs) 


-- A neighborhood of a point in a list 
data Neighborhood a = Neighborhood { 
    predecessors :: ![a], 
    point :: !a, 
    successors :: ![a] 
} deriving Show 

within :: Int -> Neighborhood a -> Neighborhood a 
within r n = Neighborhood (take r . predecessors $ n) (point n) (take r . successors $ n) 

enumerate :: Neighborhood a -> [a] 
enumerate n = (point n):(interleave (successors n) (predecessors n)) 

-- On long lists or infinite stream, this will leak memory (it keeps all the predecessors in memory) 
neighborhoods :: [a] -> [Neighborhood a] 
neighborhoods = neighborhoods' [] 
    where 
     neighborhoods' _ [] = [] 
     neighborhoods' ps (x:ss) = (Neighborhood ps x ss):(neighborhoods' (x:ps) ss) 

-- This is better on long lists or infinite stream as it will cull the predecessors before recursing 
neighborhoodsRadius :: Int -> [a] -> [Neighborhood a] 
neighborhoodsRadius radius = neighborhoods' Seq.empty 
    where 
     neighborhoods' _ [] = [] 
     neighborhoods' ps (x:ss) = 
      (Neighborhood (toList radiusPs) x radiusSs):(neighborhoods' (x <| radiusPs) ss) 
       where 
        radiusPs = Seq.take radius ps 
        radiusSs = take radius ss 

-- example 
pow2s = iterate (*2) 1 
log2 n = length . takeWhile (< n) $ pow2s 

main :: IO() 
main = do 
    let disallowed = \x -> x == pow2s !! log2 x 
    print . map point . filter (not . any disallowed . enumerate . within 1) . neighborhoods $ [2..20] 
    getLine 
    let steps = map (print . point) . filter (not . any disallowed . enumerate) . neighborhoodsRadius 1 $ [2..] 
    sequence_ steps