Przepełnienie stosu w GHCI podczas próby wyświetlenia numeru

Question

Próbując nauczyć się Haskella, zaimplementowałem obliczenie pi, aby poprawnie zrozumieć funkcje i rekurencję.

Używanie Leibniz Formula obliczania PI, wpadłem z następujących, które drukuje PI tolerancji danego parametru, a liczba funkcji rekurencyjnej wzywa, aby uzyskać tę wartość:

reverseSign :: (Fractional a, Ord a) => a -> a 
reverseSign num = ((if num > 0 
         then -1 
         else 1) * (abs(num) + 2)) 

piCalc :: (Fractional a, Integral b, Ord a) => a -> (a, b) 
piCalc tolerance = piCalc' 1 0.0 tolerance 0 

piCalc' :: (Ord a, Fractional a, Integral b) => a -> a -> a -> b -> (a, b) 
piCalc' denom prevPi tolerance count = if abs(newPi - prevPi) < tolerance 
             then (newPi, count) 
             else piCalc' (reverseSign denom) newPi tolerance (count + 1) 
             where newPi = prevPi + (4/denom) 

więc kiedy biegnę to w GHCI, wydaje się działać zgodnie z oczekiwaniami:

*Main> piCalc 0.001 
(3.1420924036835256,2000) 

Ale jeśli ustawić moja tolerancja zbyt dobrze, to się dzieje:

*Main> piCalc 0.0000001 
(3.1415927035898146,*** Exception: stack overflow 

Wydaje mi się to całkowicie sprzeczne z intuicją; Rzeczywiste obliczenia działają poprawnie, ale po prostu próbuje wydrukować, jak wiele połączeń rekursywnych nie powiedzie się?

Dlaczego tak się dzieje?

Answer 1

Jest to wariant tradycyjnego przepełnienia stosu foldl (+) 0 [1..1000000]. Problem polega na tym, że wartość zliczania nigdy nie jest oceniana podczas oceny piCalc'. Oznacza to, że po prostu niesie on stale rosnący zestaw porcji, co oznacza, że ​​dodatek trzeba zrobić w razie potrzeby. Gdy jest to potrzebne, fakt, że jego ocena wymaga głębokości stosu proporcjonalnej do liczby uderzeń, powoduje przepełnienie.

Najprostsze rozwiązanie sprawia, że ​​korzystanie z rozszerzeniem BangPatterns, zmieniając rozpoczęcia piCalc' do

piCalc' denom prevPi tolerance !count = ... 

Zmusza wartość count być oceniane gdy wzorca, co oznacza, że ​​nigdy nie będzie rosnąć gigantyczny łańcuch odłamków.

równoważnie i bez użycia rozszerzenia, można napisać go jako

piCalc' denom prevPi tolerance count = count `seq` ... 

To jest dokładnie równoważny znaczeniowo do powyższego rozwiązania, ale korzysta seq wyraźnie zamiast pośrednio poprzez rozszerzenie języka. Dzięki temu jest bardziej przenośny, ale bardziej gadatliwy.

Jak, dlaczego przybliżenie liczby pi nie jest długa sekwencja zagnieżdżonych łącznikami, ale liczba jest: piCalc' oddziałów na wyniku obliczeń, która wymaga wartości newPi, prevPi i tolerance.Musi zbadać te wartości, zanim zdecyduje, czy to zrobione, czy też musi przeprowadzić kolejną iterację. Jest to gałąź, która powoduje, że ocena jest wykonywana (gdy wykonywana jest aplikacja funkcji, co zwykle oznacza, że ​​coś jest dopasowaniem do wzorca na wyniku działania funkcji). Z drugiej strony, nic w obliczeniu piCalc' zależy od wartości count, więc nie jest uwzględniany podczas obliczeń.

Answer 2

Liczba nie jest nigdy oceniana podczas obliczeń, więc pozostawia się ją jako ogromną liczbę uderzeń (przepełnienie stosu) aż do samego końca.

Można wymusić swoją ocenę podczas obliczania przez umożliwiając rozszerzenie BangPatterns i pisanie piCalc' denom prevPi tolerance !count = ...

Dlaczego więc tylko trzeba wymusić ocenę count? Cóż, wszystkie pozostałe argumenty są oceniane w if. Musimy sprawdzić je wszystkie, zanim ponownie zadzwonimy pod numer piCalc', więc nie budują się; potrzebujemy rzeczywistych wartości, a nie tylko "obietnic, że można je obliczyć"! count, z drugiej strony, nigdy nie jest potrzebny podczas obliczeń i może pozostać jako seria dźwięków do samego końca.