Summation in functional programming

Question

I was searching in the web for exclusion-Inclusion principle, what i have found is this:

_{(from MathWorld - A Wolfram Web Resource: wolfram.com)}

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

I doesn't matter if you don't understand the formula, in fact, what i need is to implement this:

For example, the input is:

(summation (list 1 2) 3) Where (list 1 2) is i and j and 3 is the limit of the sum n.

(n had to be up the sigma but...)

Then, the output of formula, in Scheme will be:

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

How can i implemment this in Scheme or in Haskell? (sorry for my English).

Answer 1

Here is a possible way with Scheme. I've made the following function to create quantification

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

With this function you can create sum, product, generalized union and generalized intersection.

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

This way you can do

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

I work on something similar in 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

But I never go further... Probably that you can start from this however.

Answer 2

The core functionality you need for a simple implementation of the inclusion-exclusion principle is to generate all k-element subsets of the index set. Using lists, that is an easy recursion:

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

If pick is not a local function whose calls are 100% under your control, you should add a check that the Int parameter is never negative (you could use Word for that parameter, then that's built into the type). If k is largish, checking against the length of the list to pick from prevents a lot of fruitless recursion, so it's better to build that in from the start:

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

The inclusion-exclusion formula then becomes

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

where count list counts the number of elements of the intersection of [subset i | i <- list]. Of course, you need an efficient way to calculate that, or it would be more efficient to find the size of the union directly.

There's much room for optimisation, and there are different ways to do it, but that's a fairly short and direct translation of the principle.

Answer 3

In racket, you'd probably use a list comprehension:

#lang racket

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

Answer 4

In Haskell, use a list comprehension:

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

First line gives all a list of all pairs (i,j) where 1 <= i < j <= 4

Second line gives a list of i*j where 1 <= i < j <= 4

Third line gives sum of these values: Σ_{1 <= i < j <= 4} i*j.