Haskell：如何多次向右滑动求和求和？

Question

在回答一个我没能解释清楚，但由于它的大纲和解决方案被认为有用的问题，列表被右移了一次，并且在这个列表和之间使用了加法最初的一个，产生这样的输出：

[1,2] -> [1,3,2]
[1,2,3] -> [1,3,5,3]
[1,2,3,4] -> [1,3,5,7,4]

这是我根据需要重写的答案，如下所示：

slideSum :: [Integer] -> [Integer]

slideSum l = slideRight l []
  where
    slideRight [] a = a
    slideRight (x:[]) a = (x:a)
    slideRight (x:y:zs) a = slideLeft (x:a) (slideRight (sum (x:y:a):a) (slideLeft (y:zs) a))
      where
        slideLeft [] a = a
        slideLeft (x:[]) a = (x:a)
        slideLeft (x:y:zs) a = slideRight (sum (x:y:a):a) (slideLeft (y:zs) a)

它的作用是保持第一个和最后一个元素完整，对前两个和后面的对求和，为此我不得不左右移动。当我尝试为以下输出重写它时：

[1,2,3] -> [1,3,6,5,3] [1,2,3,4] -> [1,3,6,10,9,7,4]

也就是将第一个列表移位元素个数减一求和，我无法得出我认为自然的解决方案，因为我不得不通过删除一个元素来操纵两个较小表达式的结果。这是说明的问题：

  0:0:1:2:3:[]    
  0:1:2:3:0:[]    0:1:2:[]
  1:2:3:0:0:[]    1:2:0:[]
+ ------------  + --------
  1:3:6:5:3:[]    1:3:2:[]

这就是我操纵其结果的方式，我想避免这种情况：

slideSum :: [Integer] -> [Integer]
slideFromLeft :: [Integer] -> [Integer]
slideFromRight :: [Integer] -> [Integer]

slideFromLeft l = slideRight l []
  where
    slideRight [] a = a
    slideRight (x:[]) a = (x:a)
    slideRight (x:y:zs) a = slideRight (x:a) (slideRight (sum (x:y:a):zs) a)

slideFromRight l = slideLeft l []
  where
    slideLeft [] a = a
    slideLeft (x:[]) a = (x:a)
    slideLeft (x:y:zs) a = slideLeft (sum (x:y:zs):a) (slideLeft (y:zs) a)

slideSum l = slideFromLeft l ++ (tail slideFromRight l)

这个问题的性质是否需要不同的思考过程，或者需要将其问题拆分成更小部分的解决方案？你能滑动初始列表并通过将前者保留在内存中来产生不同的结果吗？

Answer 1

你想要的显然是

foo :: Num b => [b] -> [b]
foo xs = map sum . transpose . take n . map (take (n+n-1))
                 . map (++ repeat 0) . iterate (0:) $ xs
   where
   n = length xs

看到了吗？由于 Haskell 是惰性的，我们不关心是否添加了比实际需要更多的 0。最终都会通过惰性评估得到解决。

测试：

> foo [1..2]
[1,3,2]

> foo [1..3]
[1,3,6,5,3]

> foo [1..4]
[1,3,6,10,9,7,4]

我们可以通过丢弃 length 计算，使用 zipWith const 代替，

使其适当地成为非严格的，因此它也适用于无限列表

bar :: (Integral b) => [b] -> [b]
bar xs  =  map sum . zipWith take [1..]
                . transpose 
                . zipWith (const id) xs  
                . map (zipWith (const id) (xs ++ drop 1 xs))
                . map (++ repeat 0) . iterate (0:) $ xs

虽然所有这些 take，无论是明确的还是其他的，都让它看起来有点太忙了。

或者我们可以使用定义它的包之一中的 diagonals。

Haskell：如何多次向右滑动求和求和？

Haskell: how do you slide and sum a list to the right more than once?

haskell

sum

list

slide