folding right vs left

Question

This has been discussed to death here on SO, but my specific example is escaping me because I feel that my fold shouldn't care whether it's composed right-to-left or left-to-right. This is a solution to day 1 of 2016's Advent of Code which boils down to taking a list of instructions (turn right/left, walk x steps forward), applying them, and giving the taxicab-geometry distance between where you end up and where you started.

I wrote an apply function to handle one step of this journey, which has signature:

data Direction   = North | East | South | West deriving (Enum, Show)
type Location    = (Int, Int)
type Instruction = String

apply :: Direction -> Location -> Instruction -> (Direction, Location)

Assume for the moment that it's implemented correctly (because I tested it and it is. I'll include a runnable example below the fold). I noticed that I can use a fold to apply this to the whole list of instructions, and did

(_, finalLocation) = foldr f (North, (0, 0)) instructions  -- note the foldr.
  where f = (\ins (d, loc) -> apply d loc ins)

Using the right-associated fold here worked, but gave me the wrong answer. When I re-ran it with foldl (and flip f) I got a totally different answer which adventofcode accepted, so I acknowledge that the fold direction is definitely the difference, I just don't know why it's a difference since it seems to me that my code shouldn't care which way the fold happens.

Why am I wrong?

---

module AdventOfCode where

-- split
import Data.List.Split (splitOn)

day1input :: String
day1input = "L4, R2, R4, L5, L3, L1, R4, R5, R1, R3, L3, L2, L2, R5, R1, L1, L2, \
            \R2, R2, L5, R5, R5, L2, R1, R2, L2, L4, L1, R5, R2, R1, R1, L2, L3, \
            \R2, L5, L186, L5, L3, R3, L5, R4, R2, L5, R1, R4, L1, L3, R3, R1, L1, \
            \R4, R2, L1, L4, R5, L1, R50, L4, R3, R78, R4, R2, L4, R3, L4, R4, L1, \
            \R5, L4, R1, L2, R3, L2, R5, R5, L4, L1, L2, R185, L5, R2, R1, L3, R4, \
            \L5, R2, R4, L3, R4, L2, L5, R1, R2, L2, L1, L2, R2, L2, R1, L5, L3, L4, \
            \L3, L4, L2, L5, L5, R2, L3, L4, R4, R4, R5, L4, L2, R4, L5, R3, R1, L1, \
            \R3, L2, R2, R1, R5, L4, R5, L3, R2, R3, R1, R4, L4, R1, R3, L5, L1, L3, \
            \R2, R1, R4, L4, R3, L3, R3, R2, L3, L3, R4, L2, R4, L3, L4, R5, R1, L1, \
            \R5, R3, R1, R3, R4, L1, R4, R3, R1, L5, L5, L4, R4, R3, L2, R1, R5, L3, \
            \R4, R5, L4, L5, R2"

day1Processed :: [String]
day1Processed = splitOn ", " day1input

data Direction = North | East | South | West deriving (Enum, Show)
type Location = (Int, Int)

-- |'apply' takes your current 'Direction' and 'Location', applies the instruction
-- and gives back a tuple of (newDirection, (new, location))
apply :: Direction -> Location -> String -> (Direction, Location)
apply d' loc (t:num') = (d, step d loc numsteps)
  where d        = turn d' t
        numsteps = read num' :: Int

-- |'distanceBetween' returns the taxicab geometric distance between two 'Location's
distanceBetween :: Location -> Location -> Int
distanceBetween (x1, y1) (x2, y2) = (abs $ x1-x2) + (abs $ y1-y2)


-- |'turn' changes direction based on the received Char
turn :: Direction -> Char -> Direction
turn West  'R' = North
turn North 'L' = West
turn d     'R' = succ d
turn d     'L' = pred d
turn d      _  = d

-- |'step' moves location based on current direction and number of steps
step :: Direction -> Location -> Int -> Location
step North (x, y) s = (x  , y+s)
step East  (x, y) s = (x+s, y)
step South (x, y) s = (x  , y-s)
step West  (x, y) s = (x-s, y)

wrongLocation :: Location
rightLocation :: Location
(_, wrongLocation) = foldr (\x (d, loc) -> apply d loc x) (North, (0, 0)) day1Processed
(_, rightLocation) = foldl (\(d, loc) x -> apply d loc x) (North, (0, 0)) day1Processed

wrongAnswer :: Int
rightAnswer :: Int
wrongAnswer = distanceBetween (0, 0) wrongLocation
rightAnswer = distanceBetween (0, 0) rightLocation

Answer 1

Based on the comments, I'd say you have some confusion about the difference between foldl and foldr. I'll try to distinguish those here. Let's look at a minimal example.

foldr f x [a, b, c] = a `f` (b `f` (c `f` x))
foldl g x [a, b, c] = ((x `g` a) `g` b) `g` c

That's the way these functions would expand on a somewhat small list containing three elements. Now, let's suppose g = flip f and see what foldl does then.

foldr f x [a, b, c] = a `f` (b `f` (c `f` x))
foldl (flip f) x [a, b, c] = c `f` (b `f` (a `f` x))

So the order of the list, in a sense, ends up being reversed when you do foldl (flip f) as opposed to foldr f.

Thus, your initial assertion that foldl (flip f) === foldr f is false in general, but we do end up with a rather interesting property in its place. Assuming the list we're working with is finite, it seems that foldl (flip f) x === foldr f x . reverse