Можно ли доказать, что позывной имеет минимальную асимптотическую временную сложность среди всех стратегий сокращения?

Ответ 1

Я думаю, что ваш вопрос немного смущен. Прошу пояснить несколько моментов.

Прежде всего указанная вами теорема традиционно известна как теорема стандартизации и принадлежит Карри и Фейсу (Комбинирующая логика I, 1958), обобщенная на eta-редукция Хиндли (Стандартное и нормальное сокращение), а затем пересмотрено многими другими авторами (см., например, question).

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

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

                                n 2 I I

где n и 2 - целые числа в церкви, а я - тождество. Я добавляю два я в конце, иначе слабые языки сократят вычисления слишком рано.

Заметим, что член сводится к

                          2 (2 (... (2 I))..) I

и (2 I) сводится к I. Итак, с самой внутренней редукцией вы могли бы уменьшить член в линейном времени w.r.t n.

С другой стороны, я приглашаю вас выполнить предыдущие вычисления в Haskell, и вы обнаружите, что время сокращения растет экспоненциально по n. Я оставляю вам понять причины этого явления.

Аналогичное обсуждение было сделано в этой нити.

Ответ 2

Конечно нет. Рассмотрим

f x y = sum [1..x] + y
g x = sum (map (f x) [1..x])

Сокращение по требованию g x будет выполнять дополнения O (x ^ 2), но на самом деле нужно только O (x). Например, ленивый HNF доставит нам эту сложность.

-- The definition f3 will get lazily refined.
let f3 y = f 3 y = sum [1,2,3] + y

g 3 = sum (map f3 [1,2,3])
    = sum [f3 1, f3 2, f3 3]

-- Now let refine f3 to HNF *before* applying it
f3 y = sum [1,2,3] + y
     = 6 + y

-- And continue g 3
g 3 = sum [f3 1, f3 2, f3 3]
    -- no need to compute sum [1..x] three times
    = sum [6 + 1, 6 + 2, 6 + 3]
    = ...

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

Подробнее об этом см. Michael Jonathan Thyer Lazy Specialization.