函数式编程中的求和

Question

我正在网上搜索排除-包含原理，找到的是这个： _{(来源：MathWorld - Wolfram Web 资源: wolfram.com)}

http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html

如果您不理解这个公式也没关系，实际上我需要的是将其实现：

例如，输入为：

(summation (list 1 2) 3) 其中 (list 1 2) 是 i 和 j，3 是求和上限 n。

(n 应该在 sigma 上面但是...)

那么，在 Scheme 中公式的输出将为：

(list (list 1 2) (list 1 3) (list 2 3))

我该如何在 Scheme 或 Haskell 中实现这个？（对我的英语表示抱歉）。

- Carlochess

---

你的第二个公式末尾的悬空的 + 符号是什么意思？它应该在那里吗？ - Tarrasch

从大公式中剪切出的剩余部分。 - Daniel Fischer

我有点困惑。显然，您希望函数的结果是一个列表，但您给出的公式计算的是一个数字，而不是一个列表（或集合）。 - sepp2k

@sepp2k 是的，那些是某个集合中的数字。如果解决方案是（...（列表1 2）..），那么我认为1代表A，2代表B。谢谢询问。 - Carlochess

Daniel Fischer的答案应该被接受。其他两个得票最高的答案没有计算重叠集合的并集长度，而这正是问题所涉及到的容斥原理，也没有计算一组集合的成对交集的长度之和，这是问题中明确提出的更具体的子问题。 - Will Ness

Answer 1

在Haskell中，可以使用列表推导式：

Prelude> [(i,j) | i <- [1..4], j <- [i+1..4]]
[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
Prelude> [i * j | i <- [1..4], j <- [i+1..4]]
[2,3,4,6,8,12]
Prelude> sum [i * j | i <- [1..4], j <- [i+1..4]]
35

第一行列出了所有满足 1 <= i < j <= 4 的 (i,j) 对。

第二行给出了一个列表，其中包含 1 <= i < j <= 4 时的 i*j。

第三行给出了这些值的总和：Σ_{1 <= i < j <= 4} i*j。

- sdcvvc

Answer 2

在Racket中，您可能会使用列表推导式：

#lang racket

(for*/sum ([i (in-range 1 5)]
           [j (in-range (add1 i) 5)])
    (* i j))

- John Clements

Answer 3

实现容斥原理的简单方法是生成索引集合中所有k元素子集所需的核心功能。使用列表，这是一个简单的递归：

pick :: Int -> [a] -> [[a]]
pick 0 _    = [[]]    -- There is exactly one 0-element subset of any set
pick _ []   = []      -- No way to pick any nonzero number of elements from an empty set
pick k (x:xs) = map (x:) (pick (k-1) xs) ++ pick k xs
    -- There are two groups of k-element subsets of a set containing x,
    -- those that contain x and those that do not

如果pick不是一个完全在您控制之下的本地函数，您应该添加一个检查，确保Int参数永远不会为负数（您可以使用Word作为该参数，因为这已经内置于类型中）。 如果k很大，检查要从列表中选择的长度可以避免许多无用的递归，因此最好从一开始就将其构建进去：

pick :: Int -> [a] -> [[a]]
pick k xs = choose k (length xs) xs

choose :: Int -> Int -> [a] -> [[a]]
choose 0 _ _     = [[]]
choose k l xs
    | l < k      = []    -- we want to choose more than we have
    | l == k     = [xs]  -- we want exactly as many as we have
    | otherwise  = case xs of
                     [] -> error "This ought to be impossible, l == length xs should hold"
                     (y:ys) -> map (y:) (choose (k-1) (l-1) ys) ++ choose k (l-1) ys

包含排除公式则变为：

inclusionExclusion indices
    = sum . zipWith (*) (cycle [1,-1]) $
        [sum (map count $ pick k indices) | k <- [1 .. length indices]]

count list是计算[subset i | i <- list]交集元素数量的函数。当然，你需要一种高效的方法来计算它，否则直接查找并计算并集大小会更有效。

优化空间很大，有不同的方法可以做到这一点，但这是一个相当简短和直接的原则翻译。

- Daniel Fischer

---

这应该是被接受的答案。FYI，“子集i”表示问题中公式中的“A_i”（在容斥原理中，它们都是一个更大的集合的子集）。 - Will Ness

Answer 4

这是一个可能的 Scheme 实现方式。我已经创建了以下函数来创建量化。

#lang racket

(define (quantification next test op e)
  {lambda (A B f-terme)
    (let loop ([i A] [resultat e])
      (if [test i B] 
          resultat 
          (loop (next i) (op (f-terme i) resultat)) ))})

使用此函数，您可以创建总和、乘积、广义并集和广义交集。

;; Arithmetic example
(define sumQ (quantification add1 > + 0))
(define productQ (quantification add1 > * 1))

;; Sets example with (require 
(define (unionQ set-of-sets) 
  (let [(empty-set (set))
        (list-of-sets (set->list set-of-sets))
        ]
    ((quantification cdr eq? set-union empty-set) list-of-sets
                                                  '() 
                                                  car)))
(define (intersectionQ set-of-sets) 
  (let [(empty-set (set))
        (list-of-sets (set->list set-of-sets))
        ]
    ((quantification cdr eq? set-intersect (car list-of-sets)) (cdr list-of-sets)
                                                               '() 
                                                               car)))

这样你就可以做到

(define setA2 (set 'a 'b))
(define setA5 (set 'a 'b 'c 'd 'e))
(define setC3 (set 'c 'd 'e))
(define setE3 (set 'e 'f 'g))
(unionQ (set setA2 setC3 setE3))
(intersectionQ (set setA5 setC3 setE3))

我在Haskell上做类似的事情

module Quantification where

quantifier next test op = 
    let loop e a b f = if (test a b) 
                       then e 
                       else loop (op (f a) e) (next a) b f 
    in loop

quantifier_on_integer_set = quantifier (+1) (>)
sumq = quantifier_on_integer_set (+) 0
prodq = quantifier_on_integer_set (*) 1

但我从来没有深入研究过... 可能你可以从这里开始。

- Benoît Fraikin