распознавание хвостовой рекурсии

Question

Я пытаюсь выучить Хаскель и наткнулся на следующее:

myAdd (x:xs) = x + myAdd xs
myAdd null = 0

f = let n = 10000000 in myAdd [1 .. n]

main = do
 putStrLn (show f)

При компиляции с GHC это приводит к переполнению стека. Как программист C / C ++, я бы ожидал, что компилятор выполнит оптимизацию хвостового вызова.

Мне не нравится, что мне придется «помогать» компилятору в таких простых случаях, как эти, но какие есть варианты? Я думаю, что разумно потребовать, чтобы приведенные выше вычисления были выполнены без использования O (n) памяти и без использования специализированных функций.

Если я не могу сформулировать свою проблему естественным образом (даже в случае с игрушкой, такой как эта) и ожидать разумной производительности с точки зрения времени и пространства, большая часть привлекательности Haskell будет потеряна.

Answer 1

Во-первых, убедитесь, что вы компилируете с -O2. Это делает многие проблемы с производительностью просто исчезают:)

Первая проблема, которую я вижу, это то, что null - это просто имя переменной. Вы хотите []. Здесь это эквивалентно, потому что единственными вариантами являются x:xs и [], но это не всегда будет.

Проблема здесь проста: когда вы звоните sum [1,2,3,4], это выглядит так:

1 + (2 + (3 + (4 + 0)))

, не сводя ни одного из этих дополнений к числу , из-за нестрогой семантики Haskell. Решение простое:

myAdd = myAdd' 0
  where myAdd' !total [] = total
        myAdd' !total (x:xs) = myAdd' (total + x) xs

