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

Question

基本上,我会把它描述为一个联合/合并[(,)]与一对正在运行的累加器snd......这是否有一种优雅的方式来实现它？

(请仅在回答问题的上下文中引用我的代码.如果您想查看我的代码,那也会很棒,但请在其他网站上执行此操作:https://codereview.stackexchange.com/questions/54993 /合并时间序列)

时间序列,

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

...其中type ain [(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].