Есть ли прямое решение для получения элемента * до * попадания в предикат dropWhile?

Question

Учитывая условие, я хочу просмотреть список элементов и вернуть первый элемент, который достигает условия, и предыдущий.

В C / C ++ это легко:

int i = 0;
for(;;i++) if (arr[i] == 0) break;

После того, как мы получим индекс, где выполняется условие, легко получить предыдущий элемент через "arr[i-1]"

В Хаскеле:

• dropWhile (/=0) list дает нам последний элемент, который я хочу

• takeWhile (/=0) list дает нам первый элемент, который я хочу

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

Answer 1

Я бы сжал список с хвостом, чтобы у вас были пары элементов имеется в наличии. Тогда вы можете просто использовать find в списке пар:

f :: [Int] -> Maybe (Int, Int)
f xs = find ((>3) . snd) (zip xs (tail xs))

> f [1..10]
Just (3,4)

Если элемент first соответствует предикату, он вернется Nothing (или второе совпадение, если оно есть), поэтому вам может понадобиться специальный случай, если вы хотите что-то отличается.

Как говорит Робин Зигмонд, break также может работать:

g :: [Int] -> (Int, Int)
g xs = case break (>3) xs of (_, []) -> error "not found"
                             ([], _) -> error "first element"
                             (ys, z:_) -> (last ys, z)

(Или это возвращение также Maybe, в зависимости от того, что вам нужно.)

Но это, я думаю, сохранит весь префикс ys в памяти до находит совпадение, тогда как f может начать сборку мусора оно прошло мимо. Для небольших списков это не имеет значения.

Answer 2

Я бы использовал поиск по типу молнии:

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

toZipperList :: [a] -> ZipperList a
toZipperList = (,) []

moveUntil' :: (a -> Bool) -> ZipperList a -> ZipperList a
moveUntil' _ (xs, []) = (xs, [])
moveUntil' f (xs, (y:ys))
    | f y       = (xs, (y:ys))
    | otherwise = moveUntil' f (y:xs, ys)

moveUntil :: (a -> Bool) -> [a] -> ZipperList a
moveUntil f = moveUntil' f . toZipperList

example :: [Int]
example = [2,3,5,7,11,13,17,19]

result :: ZipperList Int
result = moveUntil (>10) example -- ([7,5,3,2], [11,13,17,19])

Хорошая особенность застежек-молний состоит в том, что они эффективны, вы можете получить доступ к как можно большему количеству элементов рядом с указателем и перемещать фокус молнии вперед и назад. Узнайте больше о молнии здесь:

http://learnyouahaskell.com/zippers

Обратите внимание, что моя moveUntil функция похожа на break из Prelude, но начальная часть списка перевернута. Следовательно, вы можете просто получить head обоих списков.

Answer 3

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

-- The extra [a] argument f takes with respect to foldr
-- is the tail of the list at each step of the fold.  
foldrWithTails :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldrWithTails f n = go
    where
    go (a : as) = f a as (go as)
    go [] = n

boundary :: (a -> Bool) -> [a] -> Maybe (a, a)
boundary p = foldrWithTails findBoundary Nothing
    where
    findBoundary x (y : _) bnd
        | p y = Just (x, y)
        | otherwise = bnd
    findBoundary _ [] _ = Nothing

Примечания:

• Еслиp y верно, нам не нужно смотреть на bnd, чтобы получить результат.Это делает решение адекватно ленивым.Вы можете проверить это, опробовав boundary (> 1000000) [0..] в GHCi.

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

  GHCi> boundary (<1) [0..9]
  Nothing
  GHCi> boundary even [0..9]
  Just (1,2)
  

Answer 4

Есть несколько альтернатив; в любом случае, вам придется реализовать это самостоятельно. Вы можете использовать явную рекурсию:

getLastAndFirst :: (a -> Bool) -> [a] -> Maybe (a, a)
getLastAndFirst p (x : xs@(y:ys))
    | p y = Just (x, y)
    | otherwise = getLastAndFirst p xs
getLastAndFirst _ [] = Nothing

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

Третий вариант - использовать break, как предлагается в комментариях:

getLastAndFirst' :: (a -> Bool) -> [a] -> Maybe (a,a)
getLastAndFirst' p l =
    case break p l of
        (xs@(_:_), (y:_)) -> Just (last xs, y)
        _ -> Nothing

Answer 5

(\(xs, ys) -> [last xs, head ys]) $ break (==0) list

Использование break, как предложил Робин Зигмонд, оказалось коротким и простым, без использования Maybe для отлова краевых случаев, но я мог бы заменить лямбду простой функцией, которая использовала Maybe.

---

Я немного поиграл с решением и придумал

breakAround :: Int -> Int -> (a -> Bool) -> [a] -> [a]
breakAround m n cond list = (\(xs, ys) -> (reverse (reverse take m (reverse xs))) ++ take n ys) $ break (cond) list

, который принимает два целых числа, предикат и список a и возвращает один список m элементов до предиката и n элементов после.

Пример: breakAround 3 2 (==0) [3,2,1,0,10,20,30] вернет [3,2,1,0,10]