Remove cycle and repeat from Data.List.Linear

[alt-romes]

Describe the bug

The function cycle from Data.List.Linear never terminates

To Reproduce

Load up ghci with

take 5 (Data.List.Linear.cycle ['a','b'])

Expected behavior

It should return "ababa" and terminate. Currently it returns "ababa" but never terminates 🙂.

Environment

GHC 9.4.4 and 9.6.1

[alt-romes]

I diagnosed this incorrectly. I was using linear-base's take instead of the base one, and linear take traverses the whole list. Apologies!

[treeowl]

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

[treeowl]

I'm reopening because I think we should remove cycle.

[treeowl]

I think the same is true of repeat.

[treeowl]

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

1. Use an optimized Replicator when available,
2. Avoid unnecessary dupRs, and
3. Avoid unnecessary nexts.

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'

[treeowl]

Oops, my implementation still isn't ideal.... Let me work on that a bit more....

[aspiwack]

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…

[aspiwack]

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.

[aspiwack]

@treeowl could you help me read through your code example? I don't think I understand what I'm supposed to see.

[treeowl]

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.

1. There may be an optimized dupR, so we should use that instead of dup2.
2. We probably don't want to dupR something that we never actually use, because it may well be cheaper to consume it than to dupR it. So starting off just dupRing 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.
3. If we've already dupRed 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 been dupRed.

[aspiwack]

(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.