(Вам понадобится {-# LANGUAGE BangPatterns #-} в верхней части исходного файла, чтобы скомпилировать это.)

Это накапливает сложение в другом параметре и на самом деле является хвостовой рекурсией (ваш не; + находится в хвостовой позиции, а не myAdd). Но на самом деле это не совсем хвостовая рекурсия, о которой мы заботимся в Хаскеле; это различие в основном относится к строгим языкам. Секрет в этом * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 10 * * * * * * * * *, поэтому он вычисляется каждый раз, когда вызывается * 10 27 *, поэтому никакие неоцененные дополнения не создаются, и он работает в постоянном пространстве. В этом случае GHC может на самом деле понять это с помощью -O2 благодаря своему анализу строгости, но я думаю, что обычно лучше четко указывать, что вы хотите строгого, а что нет.

Обратите внимание, что если добавление было ленивым, ваше определение myAdd будет работать нормально; проблема в том, что вы выполняете ленивый обход списка с помощью строгой операции, которая в итоге вызывает переполнение стека. Это в основном приходит с арифметикой, которая строга для стандартных числовых типов (Int, Integer, Float, Double и т. Д.).

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

myAdd = foldl' (+) 0

(Вам нужно будет добавить import Data.List для компиляции.)

foldl' (+) 0 [a, b, c, d] аналогично (((0 + a) + b) + c) + d, за исключением того, что при каждом применении (+) (как мы называем двоичный оператор + как значение функции), значение принудительно оценивается. Получающийся в результате код становится чище, быстрее и проще для чтения (как только вы узнаете, как работает свертывание списка, вы сможете понять любое определение, написанное на их основе, проще, чем рекурсивное определение).

По сути, проблема здесь не в том, что компилятор не может понять, как сделать вашу программу эффективной, а в том, что, сделав ее настолько эффективной, насколько вам нравится, вы можете изменить свою семантику , что оптимизация никогда не должна делать. Нестрогая семантика Haskell, безусловно, представляет собой кривую обучения для программистов на более «традиционных» языках, таких как C, но со временем это становится проще, и как только вы увидите мощь и абстракцию, которые предлагает нестрогость Haskell, вы никогда не захотите идти назад:)

Answer 2

Расширение примера, на который намекал Эхирд в комментариях:

data Peano = Z | S Peano
  deriving (Eq, Show)

instance Ord Peano where
    compare (S a) (S b) = compare a b
    compare Z Z = EQ
    compare Z _ = LT
    compare _ _ = GT

instance Num Peano where
    Z + n = n
    (S a) + n = S (a + n)
    -- omit others
    fromInteger 0 = Z
    fromInteger n
        | n < 0 = error "Peano: fromInteger requires non-negative argument"
        | otherwise = S (fromInteger (n-1))

instance Enum Peano where
    succ = S
    pred (S a) = a
    pred _ = error "Peano: no predecessor"
    toEnum n
        | n < 0 = error "toEnum: invalid argument"
        | otherwise = fromInteger (toInteger n)
    fromEnum Z = 0
    fromEnum (S a) = 1 + fromEnum a
    enumFrom = iterate S
    enumFromTo a b = takeWhile (<= b) $ enumFrom a
    -- omit others

infinity :: Peano
infinity = S infinity

result :: Bool
result = 3 < myAdd [1 .. infinity]

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

Answer 3

Небольшой забавный пример, касающийся «Проблема в том, что компилятор не может оптимизировать что-то, что кажется довольно тривиальным для оптимизации».

Допустим, я иду из Хаскелла в C ++. Раньше я писал foldr, потому что в Haskell foldr обычно более эффективен, чем foldl из-за лени и слияния списков.

Итак, я пытаюсь написать foldr для (односвязного) списка в C и жалуюсь, почему он крайне неэффективен:

int foldr(int (*f)(int, node*), int base, node * list)
{
    return list == NULL
        ? base
        : f(a, foldr(f, base, list->next));
}

Это неэффективно не потому, что рассматриваемый компилятор C является нереалистичным игрушечным инструментом, разработанным теоретиками башни из слоновой кости для их собственного удовлетворения, а потому, что рассматриваемый код совершенно не идиоматичен для C.

Это не тот случай, когда вы не можете написать эффективный foldr на C: вам просто нужен двусвязный список. В Haskell вы также можете написать эффективный foldl, вам нужны аннотации строгости, чтобы foldl был эффективным. Стандартная библиотека предоставляет как foldl (без аннотаций), так и foldl' (с аннотациями).

Идея левого свертывания списка в Haskell - это тот же вид извращения, что и желание перебирать односвязный список в обратном направлении с использованием рекурсии в C. Компилятор помогает обычным людям, а не извращенцам. Lol.

Поскольку ваши проекты на C ++, вероятно, не имеют кода, повторяющего односвязные списки в обратном направлении, мой проект HNC содержит только 1 foldl Я неправильно написал, прежде чем достаточно освоил Haskell. Вам вряд ли когда-нибудь понадобится foldl в Хаскеле.

Вы должны отучиться, что прямая итерация является естественной и самой быстрой, и узнать, что обратная итерация является. Прямая итерация (сворачивание влево) не выполняет то, что вы намереваетесь, пока вы не аннотируете: она выполняет три этапа - создание списка, создание цепочки блоков и вычисление блока управления, а не два (создание списка и обход списка). Обратите внимание, что в неизменяемых мировых списках можно эффективно создавать только в обратном направлении: a: b - это O (1), а a ++ [b] - это O (N).

И обратная итерация тоже не дает того, что вы намереваетесь. Он делает один проход вместо трех, как вы могли ожидать от своего фона C. Он не создает список, пересекает его до конца, а затем пересекает его назад (2 прохода) - он пересекает список по мере его создания, то есть 1 проход. При включенной оптимизации это просто цикл - никакие фактические элементы списка не создаются. С выключенными оптимизациями это все еще операция O (1) с большими постоянными издержками, но объяснение немного длиннее.

Answer 4

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

Спектакль

Дело в том, что ваша программа на самом деле не является хвостовой рекурсивной, то есть нет единственного вызова функции, которая может заменить рекурсию. Давайте посмотрим, что происходит, когда мы расширяемся myAdd [1..3]:

myAdd [1,2,3]
1 + myAdd [2,3]
1 + 2 + myAdd [3]

Как вы можете видеть, на любом данном шаге мы не можем заменить рекурсию вызовом функции, мы могли бы упростить выражение, сократив 1 + 2 до 3, но это не то, о чем говорит хвостовая рекурсия.

Итак, вот версия с хвостовой рекурсией:

myAdd2 = go 0
  where go a [] = a
        go a (x:xs) = go (a + x) xs

Давайте посмотрим, как оценивается go 0 [1,2,3]:

go 0 [1,2,3]
go (1+0) [2,3]
go (2 + 1 + 0) [3]

Как видите, на каждом шагу нам нужно только отслеживать один вызов функции, и пока первый параметр строго оценивать мы не должны получить экспоненциальное пространство взорвать, и фактически, если вы компилируете с оптимизацией (-O1 или -O2) GHC достаточно умен, чтобы понять это самостоятельно.

Выразительность

Хорошо, поэтому немного сложнее рассуждать о производительности в haskell, но большую часть времени вам не нужно. Дело в том, что вы можете использовать комбинаторы, которые обеспечивают эффективность. Этот конкретный шаблон выше записан foldl (и его строгим родственником foldl'), поэтому myAdd можно записать как:

myAdd = foldl (+) 0

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