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
- It’s less stateful (all you need from the previous iteration is the direction, and not also the current position).
- 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?