Чистый синтаксис для условного сворачивания списка в Haskell

Прежде всего,

foldrOn :: Num t => (a -> Bool) -> [a] -> [(a, t)]
-- foldrOn (== 0) [1,0,0,0,0,0,1,0,0,0,1] -- [(1,0),(1,5),(1,3)]
foldrOn p xs  =  foldr g [] xs
  where
  g x []        = [(x,0)]
  g x ((y,n):r)
    | p x       = ((y,n+1):r)
  g x r         = ((x,0):r)

Это самое простое, хотя и рекурсивное, т.е. заставит весь список дойти до конца, прежде чем начать возвращать его результат.

Чтобы сделать его максимально ленивым, нам пришлось бы использовать ленивый левый сгиб. Пропуск p-удовлетворяющих элементов по-прежнему является рекурсивным шагом, но, по крайней мере, процесс будет останавливаться между каждым таким интервалом.

Ленивая левая складка обычно реализуется как foldr с дополнительным аргументом, передаваемым слева направо по списку:

foldlOn :: Num t => (a -> Bool) -> [a] -> [(a, t)]
-- foldlOn (== 0) [1,0,0,0,0,0,1,0,0,0,1] -- [(1,0),(1,5),(1,3)]
foldlOn p xs  =  foldr g z xs 0
  where
  g x r i | p x       =         r (i+1)
          | otherwise = (x,i) : r 0
  z    _i             =         []

Или вы можете объединить span/break и unfoldr, чтобы сделать то же самое.

Вы можете найти способ использовать groupBy с некоторой последующей обработкой:

GHCi> groupBy (\a b -> (==0) b) [1,0,0,0,0,0,1,0,0,0,1]
[[1,0,0,0,0,0],[1,0,0,0],[1]]

GHCi> groupBy (const (==0)) [1,2,0,0,1,0,1]
[[1],[2,0,0],[1,0],[1]]

Закончить это не должно быть проблемой.

Вы всегда можете привезти встроенную технику. Библиотека Data.List довольно мощная:

import Data.List(mapAccumL)
import Data.Maybe(catMaybes)

foldrOn cond = catMaybes . snd . mapAccumL combine 0 where
  combine a el =
    if cond el then (a + 1, Nothing)
    else (0, Just (el, a))

Что происходит

По сути, foldrOn cond представляет собой композицию следующих функций:

• mapAccumL combine 0, который продвигается по списку, изменяя каждый элемент информацией о количестве недавно пропущенных объектов (начиная отсчет с 0 и сбрасывая его всякий раз, когда мы находим что-то, что не соответствует предикату cond).
• snd который отбрасывает конечное состояние из результата mapAccumL
• catMaybes, который удаляет слой Maybe и оставляет только «настоящие» значения.

Давайте начнем с использования сопоставления с образцом, чтобы сделать вашу собственную реализацию более идиоматической, более очевидно правильной, а также (намного) более быстрой. Мы также можем использовать охранников идиоматически, а не if/then/else; это скорее менее важно. Здесь также нет причин использовать do, поэтому мы не будем.

foldrOn _cond [] = []
foldrOn cond (hd : tl)
  | cond hd
  = case foldrOn cond tl of
      (x, y) : tl' -> (x, y + 1) : tl' 
                      -- fold token into char after it
      [] -> error "String ended on token."
  | otherwise
  = (hd, 0) : foldrOn cond tl
                      -- don't fold token

Это нормально. Но, как предполагает Уилл Несс, мы на самом деле ничего не выигрываем, добавляя «неполный» элемент в список результатов. Вместо этого мы можем подсчитывать cond-удовлетворяющие токены, пока не достигнем конца блока, а затем создать полный элемент. Я думаю, что это делает код немного более понятным, и он также должен работать немного быстрее.

foldrOn cond = go 0
  where
    go count (hd : tl)
      | cond hd
      = go (count + 1) tl -- Don't produce anything; just bump the count
      | otherwise
      = (hd, count) : go 0 tl -- Produce the element and the count; reset the count to 0
    go count []
      | count == 0
      = []
      | otherwise
      = error "List ended on a token."

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

-- At the top of the file, add this line:
{-# LANGUAGE BangPatterns #-}

foldrOn cond = go 0
  where
    go !count (hd : tl)
      | cond hd
      = go (count + 1) tl -- Don't produce anything; just bump the count
      | otherwise
      = (hd, count) : go 0 tl -- Produce the element and the count; reset the count to 0
    go count []
      | count == 0
      = []
      | otherwise
      = error "List ended on a token."

Это можно записать как складку, как это демонстрирует Уилл Несс.

Примечание: хотя можно избежать языкового расширения BangPatterns, это немного раздражает.