Экземпляр Applicative для Data.Sequence обычно работает очень хорошо. Почти все методы постепенно увеличиваются асимптотически оптимально во времени и пространстве. То есть, учитывая полностью принудительные / реализованные входы, можно получить доступ к любой части результата с асимптотически оптимальным временем и резидентностью памяти. Осталось одно исключение: (<*). Я знаю только два способа его реализации:
Реализация по умолчанию
xs <* ys = liftA2 const xs ys
Эта реализация занимает O(|xs| * |ys|) время и пространство для полной реализации результата, но только O(log(min(k, |xs|*|ys|-k))) для доступа только к k -ому элементу результата.
A "monadi c" реализация
xs <* ys = xs >>= replicate (length ys)
Это занимает только O(|xs| * log |ys|) время и пространство, но оно не увеличивается; для доступа к произвольному элементу результата требуется O(|xs| * log |ys|) время и пространство.
Я давно считал, что у нас должен быть и тортик, и съесть его, но я никогда был в состоянии жонглировать части в моем уме достаточно хорошо, чтобы добраться туда. Для этого, по-видимому, требуется сочетание идей (но не фактического кода) из реализаций liftA2 и replicate. Как это можно сделать?
Примечание: конечно, нет необходимости включать что-то вроде rigidify механизма liftA2. replicate -подобные части, безусловно, должны создавать только те виды "жестких" структур, которые мы используем rigidify для получения от пользовательских деревьев.
Обновление (6 апреля 2020 г.)
Миссия выполнена! Мне удалось найти способ сделать это . К сожалению, это слишком сложно для меня, чтобы понять все, что происходит, и код ... довольно непрозрачный. Я буду одобрять и принимать хорошее объяснение того, что я написал, а также с удовольствием приму предложения по улучшению ясности и комментарии к GitHub.