haskell - 将两个关联列表与正在运行的累加器合并

Question

基本上，我会将其描述为 [(,)] 的联合/合并。与 snd 上正在运行的累加器相结合对...有没有一种优雅的方式来实现这一点？

(请仅在回答问题时引用我的代码。如果您想查看我的代码，那也很好，但请在另一个网站上这样做:https://codereview.stackexchange.com/questions/54993/merging-time-series)

一个时间序列，

data Model a where
  Variant  :: [(Day, a)] -> Model a
  deriving (Show)

... 在哪里输入 a在 [(Day, a)]基本上代表“总余额”，例如银行账户。

一些示例数据，

day1 = fromGregorian 1987 10 17
day2 = fromGregorian 1987 10 18
day3 = fromGregorian 1987 10 19
day4 = fromGregorian 1987 10 20
day5 = fromGregorian 1987 10 21
day6 = fromGregorian 1987 10 22

m1 = Variant [(day1, 1), (day3, 3), (day5, 5)] :: Model Integer
m2 = Variant [(day1, 1), (day2, 2), (day4, 4), (day6, 6)] :: Model Integer

现在，合并两个时间序列，使“总余额”是相加的，

(&+) :: Num a => Model a -> Model a -> Model a
(Variant a) &+ (Variant b) = Variant $ reverse $ fst $ go a b ([],0)
  where
    go             []             [] (xs, c) = (xs, c)
    go   ((da,va):as)             [] (xs, c) = go as [] (((da,va+c):xs), va+c)
    go             []   ((db,vb):bs) (xs, c) = go [] bs (((db,vb+c):xs), vb+c)
    go a@((da,va):as) b@((db,vb):bs) (xs, c)
      | da > db  = go  a bs (((db,vb+c):xs), vb+c)
      | da < db  = go as  b (((da,va+c):xs), va+c)
      | da == db = go as bs (((da,va+vb+c):xs), va+vb+c)

所以，

what = m1 &+ m2

Variant [(1987-10-17,2),(1987-10-18,4),(1987-10-19,7),(1987-10-20,11),(1987-10-21,16),(1987-10-22,22)]

Answer 1

看到的那一刻reverse我觉得可能有麻烦。这是一个更懒惰的版本，适用于无限值。它确实依赖于它的每个输入，按 Day 排序。 ， 然而。首先我们寻求merge两条流

merge :: Num a => Model a -> Model a -> Model a
merge (Variant xs) (Variant ys) = Variant (go xs ys) where
  go [] ys = ys
  go xs [] = xs
  go xx@((dx, vx):xs) yy@((dy, vy):ys)
    | dx < dy   = (dx, vx)      : go xs yy
    | dx > dy   = (dy, vy)      : go xx ys
    | otherwise = (dx, vx + vy) : go xs ys

它基本上是您所拥有的核心，但要简单得多。通常，如果您可以在 Haskell 中使计算变得惰性，那么值得付出努力，因为它可能更有效。在此之后，我们将积累

accum :: Num a => Model a -> Model a
accum (Variant xs) = Variant (go xs 0) where
  go []          _ = []
  go ((d, v):xs) c = let c' = v + c in (d, c') : go xs c'

然后将这两者结合起来，我们得到了想要的结果

-- (&+) :: Num a => Model a -> Model a -> Model a
-- a &+ b = accum (merge a b)

不过，离开 merge 可能会更好。和 accum作为公开的 API，因为它们可以通过多种方式组合，而不仅仅是 (&+) .

可能值得注意的是，写 accum 的明显方式用作右折叠

accum' :: Num a => Model a -> Model a
accum' (Variant xs) = Variant (snd $ foldr go (0, []) xs) where
  go (d, v) (c, res) = let c' = v + c in (c', (d, c'):res)

不起作用，因为它从列表的后面累积参数。尝试左折叠是可行的，但我们必须颠倒列表——这是对懒惰的双重罪过。

accum'' :: Num a => Model a -> Model a
accum'' (Variant xs) = Variant (reverse $ snd $ foldl go (0, []) xs) where
  go (d, v) (c, res) = let c' = v + c in (c', (d, c'):res)

这暗示了原始版本中发生的事情。然而，我们可以把它写成一个正确的折叠，但是我们必须有点棘手才能让累加器在正确的方向上传递

accum' :: Num a => Model a -> Model a
accum' (Variant xs) = Variant (foldr go (const []) xs 0) where
  go (d, v) rest c = let c' = v + c in (d, c') : rest c'

注意这里 foldr go (const []) xs 的结果是 a -> [a] 类型的值.