Более эффективный сплит с замыканием

Question

Функция Clojure split-with довольно удобна, но она должна дважды пересечь переднюю часть seq, поскольку она буквально реализована как [(take-while pred coll) (drop-while pred coll)]. Тем не менее, довольно легко написать (хвостовую рекурсивную) версию, которая пересекает ведущую часть только один раз (поместите ведущую часть в накапливающийся вектор и т. Д.).

Однако я хотел бы извлечь первый элемент из списка , который удовлетворяет предикату, и вернуть как элемент, так и оставшийся список (т. Е. (concat (take-while pred coll) (next (drop-while pred coll)))) - надеюсь, за один проход , Если бы я использовал какой-то императивный язык, я бы просто прошел по списку, держась за последнюю ячейку, и, как только я получил элемент, чтобы выскочить, возиться со «следующим указателем» предыдущей ячейки, чтобы восстановить измененный список, но на функциональном языке это кажется невозможным.

Так есть ли способ сделать это эффективно в Clojure?

Answer 1

Для split-with (и аналогичных задач, в которых вы хотите создать два выхода из одного входа), вы можете иметь любые два из

• Лень
• Неизменность
• Идеальная эффективность.

Например, если вы не хотите лени (из первой «отброшенной» части), вы можете получить две другие, внедрив хвосто-рекурсивную версию, как вы предлагаете.

Все это не совсем применимо к вашему текущему вопросу, так как вам нужна только одна выходная последовательность, и я рекомендую решение Kotarak (или что-то подобное). Тем не менее, я подумал, что вам может понравиться объяснение того, почему встроенный в Clojure split-with дважды обходит входную последовательность.

Answer 2

Вы можете всегда опускаться до lazy-seq для особых требований.

(defn splice-tail
  ([pred coll] (splice-tail pred 1 coll))
  ([pred n coll]
   (lazy-seq
     (when-let [s (seq coll)]
       (let [fst (first s)]
         (if (pred fst)
           (cons fst (splice-tail pred n (rest s)))
           (nthnext s n)))))))