Beginner Unsure of Next Step for solution (perhaps a foldl?)

I’m using Advent of Code to learn Haskell. I’ve read most of Learn You a Haskell (just haven’t read the Monad Chapters yet)

Right now I’m doing this problem: https://adventofcode.com/2016/day/1

With this code: https://github.com/djotaku/adventofcode/blob/7f04c256cbdf911e76a0f3fe7eba70bdb729f82a/2016/Day_01/Haskell/solution.hs

If I get a series of directions like “R5, R5, L5” etc I get the following in ghci:

getComplexDirections “R5, R5, L5”
[(0 :+ (-1),“5”),(0 :+ (-1),“5”),(0 :+ 1,“5”)]

So, the way I solved this in my imperative languages was to start off with (0:+1) and multiply that by whatever is the first value in the tuple in the array. That gives me my new direction. Then I set off in that direction however many blocks is the second value in the tuple.

So since I can’t hold state in Haskell or keep changing a variable value, I figured I need to do a foldl? But I’m not quite sure where to go from here.

Thanks!

Welcome!
You’re spot on with the foldl idea (or foldl'). foldl' can let you walk through a list carrying a bit of state from one element to the next. In the foldl' signature (foldl' :: (b -> a -> b) -> b -> [a] -> b) your “state” is the b, and the a is the element type. So if in your imperative language you’re used to you had

var state = 0;
for (var i = 1; i <=5; i++) { 
  state = state + i;
}
return state;

you could accomplish the same thing with

foldl' (\state i -> state + i) 0 [1 .. 5]`

or just

foldl' (+) 0 [1 .. 5]

You should be able to use foldl' to solve it pretty similarly to your imperative solution - you just take the state as an input to the folding function and return the updated state instead of mutating the same state variable.

Another natural way to solve this could be with the related function scanl', which is like foldl' but it returns all the intermediate results that get produced in a new list. So where foldl' (+) 0 [1 .. 5] = 15, scanl' (+) 0 [1 .. 5] = [0,1,3,6,10,15]. Using scanl' you could make your state/accumulator include the direction you’re facing and produce the list of movements each as a vector, and then sum all the vectors together. That might be nicer than using foldl' with the current position as the state because

  1. It’s less stateful (all you need from the previous iteration is the direction, and not also the current position).
  2. It’s probably easier to debug because you can observe the direction & vector at each step in GHCi without having to use trace.

Another way to go (which would be recommended if foldl' and scanl' still stretch your brain a bit) is to just implement it with manual recursion. Getting really comfortable with manual recursion makes grokking folds more easy. For example, the foldl' (+) 0 [1 .. 5] could be done as

addElements :: Int -> [Int] -> Int
addElements accumulator (x:rest) = addElements (accumulator + x) rest 
addElements accumulator [] = accumulator

addElements 0 [1 .. 5]

and the scanl (+) 0 [1 .. 5] could be done as

runningSum :: Int -> [Int] -> [Int]
runningSum accumulator (x:rest) = accumulator : runningSum (accumulator + x) rest
runningSum accumulator [] = [accumulator]

runningSum 0 [1 .. 5]

which is obviously more work (that’s why helper functions like foldl and scanl exist), but really helps to nail down the core principles.

Is that enough to get you going?

3 Likes

That’s incredibly helpful. Thanks for such a comprehensive response. I will mess around with it later today and if there’s something that doesn’t make sense, I’ll be sure to ask. scanl might even help me with part 2 for the problem where you need to check if you’ve been to a certain spot before. But first I’d like to just do part 1 and see if I can’t get my first Haskell program working.

1 Like

I believe I understand what you explained here, but I’m having trouble creating a lambda that works for scanl (or foldl). The problem is that within the list I have a tuple. So I can’t just do:

scanl (*) (0:+1) [((0:+1), 4)]

<interactive>:99:20: error:
    • Couldn't match expected type ‘Complex a’
                  with actual type ‘(Complex Integer, Integer)’
    • In the expression: ((0 :+ 1), 4)
      In the third argument of ‘scanl’, namely ‘[((0 :+ 1), 4)]’
      In the expression: scanl (*) (0 :+ 1) [((0 :+ 1), 4)]
    • Relevant bindings include
        it :: [Complex a] (bound at <interactive>:99:2)

I tried something like:

scanl (\x y z -> x * y * z) (0:+1) [((0:+1), 4)]

<interactive>:100:9: error:
    • Couldn't match expected type ‘Complex a’
                  with actual type ‘Complex a -> Complex a’
    • In the first argument of ‘scanl’, namely ‘(\ x y z -> x * y * z)’
      In the expression:
        scanl (\ x y z -> x * y * z) (0 :+ 1) [((0 :+ 1), 4)]
      In an equation for ‘it’:
          it = scanl (\ x y z -> x * y * z) (0 :+ 1) [((0 :+ 1), 4)]
    • Relevant bindings include
        it :: [Complex a] (bound at <interactive>:100:2)

<interactive>:100:38: error:
    • Couldn't match expected type ‘Complex a’
                  with actual type ‘(Complex Integer, Integer)’
    • In the expression: ((0 :+ 1), 4)
      In the third argument of ‘scanl’, namely ‘[((0 :+ 1), 4)]’
      In the expression:
        scanl (\ x y z -> x * y * z) (0 :+ 1) [((0 :+ 1), 4)]
    • Relevant bindings include
        it :: [Complex a] (bound at <interactive>:100:2)

Essentially what I need for part 1 is to do this:

scanl (*) (0:+1) [(0:+1), (0:+1)]
[0.0 :+ 1.0,(-1.0) :+ 0.0,(-0.0) :+ (-1.0)]

with each of those also being mutiplied by the magnitude of the number next to it in the tuple. Then at the end sum them all up. (except the first value, I think) So I’m getting stuck on how to refer to each of the values in the tuple.

Also, what character are you using in scanl` because both the character next to the number 1 and the apostraphe seemed to cause issues for me.

Oh I’m using the apostrophe. scanl' looks like it’s defined in Data.List though and not in Prelude, so you’d have to add an import. (Frankly, using plain scanl would be fine for a problem of this size, it’s just generally recommended to use the ' version for performance reasons).

Anyway, you’re on the right track building a lambda. You’re not going to get away with a simple operator here. In the lambda, you can take the current state + the next element of the list as inputs. If the list elements are tuples though, you have to format your lambda to take a tuple as well, so like
(\state (direction, magnitude) -> ...). I think your intuition is telling you that your function is taking in three inputs, but it’s actually still taking in two inputs, and one of those happens to be a tuple pair.

So I’m I understanding correctly that you’re trying to make the state a complex number, then multiply together the state, the complex side of the list element, and the integer side of the list element? Syntactically, I think that lambda would look like
(\state (direction, magnitude) -> state * direction * (magnitude:+0))
(I’m guessing you can’t multiply a complex integer by an integer directly, but I could be wrong about that, I’ve not coded with complex numbers in Haskell before).

1 Like

You definitely got me going in the right direction there. I had done a lambda like (x,y) z… but now I see that the first param is the first state. Thanks for that. I will see if that gives me what I need.

1 Like