Как можно оптимально реализовать (<*) для последовательностей?

Question

В Applicative пример для Data.Sequenceв целом работает очень хорошо. Почти все методы являются асимптотически оптимальными по времени и пространству. То есть, учитывая полностью принудительные / реализованные входы, можно получить доступ к любой части результата с асимптотически оптимальным временем и размещением в памяти. Осталось одно исключение:(<*). Я пока знаю только два способа реализовать это:

1. Реализация по умолчанию

   xs <* ys = liftA2 const xs ys
   

   Эта реализация занимает O(|xs| * |ys|) время и место, чтобы полностью реализовать результат, но только O(log(min(k, |xs|*|ys|-k))) чтобы получить доступ только к k-й элемент результата.

2. "Монадическая" реализация

   xs <* ys = xs >>= replicate (length ys)
   

   Это займет только O(|xs| * log |ys|)время и пространство, но не инкрементально; доступ к произвольному элементу результата требуетO(|xs| * log |ys|) время и место.

Я долгое время считал, что можно есть и наш пирог, и его тоже, но мне никогда не удавалось достаточно хорошо мысленно передвигать кусочки, чтобы добраться до цели. Для этого, по-видимому, требуется комбинация идей (но не фактического кода) из реализацийliftA2 а также replicate. Как это может быть сделано?

---

Примечание: конечно, нет необходимости включать что-либо подобное rigidify механизм liftA2. Вreplicate-подобные изделия, безусловно, должны производить только те виды "жестких" структур, которые мы используем rigidify получить из предоставленных пользователем деревьев.

Обновление (6 апреля 2020 г.)

Миссия выполнена! Мне удалось найти способ это сделать. К сожалению, мне слишком сложно понять все, что происходит, а код... довольно непрозрачный. Я поддержу и приму хорошее объяснение того, что я написал, а также с радостью приму предложения по улучшению ясности и комментарии на GitHub.

Обновление 2

Большое спасибо Ли-Яо Ся и Бертраму Фельгенхауэру за помощь в очистке и документировании моего черновика кода. Теперь это значительно проще понять, и он появится в следующей версииcontainers. Было бы неплохо получить ответ, чтобы закрыть этот вопрос.