Possible tail recursive solution in haskell producing stack overflow

Question

I've been trying to solve the adventofcode day 5 question 2 (https://adventofcode.com/2017/day/5). It differs from the first question where if the item is bigger of equal to 3, it's decreased instead of increased by 1.

When running the implementation with the test data, it produces the correct outcome, so it seems that the implementation is perfect. Also, the recursive call looks to be in tail position, but it's still producing a stackoverflow exception.

The code looks like this

module AdventOfCode5 where type Instruction = Int type Position = Int main :: IO () main = do input <- readFile "day5input.txt" let instructions = fmap (read :: String -> Instruction) $ lines input _ <- putStrLn $ show $ computeResult (Prelude.length instructions) 0 (+1) $ instructions return () main2 :: IO () main2 = do input <- readFile "day5input.txt" let instructions = fmap (read :: String -> Instruction) $ lines input _ <- putStrLn $ show $ computeResult (Prelude.length instructions) 0 decAbove3AndIncBelow3 instructions return () decAbove3AndIncBelow3 :: Int -> Int decAbove3AndIncBelow3 x | x >= 3 = x - 1 | otherwise = x + 1 computeResult :: Int -> Position -> (Int -> Int) -> [Instruction] -> Int computeResult = takeStep' 0 where takeStep' :: Int -> Int -> Position -> (Int -> Int) -> [Instruction] -> Int takeStep' count max pos changeInteger instructions | pos >= max = count | otherwise = let elementAtPos = instructions!!pos newCount = count + 1 newPos = pos + elementAtPos newInstructions = (take pos instructions) ++ ([(changeInteger elementAtPos)]) ++ (drop (pos + 1)) instructions in takeStep' newCount max newPos changeInteger newInstructions

The idea of the implementation is that you hold a counter and increment the counter for every iteration, in combination with altering the list of instructions with the updated version (where the Int -> Int is the function that knows how to update). You got a position where to look at and the recursion stops as soon as the position is larger than the list size (which i passed as input but could also be derived from the list of instructions).

Can anybody explain to me why this one is producing a stackoverflow?

How are you running your program? How long does it take for the stackoverflow to occur? — Li-yao Xia
– Li-yao Xia, Commented Dec 5, 2017 at 13:24
FWIW, I did this exercise earlier today as well, and the second puzzle did take long enough to run that I went and brushed my teeth waiting for it to finish - which it did, 26,948,068 steps later! Here's my code, in case anyone's interested: github.com/ploeh/advent-of-code-2017/blob/master/Day05/… — Mark Seemann
– Mark Seemann, Commented Dec 5, 2017 at 13:32
I can't reproduce the stack overflow, but there is a space leak in the first argument of takeStep' which is fixed either by forcing it or compiling with optimizations. — Li-yao Xia
– Li-yao Xia, Commented Dec 5, 2017 at 13:51
@Li-yaoXia I run it just in the repl by first loading it (:l adventofcode5.hs) and then running just main2. — Mauro Palsgraaf
– Mauro Palsgraaf, Commented Dec 5, 2017 at 13:54
@Li-yaoXia How do you compile with optimizations? I get the stackoverflow after running for a long time (15 minutes maybe). My computer slept in between but that shouldn't be a problem right — Mauro Palsgraaf
– Mauro Palsgraaf, Commented Dec 5, 2017 at 13:56

Li-yao Xia · Accepted Answer · 2017-12-05 14:43:50Z

There is a space leak in the first argument of takeStep', because it builds a thunk (... ((0 + 1) + 1) ...) + 1 instead of just evaluating the integer.

The stack may explode when that thunk gets evaluated.

Use seq to force count before continuing, e.g., count `seq` otherwise in the guard;
or compile with optimizations.

ghci is interpreting it, not compiling it. In particular, it doesn't perform the strictness analysis necessary to automatically fix that leak.

You can run this command to compile with optimizations (-O)

ghc -O -main-is AdventOfCode5.main2 AdventOfCode5.hs

(although even without optimizations compilation seems to reduce space usage enough to succeed.)

This indeed seemed to be the problem and thank you for explaining how this could be fixed!

Collectives™ on Stack Overflow

Possible tail recursive solution in haskell producing stack overflow

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related