Code golf: Flatten с вставкой дополнительного элемента

Обновление: обсуждение завершено, результаты в конце текста вопроса.

Обсуждение вопроса ведётся в чате «Code golf на русском».

Пускай у нас есть набор лениво вычисляемых последовательностей действительных чисел. Задача состоит в том, чтобы построить также лениво вычисляемую последовательность, конкатенирующую все данные последовательности. Но между каждыми двумя последовательностями нужно ещё вставить среднее арифметическое последнего члена предыдущей, и первого члена следующей последовательности.
Пример: пусть исходные данные таковы:
1; 2; 3; 4; 5 // 1 кусок 6; 5; 4; 3 // 2 кусок // 3 кусок пустой -3; -3; -3 // 4 кусок
Тогда результирующая последовательность должна быть
1; 2; 3; 4; 5; 5.5; 6; 5; 4; 3; 0; -3; -3; -3 // 1-ая часть (5 + 6)/2 2-ая часть (3 + -3)/2 4-я часть
Ограничения:
Нельзя материализовывать последовательности, они имеют право быть очень большими и не влезать в оперативку Нельзя повторно вычислять куски последовательностей, т. к. генераторы, которые генерируют эти последовательности, имеют право быть очень медленными. Полученная последовательность должна быть ленивой, нельзя ничего вычислять заранее.
Код на C#, реализующий подобное, может быть таким:
IEnumerable FlattenWithInsertedValues(IEnumerable> seqs) { double? firstAddend = null; foreach (var seq in seqs) { double? lastInThisSeq = null; foreach (var v in seq) { if (firstAddend != null) { yield return (firstAddend.Value + v) / 2; firstAddend = null; } yield return v; lastInThisSeq = v; } if (lastInThisSeq != null) firstAddend = lastInThisSeq; } }
Этот код откровенно прямолинеен, некрасив и императивен. Существует ли более изящное решение? Любители функциональных языков, разумеется, получают в данном вопросе фору на старте, т. к. в остальных ленивые последовательности не встроены в язык.
Приветствуются красивые решения, не обязательно короткие. Дополнительный плюс за правильную обработку пустых кусков.
Поскольку гольф, пожалуйста, одно решение на ответ. Если есть разные решения, постите отдельным ответом.

Для того, чтобы было легче тестировать код, вот тесты на C#:
void Test1() { var result = FlattenWithInsertedValues(TestGenerator1()); foreach (var v in result) Console.Write(v + " "); }
void Test2() { var result = FlattenWithInsertedValues(TestGenerator2()); Console.Write(result.Count()); }
IEnumerable> TestGenerator1() { Console.Write("Generating outer seq 1 "); yield return Generator(1, 5, 1); yield return Generator(1, 0, 2); yield return Generator(1, 3, 3); }
IEnumerable> TestGenerator2() { Console.Write("Generating outer seq 2 "); yield return Generator(1, 5, 1); yield return Generator(1, 10000000000000, 2); }
IEnumerable Generator(double from, double to, int seqNum) { Console.Write($"Generating seq #{seqNum} "); for (double curr = from; curr < to; curr += 1) yield return curr; }
Они выдают:
Test1:
Generating outer seq 1 Generating seq #1 1 2 3 4 Generating seq #2 Generating seq #3 2,5 1 2
Test2:
Generating outer seq 2 Generating seq #1 Generating seq #2
Второй тест может очень долго (я не дождался результата своего), но не должен падать по переполнению памяти.

Результаты:
Приз зрительских симпатий однозначно достаётся @avp, который показал, что генераторы, ленивость и функциональные фишки вполне реализуемы на таком близком к металлу языке как C, и не ограничены функциональными языками. Решения @Qwertiy (ES6), @D-side (Ruby), @tonal (Python), @pavel (C++) по сути повторяют идею из исходного вопроса, хотя и в более изящной форме. Эти решения также заслуженно получили высокие оценки. Прекрасная алгоритмическая идея с энумерацией придумана @kmv (F#) и повторно реализована @tonal (Python) и ещё раз @tonal (теперь Haskell). Мне кажется, решения, основанные на этой идее, остались недооценёнными. Отдельной строкой идут решения с паттерн-мэтчингом на Хаскеле (@tonal, @Pavel Mayorov, снова @tonal) и Clojure (@D-side), которые выглядят неожиданно просто и легко (за счёт сложности реализации самого паттерн-мэтчинга для ленивых последовательностей). Это, пожалуй, самые правильные решения в смысле простоты и понятности кода. Поэтому самое популярное решение из них принято в качестве ответа.
(Как оказалось, паттерн-мэтчинг ленивых последовательностей есть и в F#, но решения с ним никто не предложил.) Ещё красивая идея — явный конечный автомат на Clojure (@D-side). LISP показал, что он ещё может. Ещё была реализация на языке Julia, которая, к сожалению, удалена автором решения.
Огромное спасибо всем, кто принимал участие в обсуждении и предлагал собственные решения! Надеюсь, участникам сайта будет настолько же приятно и поучительно читать ваши решения и комментарии, насколько и мне.

Ответ

На Haskell, втупую:
flatten :: [[Float]] -> [Float] flatten [] = [] flatten [y] = y flatten ([]:xs) = flatten xs flatten (y:[]:xs) = flatten $ y:xs flatten ([y]:(yy:ys):xs) = y : (y + yy)/2 : flatten ((yy:ys):xs) flatten ((y:ys):zs:xs) = y : flatten (ys:zs:xs)
main = do let ls = [[1, 2, 3, 4, 5], [6, 5, 4, 3], [-3, -3, -3]] print ls let fs = flatten ls print fs
Здесь используется сопоставление с образцами. Варианты следующие:
flatten [] = [] - На пустой список возвращаем пустой же. flatten [y] = y - Во входном списке ровно 1 элемент - его и возвращаем. flatten ([]:xs) = flatten xs - Входящий список начинается с пустого. Пропускаем его, а к хвосту xs применяем flatten flatten (y:[]:xs) = flatten $ y:xs - Во входном списке второй элемент пустой. Пропускаем его, а к списку из головы и хвоста y:xs применяем flatten flatten ([y]:(yy:ys):xs) = y : (y + yy)/2 : flatten ((yy:ys):xs) - В головном списке остался 1 элемент y. Отдаём список из него, его среднего арифметического с первым элементом второй последовательности и хвостом полученным применением flatten к списку из второй последовательности и хвоста (yy:ys):xs flatten ((y:ys):zs:xs) = y : flatten (ys:zs:xs) - В головном списке несколько элементов. Выдаём список из первого y и применения flatten к остатку ys:zs:xs