Суммирование в функциональном программировании

Question

Я искал в Интернете принцип исключения-включения, я нашел следующее:

Формула http://mathworld.wolfram.com/images/equations/Inclusion-ExclusionPrinciple/NumberedEquation3.gif

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

Я не знаюне имеет значения, если вы не понимаете формулу, на самом деле, мне нужно реализовать это:

Например, ввод:

(summation (list 1 2) 3) Где (список 1 2) - это i, а j и 3 - это предел суммы n.

(n должно быть до сигмы, но ...)

Тогда результат формулы в Схеме будет:

(список (список 1 2) (список 1 3) (список 2 3))

Как я могу реализовать это в схеме или в Haskell?(извините за мой английский).

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

В первой строке представлен список всех пар (i, j), где 1 <= i <j <= 4 </p>

Вторая строка дает список i * j, где 1 <= i <j <= 4 </p>

Третья строка дает сумму этих значений: Σ _{1 <= i <j <= 4} i* к.</sub>

Answer 2

В ракетке вы, вероятно, использовали бы понимание списка:

#lang racket

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

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 не является локальной функцией, вызовы которой находятся на 100% под вашим контролем, вы должны добавить проверку, что параметр 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].Конечно, вам нужен эффективный способ для вычисления этого, иначе было бы более эффективно определить размер объединения напрямую.

Существует много возможностей для оптимизации, и есть разные способы сделать это, но этодовольно короткий и прямой перевод принципа.

Answer 4

Вот возможный способ со Схемой. Я сделал следующую функцию для создания количественного определения

#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

Но я никогда не пойду дальше ... Вероятно, вы можете начать с этого, однако.