Функция, использующая Foldr, слишком активна - PullRequest
Новая
       6

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

10 голосов
/ 07 ноября 2011

У меня есть небольшая альтернативная реализация 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.Вызывает ли такое поведение совпадение шаблонов?

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

Ответы [ 3 ]

14 голосов
/ 07 ноября 2011

Ключевая проблема в том, что вы знаете, что 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
4 голосов
/ 07 ноября 2011

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

1 голос
/ 07 ноября 2011

Мне трудно понять, что будет делать ваш код, когда 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 xs@(x' : xs')
      | x `f` x' = (x : hd', tl')
      | otherwise = ([x], hd' : tl')
      where
        (hd', tl') = go x' xs'
...