CODEWITHSUNDEEP
haskell
Herbstein
Herbstein

Reputation: 309

Why does these three examples give different results? They seem to be equivalent

During my solving of AdventOfCode 2018 day 1 question 2 I ran into some weird behavior. The following code works as intended, and prints out the correct solution.

day1_2 = do
    content <- day1
    let content = scanl (+) 0 content
    return $ dup content
  where
    dup xs = dup' xs []
      where
        dup' [] _ = Nothing
        dup' (x : xs) seen =
            if x `elem` seen then Just x else dup' xs (x : seen)

It works, but I wanted to clean it up a little. As soon as I removed the second binding of content, and inlined the function call, the code stopped working. Since the dup function doesn't change I've omitted it from the rest of the snippets.

day1_2 = do
    content <- day1
    return $ dup $ scanl (+) 0 content

My understanding of Haskell tells me those two functions should give identical results, but they don't. On the input I've been given the first function returns Just 0 while the second returns Nothing. Is this a bug, or am I missing something?

Reducing the code even more still keeps the behavior from the second function.

day1_2 = dup . scanl (+) 0 <$> day1

Here day1 just reads the input given for day 1, and makes it parsable to Haskell.

day1 =
    map (read . (\n -> if head n == '+' then tail n else n))
        .   words
        <$> readFile "input/day1.txt"

Further weirdness:

day1_2 = do
    content <- day1
    let content' = scanl (+) 0 content
    return $ dup content

The above gives me Just 6. (Not the desired result, but that is expected)

day1_2 = do
    content <- day1
    let smth = scanl (+) 0 content
    return $ dup smth

The above, however, gives me Nothing even though it's functionally equivalent to the first snippet, save for some naming differences. From these last tests it's obvious that the content binding in the original is shadowed. However, if no shadowing is involved then the wrong output is given.

My specific input for day1.

Upvotes: 0

Views: 85

Answers (2)

HTNW
HTNW

Reputation: 29193

Your original code is broken.

do content <- day1
   let content = scanl (+) 0 content
   _etc

Does not mean "bind the result of day1 to content, apply scanl (+) 0 to that, and bind that to content". Actually, what you've written is the same as this:

do day1
   let content = scanl (+) 0 content
   _etc

Which has you executing day1, discarding its result, and then binding to content a recursively defined list. You're correct that content is being shadowed, but you didn't realize that the second content shadowed the first one in its own definition. If you type let content = scanl (+) 0 content in content, you'll actually see you have an infinite list of 0s. It should be obvious why you then get Just 0 as an "answer."

The "correct" solution is actually the final one.

day1_2 = do content <- day1
            let smth = scanl (+) 0 content
            return $ dup smth
-- don't need do notation; just functor-function-application
day1_2 = dup <$> scanl (+) 0 <$> day1

But you are missing one crucial piece of the question:

Note that your device might need to repeat its list of frequency changes many times before a duplicate frequency is found

You need just one call to a single standard library function to make this work. See if you can find it :). (Fair warning: once you find the function and use it, this solution takes a good few minutes to finish running, but it does work.)

day1_2 = dup <$> scanl (+) 0 <$> _libfunction <$> day1

Upvotes: 1

snak
snak

Reputation: 6703

When you write let content = scanl (+) 0 content, the second content is not the content declared in the previous line, but content declared in this line using let.

So the first code just ignores content gotten from day1, but the second code uses it. That's why these two behave differently.

Upvotes: 1

Related Questions