tuple-gen 1.0 → 1.1
raw patch · 2 files changed
+151/−29 lines, 2 files
Files
- src/Data/Tuple/Gen.hs +150/−28
- tuple-gen.cabal +1/−1
src/Data/Tuple/Gen.hs view
@@ -1,52 +1,53 @@ module Data.Tuple.Gen(all2s, all3s, all4s, all5s, all6s, all7s, all8s, all9s, all10s, - all2sFrom, all3sFrom, all4sFrom, all5sFrom, all6sFrom, all7sFrom, all8sFrom, all9sFrom, all10sFrom) + all2sFrom, all3sFrom, all4sFrom, all5sFrom, all6sFrom, all7sFrom, all8sFrom, all9sFrom, all10sFrom, + T2,T3,T4,T5,T6,T7,T8,T9,T10) where -- | generate all 2-tuples so that the sum of all digits is monotonic increasing -all2s :: Integral a => [(a,a)] -all2s = all2sFrom (1,0) +all2s :: Num a => [(a,a)] +all2s = (0,0) : (all2sFrom (1,0)) -- | generate all 3-tuples so that the sum of all digits is monotonic increasing -all3s :: Integral a => [(a,a,a)] -all3s = all3sFrom (1,0,0) +all3s :: Num a => [(a,a,a)] +all3s = (0,0,0) : (all3sFrom (1,0,0)) -- | generate all 4-tuples so that the sum of all digits is monotonic increasing -all4s :: Integral a => [(a,a,a,a)] -all4s = all4sFrom (1,0,0,0) +all4s :: Num a => [(a,a,a,a)] +all4s = (0,0,0,0) : (all4sFrom (1,0,0,0)) -- | generate all 5-tuples so that the sum of all digits is monotonic increasing -all5s :: Integral a => [(a,a,a,a,a)] -all5s = all5sFrom (1,0,0,0,0) +all5s :: Num a => [(a,a,a,a,a)] +all5s = (0,0,0,0,0) : (all5sFrom (1,0,0,0,0)) -- | generate all 6-tuples so that the sum of all digits is monotonic increasing -all6s :: Integral a => [(a,a,a,a,a,a)] -all6s = all6sFrom (1,0,0,0,0,0) +all6s :: Num a => [(a,a,a,a,a,a)] +all6s = (0,0,0,0,0,0) : (all6sFrom (1,0,0,0,0,0)) -- | generate all 7-tuples so that the sum of all digits is monotonic increasing -all7s :: Integral a => [(a,a,a,a,a,a,a)] -all7s = all7sFrom (1,0,0,0,0,0,0) +all7s :: Num a => [(a,a,a,a,a,a,a)] +all7s = (0,0,0,0,0,0,0) : (all7sFrom (1,0,0,0,0,0,0)) -- | generate all 8-tuples so that the sum of all digits is monotonic increasing -all8s :: Integral a => [(a,a,a,a,a,a,a,a)] -all8s = all8sFrom (1,0,0,0,0,0,0,0) +all8s :: Num a => [(a,a,a,a,a,a,a,a)] +all8s = (0,0,0,0,0,0,0,0) : (all8sFrom (1,0,0,0,0,0,0,0)) -- | generate all 9-tuples so that the sum of all digits is monotonic increasing -all9s :: Integral a => [(a,a,a,a,a,a,a,a,a)] -all9s = all9sFrom (1,0,0,0,0,0,0,0,0) +all9s :: Num a => [(a,a,a,a,a,a,a,a,a)] +all9s = (0,0,0,0,0,0,0,0,0) : (all9sFrom (1,0,0,0,0,0,0,0,0)) -- | generate all 10-tuples so that the sum of all digits is monotonic increasing -all10s :: Integral a => [(a,a,a,a,a,a,a,a,a,a)] -all10s = all10sFrom (1,0,0,0,0,0,0,0,0,0) +all10s :: Num a => [(a,a,a,a,a,a,a,a,a,a)] +all10s = (0,0,0,0,0,0,0,0,0,0) : (all10sFrom (1,0,0,0,0,0,0,0,0,0)) -all2sFrom :: Integral a => (a,a) -> [(a,a)] +all2sFrom :: Num a => (a,a) -> [(a,a)] all2sFrom start = s_A [start] where s_A ((a,b):is) = (a,b) : (s_B ((a-1,b+1):is)) s_B ((0,b):is) = (0,b) : (s_A ((b+1, 0 ):is)) s_B ((a,b):is) = (a,b) : (s_B ((a-1,b+1):is)) -all3sFrom :: Integral a => (a,a,a) -> [(a,a,a)] +all3sFrom :: Num a => (a,a,a) -> [(a,a,a)] all3sFrom start = s_A [start] where s_A ((a,b,c):is) = (a,b,c) : (s_B ((a-1,b+1,c):is)) @@ -55,7 +56,7 @@ s_C ((a,0,c):is) = (a,0,c) : (s_B ((a-1,c+1,0):is)) s_C ((a,b,c):is) = (a,b,c) : (s_C ((a,b-1,c+1):is)) -all4sFrom :: Integral a => (a,a,a,a) -> [(a,a,a,a)] +all4sFrom :: Num a => (a,a,a,a) -> [(a,a,a,a)] all4sFrom start = s_A [start] where s_A ((a,b,c,d):is) = (a,b,c,d) : (s_B ((a-1,b+1,c,d):is)) @@ -66,7 +67,7 @@ s_D ((a,b,0,d):is) = (a,b,0,d) : (s_C ((a,b-1,d+1,0):is)) s_D ((a,b,c,d):is) = (a,b,c,d) : (s_D ((a,b,c-1,d+1):is)) -all5sFrom :: Integral a => (a,a,a,a,a) -> [(a,a,a,a,a)] +all5sFrom :: Num a => (a,a,a,a,a) -> [(a,a,a,a,a)] all5sFrom start = s_A [start] where s_A ((a,b,c,d,e):is) = (a,b,c,d,e) : (s_B ((a-1,b+1,c,d,e):is)) @@ -79,7 +80,7 @@ s_E ((a,b,c,0,e):is) = (a,b,c,0,e) : (s_D ((a,b,c-1,e+1,0):is)) s_E ((a,b,c,d,e):is) = (a,b,c,d,e) : (s_E ((a,b,c,d-1,e+1):is)) -all6sFrom :: Integral a => (a,a,a,a,a,a) -> [(a,a,a,a,a,a)] +all6sFrom :: Num a => (a,a,a,a,a,a) -> [(a,a,a,a,a,a)] all6sFrom start = s_A [start] where s_A ((a,b,c,d,e,f):is) = (a,b,c,d,e,f) : (s_B ((a-1,b+1,c,d,e,f):is)) @@ -94,7 +95,7 @@ s_F ((a,b,c,d,0,f):is) = (a,b,c,d,0,f) : (s_E ((a,b,c,d-1,f+1,0):is)) s_F ((a,b,c,d,e,f):is) = (a,b,c,d,e,f) : (s_F ((a,b,c,d,e-1,f+1):is)) -all7sFrom :: Integral a => (a,a,a,a,a,a,a) -> [(a,a,a,a,a,a,a)] +all7sFrom :: Num a => (a,a,a,a,a,a,a) -> [(a,a,a,a,a,a,a)] all7sFrom start = s_A [start] where s_A ((a,b,c,d,e,f,g):is) = (a,b,c,d,e,f,g) : (s_B ((a-1,b+1,c,d,e,f,g):is)) @@ -111,7 +112,7 @@ s_G ((a,b,c,d,e,0,g):is) = (a,b,c,d,e,0,g) : (s_F ((a,b,c,d,e-1,g+1,0):is)) s_G ((a,b,c,d,e,f,g):is) = (a,b,c,d,e,f,g) : (s_G ((a,b,c,d,e,f-1,g+1):is)) -all8sFrom :: Integral a => (a,a,a,a,a,a,a,a) -> [(a,a,a,a,a,a,a,a)] +all8sFrom :: Num a => (a,a,a,a,a,a,a,a) -> [(a,a,a,a,a,a,a,a)] all8sFrom start = s_A [start] where s_A ((a,b,c,d,e,f,g,h):is) = (a,b,c,d,e,f,g,h) : (s_B ((a-1,b+1,c,d,e,f,g,h):is)) @@ -130,7 +131,7 @@ s_H ((a,b,c,d,e,f,0,h):is) = (a,b,c,d,e,f,0,h) : (s_G ((a,b,c,d,e,f-1,h+1,0):is)) s_H ((a,b,c,d,e,f,g,h):is) = (a,b,c,d,e,f,g,h) : (s_H ((a,b,c,d,e,f,g-1,h+1):is)) -all9sFrom :: Integral a => (a,a,a,a,a,a,a,a,a) -> [(a,a,a,a,a,a,a,a,a)] +all9sFrom :: Num a => (a,a,a,a,a,a,a,a,a) -> [(a,a,a,a,a,a,a,a,a)] all9sFrom start = s_A [start] where s_A ((a,b,c,d,e,f,g,h,i):is) = (a,b,c,d,e,f,g,h,i) : (s_B ((a-1,b+1,c,d,e,f,g,h,i):is)) @@ -151,7 +152,7 @@ s_I ((a,b,c,d,e,f,g,0,i):is) = (a,b,c,d,e,f,g,0,i) : (s_H ((a,b,c,d,e,f,g-1,i+1,0):is)) s_I ((a,b,c,d,e,f,g,h,i):is) = (a,b,c,d,e,f,g,h,i) : (s_I ((a,b,c,d,e,f,g,h-1,i+1):is)) -all10sFrom :: Integral a => (a,a,a,a,a,a,a,a,a,a) -> [(a,a,a,a,a,a,a,a,a,a)] +all10sFrom :: Num a => (a,a,a,a,a,a,a,a,a,a) -> [(a,a,a,a,a,a,a,a,a,a)] all10sFrom start = s_A [start] where s_A ((a,b,c,d,e,f,g,h,i,j):is) = (a,b,c,d,e,f,g,h,i,j) : (s_B ((a-1,b+1,c,d,e,f,g,h,i,j):is)) @@ -173,3 +174,124 @@ s_J ((a,b,c,d,e,f,g,0,0,j):is) = (a,b,c,d,e,f,g,0,0,j) : (s_H ((a,b,c,d,e,f,g-1,j+1,0,0):is)) s_J ((a,b,c,d,e,f,g,h,0,j):is) = (a,b,c,d,e,f,g,h,0,j) : (s_I ((a,b,c,d,e,f,g,h-1,j+1,0):is)) s_J ((a,b,c,d,e,f,g,h,i,j):is) = (a,b,c,d,e,f,g,h,i,j) : (s_J ((a,b,c,d,e,f,g,h,i-1,j+1):is)) + +-- data structures for Eq and Ord instances +-- to make the upper enumeration into an ordering + +data T2 a = T2 (a,a) deriving Show +data T3 a = T3 (a,a,a) deriving Show +data T4 a = T4 (a,a,a,a) deriving Show +data T5 a = T5 (a,a,a,a,a) deriving Show +data T6 a = T6 (a,a,a,a,a,a) deriving Show +data T7 a = T7 (a,a,a,a,a,a,a) deriving Show +data T8 a = T8 (a,a,a,a,a,a,a,a) deriving Show +data T9 a = T9 (a,a,a,a,a,a,a,a,a) deriving Show +data T10 a = T10 (a,a,a,a,a,a,a,a,a,a) deriving Show + +instance Eq a => Eq (T2 a) where + (T2 (x0,x1)) == (T2 (y0,y1)) = x0==y0 && x1==y1 + +instance Eq a => Eq (T3 a) where + (T3 (x0,x1,x2)) == (T3 (y0,y1,y2)) = x0==y0 && x1==y1 && x2==y2 + +instance Eq a => Eq (T4 a) where + (T4 (x0,x1,x2,x3)) == (T4 (y0,y1,y2,y3)) = x0==y0 && x1==y1 && x2==y2 && x3==y3 + +instance Eq a => Eq (T5 a) where + (T5 (x0,x1,x2,x3,x4)) == (T5 (y0,y1,y2,y3,y4)) = x0==y0 && x1==y1 && x2==y2 && x3==y3 && x4==y4 + +instance Eq a => Eq (T6 a) where + (T6 (x0,x1,x2,x3,x4,x5)) == (T6 (y0,y1,y2,y3,y4,y5)) = x0==y0 && x1==y1 && x2==y2 && x3==y3 && x4==y4 && x5==y5 + +instance Eq a => Eq (T7 a) where + (T7 (x0,x1,x2,x3,x4,x5,x6)) == (T7 (y0,y1,y2,y3,y4,y5,y6)) = x0==y0 && x1==y1 && x2==y2 && x3==y3 && x4==y4 && x5==y5 && x6==y6 + +instance Eq a => Eq (T8 a) where + (T8 (x0,x1,x2,x3,x4,x5,x6,x7)) == (T8 (y0,y1,y2,y3,y4,y5,y6,y7)) = x0==y0 && x1==y1 && x2==y2 && x3==y3 && x4==y4 && x5==y5 && x6==y6 && x7==y7 + +instance Eq a => Eq (T9 a) where + (T9 (x0,x1,x2,x3,x4,x5,x6,x7,x8)) == (T9 (y0,y1,y2,y3,y4,y5,y6,y7,y8)) = x0==y0 && x1==y1 && x2==y2 && x3==y3 && x4==y4 && x5==y5 && x6==y6 && x7==y7 && x8==y8 + +instance Eq a => Eq (T10 a) where + (T10 (x0,x1,x2,x3,x4,x5,x6,x7,x8,x9)) == (T10 (y0,y1,y2,y3,y4,y5,y6,y7,y8,y9)) = x0==y0 && x1==y1 && x2==y2 && x3==y3 && x4==y4 && x5==y5 && x6==y6 && x7==y7 && x8==y8 && x9==y9 + + +instance (Eq a,Ord a,Num a) => Ord (T2 a) where + (T2 (x0,x1)) <= (T2 (y0,y1)) = (x0+x1) <= (y0+y1) && (x0 > y0 || + (x0 == y0 && x1 > y1)) + +instance (Eq a,Ord a,Num a) => Ord (T3 a) where + (T3 (x0,x1,x2)) <= (T3 (y0,y1,y2)) = (x0+x1+x2) <= (y0+y1+y2) && + (x0 > y0 || + (x0 == y0 && x1 > y1) || + (x0 == y0 && x1 == y1 && x2 > y2)) + +instance (Eq a,Ord a,Num a) => Ord (T4 a) where + (T4 (x0,x1,x2,x3)) <= (T4 (y0,y1,y2,y3)) = (x0+x1+x2+x3) <= (y0+y1+y2+y3) && + (x0 > y0 || + (x0 == y0 && x1 > y1) || + (x0 == y0 && x1 == y1 && x2 > y2) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 > y3)) + +instance (Eq a,Ord a,Num a) => Ord (T5 a) where + (T5 (x0,x1,x2,x3,x4)) <= (T5 (y0,y1,y2,y3,y4)) = (x0+x1+x2+x3+x4) <= (y0+y1+y2+y3+y4) && + (x0 > y0 || + (x0 == y0 && x1 > y1) || + (x0 == y0 && x1 == y1 && x2 > y2) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 > y3) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 > y4)) + +instance (Eq a,Ord a,Num a) => Ord (T6 a) where + (T6 (x0,x1,x2,x3,x4,x5)) <= (T6 (y0,y1,y2,y3,y4,y5)) = (x0+x1+x2+x3+x4+x5) <= (y0+y1+y2+y3+y4+y5) && + (x0 > y0 || + (x0 == y0 && x1 > y1) || + (x0 == y0 && x1 == y1 && x2 > y2) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 > y3) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 > y4) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 > y5)) + +instance (Eq a,Ord a,Num a) => Ord (T7 a) where + (T7 (x0,x1,x2,x3,x4,x5,x6)) <= (T7 (y0,y1,y2,y3,y4,y5,y6)) = (x0+x1+x2+x3+x4+x5+x6) <= (y0+y1+y2+y3+y4+y5+y6) && + (x0 > y0 || + (x0 == y0 && x1 > y1) || + (x0 == y0 && x1 == y1 && x2 > y2) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 > y3) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 > y4) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 > y5) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 > y6)) + +instance (Eq a,Ord a,Num a) => Ord (T8 a) where + (T8 (x0,x1,x2,x3,x4,x5,x6,x7)) <= (T8 (y0,y1,y2,y3,y4,y5,y6,y7)) = (x0+x1+x2+x3+x4+x5+x6+x7) <= (y0+y1+y2+y3+y4+y5+y6+y7) && + (x0 > y0 || + (x0 == y0 && x1 > y1) || + (x0 == y0 && x1 == y1 && x2 > y2) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 > y3) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 > y4) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 > y5) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 > y6) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 == y6 && x7 > y7)) + +instance (Eq a,Ord a,Num a) => Ord (T9 a) where + (T9 (x0,x1,x2,x3,x4,x5,x6,x7,x8)) <= (T9 (y0,y1,y2,y3,y4,y5,y6,y7,y8)) = (x0+x1+x2+x3+x4+x5+x6+x7+x8) <= (y0+y1+y2+y3+y4+y5+y6+y7+y8) && + (x0 > y0 || + (x0 == y0 && x1 > y1) || + (x0 == y0 && x1 == y1 && x2 > y2) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 > y3) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 > y4) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 > y5) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 > y6) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 == y6 && x7 > y7) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 == y6 && x7 == y7 && x8 > y8)) + +instance (Eq a,Ord a,Num a) => Ord (T10 a) where + (T10 (x0,x1,x2,x3,x4,x5,x6,x7,x8,x9)) <= (T10 (y0,y1,y2,y3,y4,y5,y6,y7,y8,y9)) = (x0+x1+x2+x3+x4+x5+x6+x7+x8+x9) <= (y0+y1+y2+y3+y4+y5+y6+y7+y8+y9) && + (x0 > y0 || + (x0 == y0 && x1 > y1) || + (x0 == y0 && x1 == y1 && x2 > y2) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 > y3) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 > y4) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 > y5) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 > y6) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 == y6 && x7 > y7) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 == y6 && x7 == y7 && x8 > y8) || + (x0 == y0 && x1 == y1 && x2 == y2 && x3 == y3 && x4 == y4 && x5 == y5 && x6 == y6 && x7 == y7 && x8 == y8 && x9 > y9))
tuple-gen.cabal view
@@ -1,5 +1,5 @@ Name: tuple-gen -Version: 1.0 +Version: 1.1 Synopsis: Generating all n-tuples without getting stuck in one infinity Description: Generating tuples like this: [(x, y) | x <- [1..], y <- [1..]] generates tuples that change only in the second position. This library uses an automata to generate all tuples whose sum of digits is constant. This constant is increased and thereby all tuples are generated. category: Data