Функция, использующая foldr, слишком нетерпелив

У меня есть небольшая альтернативная реализация groupBy, которая более полезна для меня, чем версия в Data.List, потому что это не требует, чтобы тест был отношением эквивалентности:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' f = foldr step []
    where step x [] = [[x]]
          step x (xs:xss)
              | x `f` head xs = (x:xs):xss
              | otherwise     = [x]:xs:xss

Однако он слишком нетерпелив и не начнет вычислять входные данные, такие как groupBy' (<) [1,2,3,2,3,4,1,undefined]. Я прочитал HaskellWiki и Wikibooks статьи которые объясняют, почему некоторые вещи, такие как совпадения с образцами, могут сделать функции менее ленивыми, и я думаю, что понимаю большинство приведенных здесь примеров. Тем не менее, я не понимаю, почему эта функция не может начать производить вывод до тех пор, пока он не достигнет значения undefined. Соответствуют ли шаблону такое поведение?

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

Ответ 1

Основная проблема заключается в том, что вы знаете, что step x xss всегда будет производить результат формы (x:_):_, но вы "скрываете" это за совпадением шаблона, поэтому Haskell вынужден сначала оценить их, чтобы определить, какой случай из step выбрать, прежде чем он даже увидит эти конструкторы.

В общем случае для foldr f x, чтобы иметь возможность производить какой-либо вывод до достижения конца списка, f должен иметь возможность выводить некоторый результат перед рассмотрением его второго аргумента.

Мы можем исправить это, разделив step на два, чтобы мы могли создать два конструктора (:), прежде чем выполнять сопоставление шаблонов во втором аргументе.

groupBy' f = foldr step []
  where step x xss = let (ys, yss) = step' x xss in (x:ys):yss
        step' x [] = ([], [])
        step' x (xs:xss) | f x (head xs) = (xs, xss)
                         | otherwise     = ([], xs:xss)

Это примерно так же лениво, как вы можете его получить.

*Main> groupBy' (<) [1, 2, 3, 2, 3, 4, 1, undefined]
[[1,2,3],[2,3,4],[1*** Exception: Prelude.undefined

Ответ 2

foldr step [] [1,2,3,...] будет расширяться до step 1 (foldr step [] [2,3]). Теперь step нужно решить, идти ли в первом случае или во втором. Для этого ему нужно знать, оценивает ли foldr step [] [2,3,...] пустой список. Для этого ему нужно знать, возвращает ли step 2 (foldr step [] [3,...]) пустой список (чего никогда не будет, но Haskell этого не знает). Это продолжается до тех пор, пока не будет достигнут конец списка (и если список не имеет конца, он продолжается вечно).

Ответ 3

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

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' f [] = []
groupBy' f [x] = [[x]]
groupBy' f (x : xs)
  | x `f` head xs = (x : head l) : tail l
  | otherwise = [x] : l
  where
    l = groupBy' f xs

или эквивалентно без использования head или tail:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' f [] = []
groupBy' f (x : xs) = hd : tl
  where
    (hd, tl) = go x xs
    go x [] = ([x], [])
    go x [email protected](x' : xs')
      | x `f` x' = (x : hd', tl')
      | otherwise = ([x], hd' : tl')
      where
        (hd', tl') = go x' xs'