Частичное применение и сопоставление с образцом: почему эти Haskell функции ведут себя по-разному? - PullRequest
Новая
       41

Частичное применение и сопоставление с образцом: почему эти Haskell функции ведут себя по-разному?

7 голосов
/ 21 февраля 2020

Я пытаюсь понять кое-что о Haskell функциях.

Во-первых, вот функция Фибоначчи, определенная типичным «медленным» способом (то есть рекурсивным без запоминания и без трюков с бесконечным списком). ) 

slowfib :: Int -> Integer
slowfib 0 = 0
slowfib 1 = 1
slowfib n = slowfib (n-2) + slowfib (n-1)

Далее каноническая запоминающаяся версия того же самого. (Только немного отличается от типичных примеров в tutorals / books / et c, потому что я предпочитаю префиксную версию оператора !!.) 

memfib = (!!) (map fib [0..])
  where
    fib 0 = 0
    fib 1 = 1
    fib k = memfib(k-2) + memfib(k-1)

Приведенное выше решение использует частичное применение * 1010 Оператор *, который имеет смысл: мы хотим, чтобы memfib заканчивал как функция, которая принимает параметр, и мы определяем его без включения параметра в определение.

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

memfib_wparam n = ((!!) (map fib [0..])) n
  where
    fib 0 = 0
    fib 1 = 1
    fib k = memfib_wparam(k-2) + memfib_wparam(k-1)

(В терминах лямбда-исчисления memfib и memfib_wparams - это просто eta-преобразования друг друга. Я думаю ???)

Это работает, но запоминание пропало. На самом деле memfib_wparam ведет себя даже хуже, чем showfib: он не только медленнее, но и использует больше, чем вдвое.) 

*Main> slowfib 30
832040
(1.81 secs, 921,581,768 bytes)
*Main> memfib 30
832040
(0.00 secs, 76,624 bytes)
*Main> memfib_wparam 30
832040
(2.01 secs, 2,498,274,008 bytes)

Что здесь происходит? Что еще более важно, каково мое более широкое понимание ошибочных определений функций Haskell? Я предполагал, что синтаксис, который я использовал в memfib_wparam, был просто syntacti c sugar для того, что я делал в memfib, но, очевидно, это не так.

1 Ответ

5 голосов
/ 21 февраля 2020

Разница в том, когда ваша функция fib связана.

where -определения имеют доступ к параметрам внешней функции (т. Е. Параметры находятся «в области видимости» в пределах where). Это означает, что fib должен иметь доступ к n, что, в свою очередь, означает, что fib определено после того, как n пройдено, что означает, что он отличается fib для каждого n , это означает, что это разные вызовы map fib [0..] для каждого n.

Если вы хотите eta-расширить свой memfib, это будет «правильный» способ сделать это (то есть без излишне расширение области действия n): 

memfib = \n -> theCache !! n
    where
        theCache = map fib [0..]

        fib 0 = 0 
        fib 1 = 1 
        fib k = memfib(k-2) + memfib(k-1)

Если вы сравниваете с лямбда-исчислением, ключевое отличие состоит в том, что eta-сокращение / extension ничего не говорит о производительности, оно просто гарантирует, что Результат программы остается неизменным по логике. Что это делает.

...