Оптимизирована ли следующая функция хвостового вызова?

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

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

myLength (x:xs) = 1 + myLength(xs) 
myLength [] = 0
Источник

4 ответа

Решение

GHC, вероятно, может оптимизировать его, чтобы он был рекурсивным, но, как вы написали, это не так. Чтобы быть рекурсивным хвостовым вызовом, функция "top" в дереве должна быть рекурсивным вызовом. Когда я запускаю ваш код в 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, компилятор имеет достаточную свободу в реорганизации вашего кода во время оптимизации.

Источник

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

Источник

Нет, это не функция, вызывающая хвост (последний вызов в непустом списке будет + но это не имеет большого значения в 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)
Источник

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

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

Источник
Другие вопросы по тегам