求和函数式编程

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 <Ĵ< = 4

第二行给出我的列表* j，其中1 < = I <Ĵ< = 4

第三行给出这些值的总和：Σ = I < j < = 4 i * j。

来源

2011-11-03 21:25:33 sdcvvc

在拍，你可能会使用列表理解：

#lang racket 

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

来源

2011-11-03 21:30:33

你需要一个简单实现的容斥原理的核心功能是生成索引集的所有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]。当然，你需要一种有效的方法来计算，或者直接找到联合的大小会更有效率。

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

来源

2011-11-03 22:52:19

以下是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))))})

使用此功能，您可以创建sum，product，generalized union和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)))

这样你就可以做

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

我在哈斯克尔

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

类似的工作，但我从来没有走得更远......可能是你可以从这个然而开始。

来源

2011-11-04 02:37:40

求和函数式编程

回答

相关问题