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

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.

Answer 2

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