Может ли последовательность по infinte Maybes когда-либо прекратить?

Question

Другими словами, можно ли оптимизировать следующее Just [1..]?

> sequence (map Just [1..])
*** Exception: stack overflow

Существует также более конкретный пример в data61/fp-course где досрочное прекращение ожидается, если Empty значение присутствует.

seqOptional ::
  List (Optional a)
  -> Optional (List a)
seqOptional =
    foldRight f (Full Nil)
      where
          f Empty _ = Empty
          f _ Empty = Empty
          f (Full a) (Full as) = Full (a :. as)

Почему изменение порядка первых двух шаблонов делает цикл функции вечным, как если бы Empty не может быть сопоставлен? Я смутно понимаю, что такое определение сделает f строг в бесконечном списке, но я не вижу, что на самом деле вызывает это.

Или это не связанные проблемы?

Дополнительный вопрос: имеет ли значение, что стек исчерпан, а не куча?

Answer 1

Даже если бы мог, не должен. Как и в комментарии @user2407038, согласно денотационной семантике Хаскелла, sequence (map Just [1..]) обозначает другое значение, чем Just [1..],

Функции Haskell являются непрерывными, что является ключевым инструментом для точных рассуждений о бесконечных структурах данных. Чтобы проиллюстрировать, что означает непрерывность, предположим, что у нас есть бесконечная последовательность значений, которые все чаще определяются, например:

⟂
1:⟂
1:2:⟂
1:2:3:⟂

Теперь примените функцию к каждому из них, скажем, tail:

tail ⟂             = ⟂
tail (1:⟂)         = ⟂
tail (1:2:⟂)       = 2:⟂
tail (1:2:3:⟂)     = 2:3:⟂
     ⋮                 ⋮
tail [1..]         = [2..]

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

Теперь некоторые замечания о sequence в частично определенных списках:

-- a ⟂ after a bunch of Justs makes the result ⟂
sequence (Just 1 : Just 2 : ⟂) = ⟂
-- a Nothing anywhere before the ⟂ ignores the ⟂ (early termination)
sequence (Just 1 : Nothing : ⟂) = Nothing

Нам нужно только первое наблюдение. Теперь мы можем задать ваш вопрос:

sequence (map Just ⟂)       = sequence ⟂                     = ⟂
sequence (map Just (1:⟂))   = sequence (Just 1 : ⟂)          = ⟂
sequence (map Just (1:2:⟂)) = sequence (Just 1 : Just 2 : ⟂) = ⟂
          ⋮                                   ⋮                 ⋮
sequence (map Just [1..])                                    = ⟂

Так что по преемственности, sequence (map Just [1..]) = ⟂, Если вы "оптимизировали" его, чтобы дать другой ответ, эта оптимизация была бы неправильной.

Answer 2

Я не могу ответить на ваш второй вопрос, но могу ответить на ваш первый.

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