左右折叠

Question

这已被讨论 到 死亡在这里如此,但我具体的例子是逃避我,因为我觉得我的折叠不应该关心无论是由右到左或左到右.这是2016年第1天代码出现的解决方案,归结为获取指令列表(向右/向左,向前走x步),应用它们,并给出你最终到达的地方与出租车几何之间的距离你开始了

我写了一个apply函数来处理这个旅程的一个步骤,它有签名:

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

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

假设它正确实现(因为我测试了它,它是.我将在折叠下面包括一个可运行的例子).我注意到我可以使用折叠将其应用于整个指令列表,并且确实如此

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

使用权利相关的折叠在这里工作,但给了我错误的答案.当我用foldl(和flip f)重新运行它时,我得到了一个完全不同的答案,其中接受了adventofcode,所以我承认折叠方向肯定是差异,我只是不知道为什么它有区别,因为在我看来我的代码不应该关心折叠发生的方式.

为什么我错了？

---

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

根据评论,我会说你对foldl和之间的区别有些困惑foldr.我会试着在这里区分这些.让我们看一个最小的例子.

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

这就是这些函数在包含三个元素的小型列表上扩展的方式.现在,让我们假设g = flip f并看看那是什么foldl.

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))

所以列表的顺序,从某种意义上说,最终当你被逆转foldl (flip f),而不是foldr f.

因此,你的初始断言foldl (flip f) === foldr f一般是错误的,但我们最终会得到一个相当有趣的属性.假设我们正在使用的列表是有限的,似乎foldl (flip f) x === foldr f x . reverse