Преобразовать рекурсивную функцию в хвостовую рекурсивную функцию.Концепция хвостовой рекурсии - PullRequest
Новая
       20

Преобразовать рекурсивную функцию в хвостовую рекурсивную функцию.Концепция хвостовой рекурсии

0 голосов
/ 25 апреля 2019

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

h x = if x > 20 then 50 else x*x + h (x+1)

1 Ответ

3 голосов
/ 25 апреля 2019

Как говорит Робин Зигмонд, концепция хвостовой рекурсии не применяется в Haskell так же, как в неленивых языках.В языках с семантикой non-lazy (т.е. не с Haskell), что вы можете сделать для достижения хвостовой рекурсии, это переместить выражение, которое вызывает использование стека, в накапливающийся аргумент, например: 

h :: Int -> Int
h x = if x > 20 then 50 else x*x + h (x+1)

g :: Int -> Int
g z = g' z 50 where
  g' x y
    | x > 20 = y
    | otherwise = g' (x+1) (x*x + y)

Здесь внешнее выражение тела функции g' - это вызов самого себя, поэтому, если бы это был не ленивый язык, вам не нужно было бы сохранять кадры стека старых рекурсивных вызовов перед разрешением x*x + ...часть выражения.В Haskell это оценивается по-разному.

Сравнивая h и этот g в микропроцессоре, 

module Main where

import Criterion
import Criterion.Main

main :: IO ()
main = defaultMain [ bgroup "tail-recursion" [ bench "h" $ nf h 1
                                             , bench "g" $ nf g 1
                                             ]
                   ]

вы на самом деле получаете худшую производительность от этого g':

benchmarking tail-recursion/h
time                 826.7 ns   (819.1 ns .. 834.7 ns)
                     0.993 R²   (0.988 R² .. 0.997 R²)
mean                 911.1 ns   (866.4 ns .. 971.9 ns)
std dev              197.7 ns   (149.3 ns .. 241.3 ns)

benchmarking tail-recursion/g
time                 1.742 μs   (1.730 μs .. 1.752 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 1.742 μs   (1.729 μs .. 1.758 μs)
std dev              47.44 ns   (34.69 ns .. 66.29 ns)

Вы можете вернуть часть производительности, сделав аргументы g' строгого, 

{-# LANGUAGE BangPatterns #-}

g2 :: Int -> Int
g2 z = g' z 50 where
  g' !x !y
    | x > 20 = y
    | otherwise = g' (x+1) (x*x + y)

, но он выглядит и работает хуже, чем исходный h:

benchmarking tail-recursion/g2
time                 1.340 μs   (1.333 μs .. 1.349 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 1.344 μs   (1.336 μs .. 1.355 μs)
std dev              33.40 ns   (24.71 ns .. 48.94 ns)

Редактировать: Как указал К. А. Бур, я забыл флаг -O2 для GHC;выполнение этого обеспечивает следующие результаты микро-бенчмарка: 

h  time: 54.27 ns   (48.05 ns .. 61.24 ns)
g  time: 24.50 ns   (21.15 ns .. 27.35 ns)
g2 time: 25.47 ns   (22.19 ns .. 29.06 ns)

в этот момент версия с накапливающимся аргументом работает лучше, а версия BangPatterns работает также хорошо, но оба выглядят хуже, чем оригинал.

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

...