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

5

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.)

edited Dec 5, 2017 at 14:43

answered Dec 5, 2017 at 14:14

Li-yao Xia

34.2k2 gold badges38 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mauro Palsgraaf Over a year ago

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

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related