Является ли следующая функция хвостового вызова optmized?

Question

Является ли следующая функция хвостового вызова optmized?

Я новичок в haskell (впервые пробую FN программирование) и просто пробую различные упражнения из книги "реальный мир haskell". Может ли кто-нибудь, пожалуйста, исправить меня и сказать, оптимизирована ли функция ниже хвостового вызова или нет? Если да, то не могли бы вы поправить меня, как это делается? Я добавляю 1 к рекурсивной функции, поэтому я считаю, что это должно вызвать исключение stackoverflow?

Я попытался вызвать myLength [1..2000000] но это не вызвало никакого исключения stackoverflow

myLength (x:xs) = 1 + myLength(xs) 

myLength [] = 0

618 4

haskell recursion tail-recursion

4 ответов:

Comments

Ничего не найдено.

bheklilr · Accepted Answer · 2014-08-19 17:57:14

GHC, вероятно, может оптимизировать это, чтобы быть хвостовым вызовом рекурсивным, но способ, которым вы это написали, не является. Чтобы быть рекурсивным хвостовым вызовом," верхняя " функция в дереве должна быть рекурсивным вызовом. Когда я запускаю ваш код в GHCi с [1..20000000000000], у него заканчивается память с ошибкой сегментации, поэтому он не будет работать для очень больших входных данных.

Если мы немного изменим ваше определение, я думаю, это сделает его немного более ясным относительно того, почему это не TCR:
myLength (x:xs) =
    (+)
        1
        (myLength xs)
myLength [] = 0
Вот я его сломал. в то, что по существу является деревом, и может быть представлено как
        (+)
       /   \
      /     \
     1     myLength
              \
               xs
Как вы можете видеть, последняя функция, вызываемая в этом дереве, - это (+), а не myLength. Чтобы исправить это, вы можете использовать шаблон сгиба:
myLength = go 0
    where
        go acc (x:xs) = go (1 + acc) xs
        go acc []     = acc
А теперь дерево выглядит как
             go
           /    \
         (+)     xs
        /   \
       1    acc
Таким образом, верхняя функция в дереве-это go, которая является рекурсивным вызовом. Кроме того, вы можете использовать встроенный сгиб для реализации этого. Чтобы не создавать много Громов, моя рекомендация была бы использовать foldl' из Data.List:
myLength = foldl' (\acc x -> acc + 1) 0
И хотя это может занять очень много времени для выполнения, он не будет взрывать стек и не будет создавать Громов, которые съедают ОЗУ.

Но, как говорит @DonStewart, компилятор имеет достаточно свободы в перестановке кода во время оптимизации.

Don Stewart · Accepted Answer · 2014-08-19 17:53:26

Наивно, это использует стек. Но язык не конкретизирует операционную семантику, поэтому компилятор волен изменять порядок вещей до тех пор, пока он не изменяет наблюдаемую строгость.

Carsten · Accepted Answer · 2014-08-19 18:11:02

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

Таким образом, вам не нужно реструктурировать его, но если вы хотите, вы можете сделать это с помощью аккумулятора:
myLength :: [a] -> Int
myLength = myLength' 0
  where myLength' acc [] = acc
        myLength' acc (_:xs) = myLength' (acc+1) xs
Если мы хотим сделать Карла (немного больше) счастливым, мы можем избавиться от некоторых Громов (не слишком усложняя это - или так я думаю, я не настолько хорош, когда дело доходит до лени в Хаскелле, извините):
myLength :: [a] -> Int
myLength = myLength' 0
  where myLength' acc []     = acc
        myLength' acc xs     = let acc' = acc+1
                               in seq acc' $ myLength' acc' (tail xs)

Carl · Accepted Answer · 2014-08-19 17:56:55

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

Насколько мне известно, GHC не имеет никаких оптимизаций, которые изменят это на более эффективную форму памяти, и я подозреваю, что комментарий @Ferruccio к чему-то относится.