Переполнение стека при сворачивании бесконечных списков? - PullRequest
Новая
       53

Переполнение стека при сворачивании бесконечных списков?

8 голосов
/ 16 июня 2019

Рассмотрим следующую функцию: 

(<.>) :: [[a]] -> [[a]] -> [[a]]
xs <.> ys = zipWith (++) xs ys

Это, по сути, берет два двумерных массива a с и объединяет их слева направо, например ::100100 

[[1,2],[3,4]] <.> [[1,2],[3,4]] == [[1,2,1,2],[3,4,3,4]]

Я бы хотел написать что-то вроде следующего: 

x = foldr1 (<.>) $ repeat [[1,2],[3,4]]

Что должно иметь смысл из-за ленивой оценки Хаскелла, то есть мы должны получить: 

x !! 0 == [1,2,1,2,1,2,1,2...]
x !! 1 == [3,4,3,4,3,4,3,4...]

Однако, когда я пытаюсь запустить этот пример с GHCi, используя либо foldr1, либо foldl1, я либо получаю бесконечное вычисление, либо переполнение стека.

Итак, мой вопрос:

  1. Что здесь происходит?
  2. Можно ли сделать то, что я пытаюсь сделать, с помощью какой-либо функции, отличной от foldr1 или foldl1? (Я рад, если мне нужно изменить реализацию <.>, если она вычисляет ту же функцию)

Также обратите внимание: я знаю, что для этого примера map repeat [[1,2],[3,4]] производит желаемый вывод, но я ищу решение, которое работает для произвольных бесконечных списков, а не только для форм repeat xs.

Ответы [ 2 ]

8 голосов
/ 16 июня 2019

Я подробно остановлюсь на том, что было сказано в комментариях здесь.Я собираюсь позаимствовать (упрощенную версию) версию GHC zipWith, которой должно быть достаточно для этого обсуждения. 

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

Теперь вот чтовычисления в конечном итоге выглядят как в великолепной бесконечной форме. 

[[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

Хорошо, поэтому верхний уровень - <.>.Хорошо.Давайте подробнее рассмотрим это. 

zipWith (++) [[1, 2], [3, 4]] ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

Все еще нет проблем.Теперь мы рассмотрим шаблоны для zipWith.Первый шаблон соответствует, только если левая сторона пуста.Welp, это определенно не правда, так что давайте двигаться дальше.Второе совпадение только в том случае, если правая сторона пуста.Итак, давайте посмотрим, если правая сторона пуста.Правая сторона выглядит так: 

[[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

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

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

-- (I'm also changing the name so we don't conflict with the Prelude version)
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

(<.>) :: [[a]] -> [[a]] -> [[a]]
xs <.> ys = zipWith' (++) xs ys

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

Если бы был способ сопоставления с шаблоном без необходимости обращаться к WHNF... введите ленивые узоры .Давайте перепишем нашу функцию следующим образом. 

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f ~(x:xs) ~(y:ys) = f x y : zipWith' f xs ys

Теперь наша функция определенно прекратит работу, если получить конечный список.Но это позволяет нам «делать вид» совпадения с образцом в списках, фактически не выполняя никакой работы.Это эквивалентно более многословному 

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f xs ys = f (head xs) (head ys) : zipWith' f (tail xs) (tail ys)

И теперь мы можем правильно протестировать вашу функцию. 

*Main> let x = foldr1 (<.>) $ repeat [[1, 2], [3, 4]]
*Main> x !! 0
[1,2,1,2,1,2,1,2,1,...]
*Main> x !! 1
[3,4,3,4,3,4,3,4,3,...]

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

*Main> [[1, 2], [3, 4]] <.> [[1, 2], [3, 4]]
[[1,2,1,2],[3,4,3,4],*** Exception: Prelude.head: empty list
5 голосов
/ 16 июня 2019

zipWith не является - фактически, это не может быть - настолько ленивым, как вы хотели бы. Рассмотрим этот вариант на вашем примере: 

GHCi> foldr1 (zipWith (++)) [ [[1,2],[3,4]], [] ]
[]

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

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

GHCi> import qualified Data.List.NonEmpty as N
GHCi> import Data.List.NonEmpty (NonEmpty(..))
GHCi> take 10 . N.head $ foldr1 (N.zipWith (++)) $ repeat ([1,2] :| [[3,4]])
[1,2,1,2,1,2,1,2,1,2]

N.zipWith не нужно иметь дело с пустым списком , поэтому он может быть ленивее.

...