Recursive Haskell function seemingly doesn't terminate

Question

To improve my Haskell skills, I'm trying to solve the Advent of Code 2018. As expected, I am already stuck on day 1, specifically on part 2:

--- Part Two ---

You notice that the device repeats the same frequency change list over and over.

To calibrate the device, you need to find the first frequency it reaches twice.

For example, using the same list of changes above, the device would loop as follows:

Current frequency 0, change of +1; resulting frequency 1.

Current frequency 1, change of -2; resulting frequency -1.

Current frequency -1, change of +3; resulting frequency 2.

Current frequency 2, change of +1; resulting frequency 3.

(At this point, the device continues from the start of the list.)

Current frequency 3, change of +1; resulting frequency 4.

Current frequency 4, change of -2; resulting frequency 2, which has already been seen.

In this example, the first frequency reached twice is 2. Note that your device might need to repeat its list of frequency changes many times before a duplicate frequency is found, and that duplicates might be found while in the middle of processing the list.

Here are other examples:

+1, -1 first reaches 0 twice.

+3, +3, +4, -2, -4 first reaches 10 twice.

-6, +3, +8, +5, -6 first reaches 5 twice.

+7, +7, -2, -7, -4 first reaches 14 twice.

What is the first frequency your device reaches twice?

Basically, I have a very large list vals::[Int] that includes all the frequency changes mentioned above.

Here is the function I wrote for solving this problem:

-- [1] The list of frequency changes
-- [2] The first repeat frequency
--             [1]      [2]
part2helper :: [Int] -> Int
part2helper ds = go ds []
    where go ds [] = go ds [0]
          go (d:ds) [f] = go ds $ (f+d):[f]
          go (d:ds) (f:fs) =
              if f `elem` fs then f
              else go ds $ (d+f):f:fs

I test this function with the values provided in the description in ghci:

*Main> part2helper (cycle [1, -2, 3, 1])
2
*Main> part2helper (cycle [1, -1])
0
*Main> part2helper (cycle [3, 3, 4, -2, -4])
10
*Main> part2helper (cycle [7, 7, -2, -7, -4])
14
*Main>

All result are correct, so I assume my function works correctly. The problem now is, when I compile this into a program that reads the input list from a file, the program never terminates. Here's the code:

module Main where

import System.Environment

main = do 
    [input] <- getArgs
    s       <- readFile input
    let n    = lines $ s
        vals = map (read::String->Int) $ fmap (filter (/='+')) n
        sol  = part2helper (cycle vals)
    print sol

-- [1] The list of frequency changes
-- [2] The first repeat frequency
--             [1]      [2]
part2helper :: [Int] -> Int
part2helper ds = go ds []
    where go ds     []     = go ds [0]
          go (d:ds) [f]    = go ds $ (f+d):[f]
          go (d:ds) (f:fs) =
              if f `elem` fs then f
              else go ds $ (d+f):f:fs

This builds with GHC correctly, but as I said, never terminates and prints no result. What am I missing? The input file can be found here.

It is possible that no frequency is ever reached twice. For example [11,-1] will just go off to infinity. You might want to Debug.Trace in part2helper to see if this is happening, or if it's a performance thing as melpomene suggests (though your algorithm could be improved, I have my doubts that it's a performance problem) — luqui
– luqui, Commented Dec 14, 2018 at 0:49
Actually it might be. I thought a solution would always be found within 2 cycles, but I was mistaken--it might take up to n cycles, which would make your algorithm O(n^4). That could easily get slow. — luqui
– luqui, Commented Dec 14, 2018 at 1:01
@luqui is correct; I was working on my laptop, I just ran it on my desktop, and it produces the correct result after some time. So it is simply a very ineffective algorithm that runs criminally slow. — koalag
– koalag, Commented Dec 14, 2018 at 1:51

Jorge Adriano Branco Aires · Accepted Answer · 2018-12-14 19:50:30Z

You're trying to put everything together in a single function. It's much better if you work in a modular fashion, breaking the problem into smaller ones.

Here's an idea,

generate the sequence of frequencies,
f0, f1, f2...
generate the sequence of cumulative sets of frequencies
{}, {f0}, {f0,f1}, {f0,f1,f2}...
check repeated insertions, i.e.
fi such that fi ∈ {f0..fi-1}

To make things clearer regarding the last point consider,

 f0, f1,   f2,      f3...
 {}, {f0}, {f0,f1}, {f0,f1,f2}...`

if f3 were a repetition then f3 ∈ {f0,f1,f2}

This may seem terribly inefficient but because Haskell is lazy, these lists will be generated as needed.

We'll need to import modules to work with sets and maybes,

import Data.Set
import Data.Maybe

Generating the frequencies from the first frequency and a list of frequency changes can be done via scanl (+). The function scanl (+) x xs operates the elements of xs with the operator + , starting at x, generating the cumulative list of sums.

freqs :: Int -> [Int] -> [Int]
freqs = scanl (+)

Now we can generate the list of sets. Here too we use a scanl. In each step we insert a new frequency, and we start with the empty set.

sets  :: [Int] -> [Set Int]
sets  = scanl (\s x -> insert x s) (empty)

Once we have the frequencies and the sets we are pretty much done.The main function just puts everything together. It combines both lists and finds the first pair (fi , {f0,...,fi-1}) such that fi ∈ {f0,...,fi-1}, and returns the corresponding fi

result :: Int -> [Int] -> Maybe Int
result x xs = let fs = freqs x xs
                  ss = sets fs                  
                  r  = find (\(y,s) -> y `elem` s) (zip fs ss)
              in fmap fst r

Note find returns a Maybe (Int, Set Int). It may find Nothing or return Just (x,s) for some frequency x that was already in s. We use fmap fst to turn Just (x,s) into Just x.

EDIT

Once you've got things working if you wish to, may optimize a few things, or play around with your style. The following is a more succinct, and possibly a little bit more efficient version.

The list of frequencies and sets can be built together in one go.

freqsets :: Int -> [Int] -> [(Int, Set Int)]
freqsets f0 = scanl (\(f,s) x -> (f+x,insert f s)) (f0,empty)

And so it's ready to use for the result function. Also we can take advantage of Maybe being a monad to make things a bit more readable.

result :: Int -> [Int] -> Maybe Int
result f0 xs = do (f,_) <- find(\(y,s)->y `elem` s) (freqsets f0 xs)
                  return f

And there you have it, a rather short solution. I like the change in the result function. I like the do notation, as well as not having it calculate the zipping of the two previous lists. I'm not so sure if "fusing" the building of both lists is worth it. It's a bit less readable. Using three functions, one for frequencies, one for sets, and one for zipping, might be best.

Very thorough answer and analysis! I was thinking along these lines a bit, but went for "slow and dirty". But such math analysis are almost the most fun about such stuff.
@georgjz Added a shortened version by the way. Also note that while it is indeed fun, it's also a matter of practicality. It makes it easier to understand, to reason about, to test, to adapt, etc. Even if you optimise things latter, it's good to have a simple and easy to read version around, that you can use to test the correctness of your changes.

Collectives™ on Stack Overflow

Recursive Haskell function seemingly doesn't terminate

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related