Comments (3)
Oooff… I kind of forgot about this issue for a while. Sorry.
My intention with these is type is that
(==) :: a %1-> a %1-> (Bool, a, a)
is a pretty awful type to work with- types that can implement the equality test above will be
Dupable
.
You come with two counter-example. Mutable arrays are not dupable, neither would mutable byte arrays. Nevertheless it may make sense to compare them.
- You could have structural,
$O(n)$ , equality. - Pointer equality doesn't make much sense for these: it's always false
- But you can have pointer comparisons for the sake of an ordered data structure. Probably not for mutable arrays, as this is not stable (it would have to be in
IO
); but for byte arrays that are pinned, it makes sense for comparison to be pure.
There is more than one way to think about this.
- We can keep the classes as they are and say: this is the most common case,
Dupable
structures, and they're better types when working on them. But I see an issue there that hadn't surfaced yet: pretty much every data structure requiring anOrd
instance will have to useDupable
as well. Dubious. - We can use your definitions, but then, when we always have to handle these pesky extra fields, even when we are in the
Dupable
case. Possible mitigation, add a copy of each method like so:But forclass Eq a where (==:) :: a %1-> a %1-> (Bool, a, a) (==) :: Consumable a => a %1-> a %1-> Bool a == b = let !(r, a', b') = a ==: b in a' `lseq` b' `lseq` r
Consumable
data types, we can typically implement(==)
directly, and bypass the extra call toconsume
/lseq
. - Or we could say that we need to invent something new.
Let me riff on this third possibility for a little while.
We could say that, instead of (==)
, compare
and all that, the proper primitive is compare-and-swap:
cas :: a %1 -> a %1 -> (a, a)
Where the guarantee is that in the returned pair, the smaller a
is first. As an aside cas
has well-defined laws, and is equivalent to lattices (maybe distributive, I don't remember) (it works for partial orderings, in which case the result is to be understood as $(a \wedge b, a \vee b)$).
It's quite clear that a linear cas
is a perfectly reasonable construction.
However, it's far from perfect. For instance, you can't write quicksort or mergesort with cas (exercise: try). Sorting that can be done with cas are called network sorts, the most famous is the bitonic sort.
One key issue with cas
is that it doesn't let us decide equality.
Ok, maybe let's add a boolean:
cas :: a %1 -> a %1 -> (Bool,a, a)
It's not much worse, and it's easy to produce a version that doesn't return the boolean. It does encode the additional ordering structure in the ordering of the pair. Pretty neat.
But I don't think it suffices for mergesort: at some point in merge sort you have (a : as) (b : bs)
, and you need to pick the smaller of a
and b
, and leave the other one in its place. So we really need to know which one was the smaller. The above type doesn't give it to us. So we'd need to know whether a reordering has happened. Basically
cas :: a %1 -> a %1 -> (Ordering, a, a)
This is your compare
but the two returned a
may have been permuted. Not a very useful “improvement”. It's interesting that with a boolean we could still encode some data in the choice of which a
to return in which place, but this isn't the case as soon as we add just a third alternative.
Well… I wrote a lot of words, not many are useful, are they?
from linear-base.
A couple examples:
- Comparing two mutable arrays for (pointer) equality should not consume them.
- Comparing the addresses of two pinned mutable byte arrays (with
compare
) should not consume them.
from linear-base.
I'm being silent on this issue, because I need to think about it. Apologies.
from linear-base.
Related Issues (20)
- Provide Ormolu via Nix HOT 6
- `linear-base` has a `streaming`-style `Stream` type. Should it have a `streaming-bytestring` style `ByteStream`? HOT 1
- Dispose with side effects HOT 9
- Fails to build with GHC 9.6 alpha2 HOT 19
- 0.3.1 doesn't build with GHC 9.0 HOT 3
- [Doc question] Definition of linear HOT 3
- Movable for amortized structures HOT 11
- Question: unrestricted list functions HOT 1
- We're broken on master (929161943f19) HOT 7
- Remove cycle and repeat from Data.List.Linear HOT 11
- Add one or more queue/steque types HOT 5
- More natural takeWhile analogue? HOT 2
- Lazy tuple workaround HOT 6
- Lens won't work as expected due to the missing `Functor (FUN 'One a)` instance (both `Data` and `Control`) HOT 3
- How ready is Linear Haskell for real world use cases? HOT 3
- linear-base-0.1.0 build failure with GHC 9.8 HOT 7
- Word does not have instances for the Data.Num.Linear typeclasses HOT 2
- Pull array index isn't safe HOT 2
- &, T tensor HOT 10
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from linear-base.