求和函數式編程

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

求和函數式編程

回答

相關問題