[GHC] #9818: Add `Natural` number type to `base`
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: Type: feature request | Status: new Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Unknown | Type of failure: Blocked By: | None/Unknown Related Tickets: #3650 | Test Case: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- See original proposal at http://thread.gmane.org/gmane.comp.lang.haskell.libraries/23300 which was generally met with unanimous support for adding such a type. Request for CLC-arbitration (and its conclusion) on two more or less controversial details lacking consensus: https://groups.google.com/forum/#!msg/haskell-core- libraries/CVylSkkHCWE/Cqn7VEgR24sJ -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Changes (by hvr): * cc: core-libraries-committee@… (added) * keywords: => base natural * differential: => Phab:D473 * component: Compiler => Core Libraries * owner: => hvr -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"8a8cdbbfd855015049526c7945cbe9ccbb152f1e/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="8a8cdbbfd855015049526c7945cbe9ccbb152f1e" Implement `Natural` number type (re #9818) This implements a `Natural` type for representing unsigned arbitrary precision integers. When available, `integer-gmp>=1.0.0`'s `BigNat` type is used as building-block to construct `Natural` as an algebraic data-type. Otherwise, `Natural` falls back being a `newtype`-wrapper around `Integer` (as is done in Edward Kmett's `nats` package). The `GHC.Natural` module exposes an internal GHC-specific API, while `Numeric.Natural` provides the official & portable API. Reviewed By: austin, ekmett Differential Revision: https://phabricator.haskell.org/D473 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"4b6537677fa9460ca5febe2eb79a2d9d5bdadba2/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="4b6537677fa9460ca5febe2eb79a2d9d5bdadba2" Add `isValidNatural` predicate (#9818) This predicate function encodes the internal `Natural` invariants, and is useful for testsuites or code that directly constructs `Natural` values. C.f. `integer-gmp2`'s `isValidBigNat#` and `isValidInteger#` predicates for testing internal invariants. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"b836139099fc203a8b94849655d7dfb95dd80f4a/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="b836139099fc203a8b94849655d7dfb95dd80f4a" Fix `fromInteger` constructing invalid `Natural` This fixes a case where `isValidNatural . fromInteger` would be `False`. Re #9818 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"41300b7687c7fc60832f5fa91fce897fc2679ccd/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="41300b7687c7fc60832f5fa91fce897fc2679ccd" Implement {gcd,lcm}/Natural optimisation (#9818) This provides the equivalent of the existing `{gcd,lcm}/Integer` optimisations for the `Natural` type, when using the `integer-gmp2` backend. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"96d29b5403bd8a6465a65a39da861f5b9610fc89/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="96d29b5403bd8a6465a65a39da861f5b9610fc89" Call `popCountBigNat` directly (#9818) This calls the `popCountBigNat` primitive directly instead of going through `Integer`'s `popCount`. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"4bf055c70d07b98be1e7749e0306e406dfbbc006/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="4bf055c70d07b98be1e7749e0306e406dfbbc006" Define `Data` instance for `Natural` type (#9818) This follows the same style as the other integral `Data` instances defined in the `Data.Data` module. Reviewed By: ekmett Differential Revision: https://phabricator.haskell.org/D526 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"859680f6fe952ecbef3395fa4f299530d0f10c58/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="859680f6fe952ecbef3395fa4f299530d0f10c58" Implement `GHC.Natural.powModNatural` (#9818) This makes use of the `powMod*` primitives provided by `integer-gmp-1.0.0`. This is the `Natural`-version of the related `GHC.Integer.GMP.Internals.powModInteger` operation. The fallback implementation uses a square and multiply algorithm, compared to which the optimized GMP-based implementation needs much less allocations due to in-place mutation during the computation. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 #9281 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Changes (by hvr): * status: new => closed * resolution: => fixed * related: #3650 => #3650 #9281 Comment: This task is effectively done. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:9> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 #9281 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by thomie): The comment about @Natural@ in `libraries/base/Data/Word.hs` can be deleted or changed to point to this new module. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 #9281 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"a29e295c6fddfb0bbd390cff8cf2e5dbe9b1aa5b/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="a29e295c6fddfb0bbd390cff8cf2e5dbe9b1aa5b" Mention existence of 'Natural' in "Data.Word" This replaces the note mentioning the lack of a `Natural`-type by a note pointing to the new "Numeric.Natural" (#9818) module. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 #9281 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"6b063ef2a1f68290b51778a38e9b89b6fec5e170/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="6b063ef2a1f68290b51778a38e9b89b6fec5e170" Make Natural's (.|.) really an OR operation (#9818) Currently it's an AND when at least one of the operands is big. Reviewed By: hvr Differential Revision: https://phabricator.haskell.org/D549 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9818#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC