Safe Haskell | Safe-Inferred |
---|

"Sieves" by Iannis Xenakis and John Rahn
*Perspectives of New Music*
Vol. 28, No. 1 (Winter, 1990), pp. 58-78

- type I = Integer
- data Sieve
- union :: [Sieve] -> Sieve
- intersection :: [Sieve] -> Sieve
- (∪) :: Sieve -> Sieve -> Sieve
- (∩) :: Sieve -> Sieve -> Sieve
- l :: I -> I -> Sieve
- (⋄) :: I -> I -> Sieve
- normalise :: Sieve -> Sieve
- is_normal :: Sieve -> Bool
- element :: Sieve -> I -> Bool
- build :: Sieve -> [I]
- buildn :: Int -> Sieve -> [I]
- differentiate :: Num a => [a] -> [a]
- euclid :: Integral a => a -> a -> a
- de_meziriac :: Integral a => a -> a -> a
- reduce_intersection :: Integral t => (t, t) -> (t, t) -> Maybe (t, t)
- reduce :: Sieve -> Sieve

# Documentation

A Sieve.

intersection :: [Sieve] -> SieveSource

The `Intersection`

of a list of `Sieve`

s, ie. `foldl1`

`Intersection`

.

is_normal :: Sieve -> BoolSource

Predicate to test if a `Sieve`

is *normal*.

is_normal (L (15,4)) == True

Construct the sequence defined by a `Sieve`

. Note that building
a sieve that contains an intersection clause that has no elements
gives `_|_`

.

let d = [0,2,4,5,7,9,11] in take 7 (build (union (map (l 12) d))) == d

buildn :: Int -> Sieve -> [I]Source

Variant of `build`

that gives the first *n* places of the
`reduce`

of `Sieve`

.

buildn 6 (union (map (l 8) [0,3,6])) == [0,3,6,8,11,14] buildn 12 (L (3,2)) == [2,5,8,11,14,17,20,23,26,29,32,35] buildn 9 (L (8,0)) == [0,8,16,24,32,40,48,56,64] buildn 3 (L (3,2) ∩ L (8,0)) == [8,32,56] buildn 12 (L (3,1) ∪ L (4,0)) == [0,1,4,7,8,10,12,13,16,19,20,22] buildn 14 (5⋄4 ∪ 3⋄2 ∪ 7⋄3) == [2,3,4,5,8,9,10,11,14,17,19,20,23,24] buildn 6 (3⋄0 ∪ 4⋄0) == [0,3,4,6,8,9] buildn 8 (5⋄2 ∩ 2⋄0 ∪ 7⋄3) == [2,3,10,12,17,22,24,31] buildn 12 (5⋄1 ∪ 7⋄2) == [1,2,6,9,11,16,21,23,26,30,31,36]

buildn 10 (3⋄2 ∩ 4⋄7 ∪ 6⋄9 ∩ 15⋄18) == [3,11,23,33,35,47,59,63,71,83]

let s = 3⋄2∩4⋄7∩6⋄11∩8⋄7 ∪ 6⋄9∩15⋄18 ∪ 13⋄5∩8⋄6∩4⋄2 ∪ 6⋄9∩15⋄19 in buildn 16 s == buildn 16 (24⋄23 ∪ 30⋄3 ∪ 104⋄70)

buildn 10 (24⋄23 ∪ 30⋄3 ∪ 104⋄70) == [3,23,33,47,63,70,71,93,95,119]

differentiate :: Num a => [a] -> [a]Source

Standard differentiation function.

differentiate [1,3,6,10] == [2,3,4] differentiate [0,2,4,5,7,9,11,12] == [2,2,1,2,2,2,1]

euclid :: Integral a => a -> a -> aSource

Euclid's algorithm for computing the greatest common divisor.

euclid 1989 867 == 51

de_meziriac :: Integral a => a -> a -> aSource

Bachet De Méziriac's algorithm.

de_meziriac 15 4 == 3 && euclid 15 4 == 1

reduce_intersection :: Integral t => (t, t) -> (t, t) -> Maybe (t, t)Source

Attempt to reduce the `Intersection`

of two `L`

nodes to a
singular `L`

node.

reduce_intersection (3,2) (4,7) == Just (12,11) reduce_intersection (12,11) (6,11) == Just (12,11) reduce_intersection (12,11) (8,7) == Just (24,23)

reduce :: Sieve -> SieveSource

Reduce the number of nodes at a `Sieve`

.

reduce (L (3,2) ∪ Empty) == L (3,2) reduce (L (3,2) ∩ Empty) == L (3,2) reduce (L (3,2) ∩ L (4,7)) == L (12,11) reduce (L (6,9) ∩ L (15,18)) == L (30,3)

let s = 3⋄2∩4⋄7∩6⋄11∩8⋄7 ∪ 6⋄9∩15⋄18 ∪ 13⋄5∩8⋄6∩4⋄2 ∪ 6⋄9∩15⋄19 in reduce s == (24⋄23 ∪ 30⋄3 ∪ 104⋄70)

let s = 3⋄2∩4⋄7∩6⋄11∩8⋄7 ∪ 6⋄9∩15⋄18 ∪ 13⋄5∩8⋄6∩4⋄2 ∪ 6⋄9∩15⋄19 in reduce s == (24⋄23 ∪ 30⋄3 ∪ 104⋄70)