Проблема стиля программирования Haskell CPS

вот функция умножает элементы в списке, используя стиль CPS

mlist xx k = aux xx k
  where aux [] nk = nk 1
    aux (0:xs) nk = k 0
    aux (x:xs) nk = aux xs $ \v -> mul x v nk

что, если я заменю 'k' на 'nk' в выражении aux (0:xs) nk = k 0, какая разница между ними?


person Rn2dy    schedule 09.07.2010    source источник


Ответы (2)


k всегда является исходным продолжением, переданным mlist, тогда как для списка [1, 0] nk в этом случае будет \v -> mul 1 v k (из третьего случая aux).

Если мы предположим, что mul определяется как mul x y k = k $ x*y, это не имеет практического значения, поскольку y всегда будет равно 0. Но фактический метод получения этого результата отличается (за исключением возможных оптимизаций компилятором).

person Chuck    schedule 09.07.2010
comment
IME, использующий k вместо передачи нового продолжения, часто позволяет значительно оптимизировать компилятор. Я еще не видел случая, когда использование 'k' было бы, по крайней мере, не столь эффективным, как 'nk', а зачастую и заметно быстрее. - person John L; 09.07.2010

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

person BMeph    schedule 09.07.2010