lazy fromList?

[jwaldmann]

As discussed elsewhere, there are use cases in algorithmic composition that would benefit from a lazy fromList :: [a] -> Pattern a (where the argument is infinite).

Current implementation uses cat and that's not lazy: it will evaluate the length of its argument.

We can build a lazy fromList by shifting the time inside queries - this is already in the implementation of cat.

The time-shift then appears as list-access. But !! i takes time linear in i. We can do better (somewhat): there are data structures for infinite sequences that are non-strict in the tail and allow logarithmic indexed access (for the part that's evaluated). Basically, a lazy sequence of balanced trees (of increasing size).

Cf. https://apfelmus.nfshost.com/articles/implicit-heaps.html

[yaxu]

I haven't looked in detail, but is this from @moxuse relevant? https://github.com/moxuse/tidal-lazy/