Skip to content
This repository has been archived by the owner on Jun 4, 2021. It is now read-only.

Fix quadratic slowdown in Gen #62

Open
runarorama opened this issue Jun 18, 2020 · 0 comments
Open

Fix quadratic slowdown in Gen #62

runarorama opened this issue Jun 18, 2020 · 0 comments
Assignees

Comments

@runarorama
Copy link
Contributor

This replaces the test.Gen ability with a more direct encoding. Rather than going through Weighted (which has very poor asymptotics), this ability uses Stream:

ability Gen where
  generate : '{Stream (Either Nat a)} () ->{Gen} a

The convention is that a Nat emitted on the Left of the stream is a weight for the remainder of the stream. So in effect, the weight of any given element of the stream is the sum of all the weights that have been emitted before it.

Semantically equivalent to Weighted, with the exception that weights can be zero. This difference may slightly change the generated order of some existing generators after migrating to this new type.

Fixes #58 and #45

Included term and type replacements in patch to automatically migrate existing tests.

Code review

The changes summarized below are available for you to review, using the
following command:

pull-request.load https://github.com/unisonweb/base:.trunk https://github.com/runarorama/mybase:.newgen2

Updates:

 ability test.Gen

 ↓
 ability test.Gen
   +  unisoncomputing2020 : License
   +  Gen.doc             : Doc
   +  runarorama          : Author

 test.Gen.append : '{base.test.Gen} a
 -> '{base.test.Gen} a
 -> '{base.test.Gen} a
 ↓
 test.Gen.append : '{head.test.Gen} a
 -> '{head.test.Gen} a
 ->{head.test.Gen} a
 -  #b6pq28sm8m              : Doc
 +  unisoncomputing2020      : License
 +  pchiusano                : Author
 +  head.test.Gen.append.doc : Doc
 +  runarorama               : Author

 test.both : Test -> Test -> Test
 ↓
 test.both : Test -> Test -> Test
 +  unisoncomputing2020 : License
 +  runarorama          : Author

 test.gen.empty : '{base.test.Gen} a
 ↓
 test.gen.empty : '{head.test.Gen} a
 +  unisoncomputing2020 : License
 +  runarorama          : Author

 test.gen.int : '{base.test.Gen} Int
 ↓
 test.gen.int : '{head.test.Gen} Int
 +  unisoncomputing2020 : License
 +  runarorama          : Author

 test.gen.listOf : '{base.test.Gen} a -> '{base.test.Gen} [a]
 ↓
 test.gen.listOf : '{head.test.Gen} a -> '{head.test.Gen} [a]
 +  unisoncomputing2020 : License
 +  runarorama          : Author

 test.gen.nat : '{base.test.Gen} Nat
 ↓
 test.gen.nat : '{head.test.Gen} Nat
 +  unisoncomputing2020 : License
 +  runarorama          : Author

 test.gen.oneOf : [a] -> '{base.test.Gen} a
 ↓
 test.gen.oneOf : [a] -> '{head.test.Gen} a
 +  unisoncomputing2020 : License
 +  oneOf.doc           : Doc
 +  runarorama          : Author

 test.internals.v1.Test.run : Test -> [Result]
 ↓
 test.internals.v1.Test.run : Test -> [Result]

 test.run : Test -> [Result]
 ↓
 test.run : Test -> [Result]
 +  unisoncomputing2020 : License
 +  runarorama          : Author

 test.runs : Nat -> '{e, base.test.Gen} Test ->{e} [Result]
 ↓
 test.runs : Nat -> '{head.test.Gen} Test -> [Result]

 test.sample : Nat -> '{e, base.test.Gen} a ->{e} [a]
 ↓
 test.sample : Nat -> '{head.test.Gen} a -> [a]
 +  unisoncomputing2020 : License
 +  runarorama          : Author

 test.tests : [Test] -> Test
 ↓
 test.tests : [Test] -> Test
 +  unisoncomputing2020 : License
 +  runarorama          : Author

There were 208 auto-propagated updates.

 patch patch (added 12 updates)

Added definitions:

 test.Gen.generate                  : '{Stream (Either Nat a)} ()
                                    ->{head.test.Gen} a (+1 metadata)
 List.interleave                    : [a] -> [a] -> [a] (+3 metadata)
 List.interleave.doc                : Doc (+2 metadata)
 List.interleave.examples.ex1       : [Nat] (+2 metadata)
 List.interleave.examples.ex1.asDoc : Doc (+2 metadata)
 Stream.flatMap                     : (a -> '{e, Stream b} r)
                                    -> '{e, Stream a} r
                                    ->{e, Stream b} r (+2 metadata)
 ┌ test.Gen.<|>                     : '{head.test.Gen} a
                                    -> '{head.test.Gen} a
                                    -> '{head.test.Gen} a (+4 metadata)
 └ test.Gen.or                      : '{head.test.Gen} a
                                    -> '{head.test.Gen} a
                                    -> '{head.test.Gen} a (+4 metadata)
 test.Gen.addWeight                 : Nat ->{head.test.Gen} a (+3 metadata)
 test.Gen.addWeight.doc             : Doc (+2 metadata)
 test.Gen.doc                       : Doc (+2 metadata)
 test.Gen.examples.ex1              : [Nat] (+2 metadata)
 test.Gen.examples.ex2              : [[Nat]] (+2 metadata)
 test.Gen.fail                      : '{head.test.Gen} a (+3 metadata)
 test.Gen.fail.doc                  : Doc (+2 metadata)
 test.Gen.generate.doc              : Doc (+2 metadata)
 test.Gen.or.doc                    : Doc (+2 metadata)
 test.Gen.or.examples.ex1           : [Nat] (+2 metadata)
 test.Gen.or.examples.ex1.asDoc     : Doc (+2 metadata)
 test.Gen.or.tests.associative      : [Result] (+3 metadata)
 test.Gen.or.tests.unit             : [Result] (+3 metadata)
 test.Gen.toStream                  : '{head.test.Gen} a
                                    ->{Stream (Either Nat a)} () (+3 metadata)
 test.Gen.toStream.doc              : Doc (+2 metadata)
 test.Gen.weight                    : Nat
                                    -> '{head.test.Gen} a
                                    ->{head.test.Gen} a (+4 metadata)
 test.Gen.weight.doc                : Doc (+2 metadata)
 test.Gen.yield                     : a ->{head.test.Gen} a (+3 metadata)
 test.Gen.yield.doc                 : Doc (+2 metadata)
 ┌ test.check                       : Boolean -> [Result] (+1 metadata)
 └ test.internals.v1.Test.check     : Boolean -> [Result] (+1 metadata)
 test.internals.v2.<|>              : '{Stream (Either Nat x)} ()
                                    -> '{Stream (Either Nat x)} ()
                                    ->{Stream (Either Nat x)} () (+2 metadata)
 test.internals.v2.Test.report      : Test -> Report (+2 metadata)
 test.internals.v2.Test.untest      : Test -> Scope -> Report (+2 metadata)
 test.internals.v2.interleaveMap    : (x -> '{Stream (Either Nat y)} ())
                                    -> '{Stream (Either Nat x)} ()
                                    ->{Stream (Either Nat y)} () (+2 metadata)
 test.laws.monoid                   : '{head.test.Gen} a
                                    -> a
                                    -> (a ->{e} a ->{e} a)
                                    ->{e, head.test.Gen} Test (+2 metadata)
 test.laws.unit                     : '{head.test.Gen} a
                                    -> a
                                    -> (a ->{e} a)
                                    ->{e, head.test.Gen} Test (+2 metadata)
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

2 participants