Comments (11)
I diagnosed this incorrectly. I was using linear-base's take
instead of the base one, and linear take
traverses the whole list. Apologies!
from linear-base.
I believe the essential problem is that it's impossible to ever consume
an infinite list. So cycle
seems quite useless in a linear context. Solution: get rid of it, and add an equivalent of Data.Sequence.cycleTaking
from linear-base.
I'm reopening because I think we should remove cycle
.
from linear-base.
I think the same is true of repeat
.
from linear-base.
I have no idea if something cycle
-like is appropriate, but for the heck of it I decided to write one (following Data.Sequence
). It is not at all trivial to
- Use an optimized
Replicator
when available, - Avoid unnecessary
dupR
s, and - Avoid unnecessary
next
s.
I came up with a version using the following simple queue:
module BoringQueue where
module Data.BoringQueue.Linear where
import Data.Unrestricted.Linear.Internal.Consumable (Consumable (consume), lseq)
infixl 5 :>
infixr 5 :<
-- | Strict cons list.
data CL a = CNil | !a :< !(CL a)
instance Consumable a => Consumable (CL a) where
consume CNil = ()
consume (a :< as) = a `lseq` consume as
-- | Strict snoc list.
data SL a = SNil | !(SL a) :> !a
instance Consumable a => Consumable (SL a) where
consume SNil = ()
consume (as :> a) = a `lseq` consume as
-- | A boring queue strict in its values.
data Queue a where
Queue :: !Int -> !(CL a) %1-> !(SL a) %1-> Queue a
instance Consumable a => Consumable (Queue a) where
consume (Queue _ front rear) = front `lseq` consume rear
size :: Queue a %1-> (Int, Queue a)
size (Queue s fr r) = (s, Queue s fr r)
data SizedQueue a where
SizedQueue :: !Int -> !(Queue a) %1-> SizedQueue a
sized :: Queue a %1-> SizedQueue a
sized (Queue s front rear) = SizedQueue s (Queue s front rear)
rot :: SL a %1-> CL a
rot = go CNil
where
go :: CL a %1-> SL a %1-> CL a
go !acc SNil = acc
go !acc (as :> a) = go (a :< acc) as
empty :: Queue a
empty = Queue 0 CNil SNil
check :: Int -> CL a %1-> SL a %1-> Queue a
check s (x :< xs) ys = Queue s (x :< xs) ys
check s CNil rear = Queue s (rot rear) SNil
insert :: a %1-> Queue a %1-> Queue a
insert a (Queue s front rear) = check (s + 1) front (rear :> a)
insDel :: Queue a %1-> a %1-> (a, Queue a)
insDel (Queue s CNil rear) a = case rear of
SNil -> (a, empty)
zs :> z -> error "Broken invariant." a s zs z
insDel (Queue s (x :< front) rear) a = (x, check s front (rear :> a))
uncons :: Queue a %1-> Maybe (a, Queue a)
uncons (Queue _ CNil rear) = case rear of
SNil -> Nothing
xs :> x -> error "invariant failure" xs x
uncons (Queue s (x :< xs) rear) = Just (x, check (s - 1) xs rear)
The actual implementation:
cycleTaking :: forall a. (HasCallStack, Dupable a) => Int -> [a] %1 -> [a]
cycleTaking = start Q.empty
where
start :: Q.Queue (Rep.Replicator a) %1-> Int -> [a] %1-> [a]
start q n xs
| n Prelude.<= 0 = q `lseq` xs `lseq` []
start q n xs =
case Q.sized q of { Q.SizedQueue s q' ->
case xs of
[] -> Prelude.error "cycleTaking: empty list" q'
[a]
| n Prelude.<= s + 1
-> a : finish (n - 1) q'
| otherwise
-> case Rep.next (dupR a) of
(z, p) -> z : go (n - 1) q' p
(x : xs') -> case Rep.next (dupR x) of
(x', repx) -> x' : start (Q.insert repx q') (n - 1) xs'
}
go :: Int -> Q.Queue (Rep.Replicator a) %1-> Rep.Replicator a %1-> [a]
go 0 q a = a `lseq` q `lseq` []
go n q a = case Q.sized q of
Q.SizedQueue s q'
| n Prelude.<= s + 1
-> finish n (Q.insert a q')
| otherwise
-> case Q.insDel q' a of { (z, q'') ->
case Rep.next z of
(w, x) -> w : go (n - 1) q'' x}
finish :: Int -> Q.Queue (Rep.Replicator a) %1-> [a]
finish 0 q = q `lseq` []
finish n q = case Q.uncons q of
Nothing -> []
Just (s, q') -> Rep.extract s : finish (n - 1) q'
from linear-base.
Oops, my implementation still isn't ideal.... Let me work on that a bit more....
from linear-base.
On the efficiency stand-point, I think the right approach is to use dupR
instead of dup2
(in iterate
, cycle
, etc…). But even using a Replicator
in our recursion, there may still be superfluous duplications when chaining functions that have a Duplicable
constraint.
It is true that these infinite lists are not tremendously useful. As they can only be used after proving that they contain no linearity to begin with. The Dupable
constraints ensure that they are not fully compatible with their base
equivalent. Maybe they should have other named. May be useful in fusion pipelines where linearity helps us ensure that no allocation is built, but I wouldn't use lists directly to achieve such a purpose. So I don't know…
from linear-base.
Another option is to build take
into these functions and produce only a prefix of the list. But it feels rather limited as we can't compose these functions well. So maybe the “right” solution is to use our “affine” (or “interruptible”) streams (probably their API needs to be cleaned up so that they can can be published as their own module) for these infinite structures and convert them back into lists when we're happy.
from linear-base.
@treeowl could you help me read through your code example? I don't think I understand what I'm supposed to see.
from linear-base.
I think you're right about affine streams of some sort being the right approach here. My code is a bit off, and not worth fixing if we're not going that way, but here are the general considerations behind it.
- There may be an optimized
dupR
, so we should use that instead ofdup2
. - We probably don't want to
dupR
something that we never actually use, because it may well be cheaper toconsume
it than todupR
it. So starting off justdupR
ing all the elements in the list is a bad plan—the number of elements taken may be fewer than the number of elements in the list. - If we've already
dupR
ed enough elements to satisfy the number requested but there are elements remaining in the list, we shouldn't duplicate any more; we should instead pass on the remaining elements directly until they run out, and then complete the request from what's beendupR
ed.
from linear-base.
(2) seems to be largely a theoretical concern. I don't know any example (for the record, in the case where dup2
and consume
were given explicitly but not dupR
, then consume (dupR a)
is (up to one allocation) actuallyconsume a
.). Maybe you could simplify the code based on this observation.
Generally speaking, seeing a queue of replicators gives me pause. From your (3), I think this is because you are trying to duplicate individual elements rather than the list itself, to avoid creating additional copies of the leftover elements when we stop in the middle. Which is probably fair.
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
- Eq and Ord classes don't seem very useful HOT 3
- We're broken on master (929161943f19) HOT 7
- 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.