конкатенация в haskell

Долго делать 'a ++ b ++ c ++ ...', поэтому городят всякие билдеры.

Наверное так и будет, но какой тогда смысл конкатенировать что-то, если нужен только первый элемент x?

смысл в том, что я заранее хз, нужен только первый, или стопятьсотый.

если нужен первый - получается, никаких тормозов. а если 100500-й - то тормоза есть, но не из-за конкатенации, а из-за списка: тормозить будет ровно так же, как если бы мне понадобился 100500-й элемент в цельном списке

и каждый, каждый туториал, каждая книга, включая rwh и lyhgg обязательно, когда покажет оператор ++, сразу предупреждает: конкатенация - зло. списки ок, а конкатенация - зло

Watch out when repeatedly using the ++ operator on long strings. When you put together two lists (even if you append a singleton list to a list, for instance: [1,2,3] ++ [4]), internally, Haskell has to walk through the whole list on the left side of ++. That’s not a problem when dealing with lists that aren’t too big. But putting something at the end of a list that’s fifty million entries long is going to take a while. However, putting something at the beginning of

а если 100500-й - то тормоза есть, но не из-за конкатенации, а из-за списка: тормозить будет ровно так же, как если бы мне понадобился 100500-й элемент в цельном списке

Здесь списки используются не по назначению.

так я о том же. только все предупреждения, почему-то, в адрес конкатенации, а не списков. если б так было где-то в одном источнике - я б забил. но так везде

Это служит предупреждением для людей с определенным бекграундом — для тех кто раньше не писал в тотально иммутабельном окружнии. В императивных языках обычно конкатенация занимает O(1), но такие списки не персистентны. Поэтому откладывается привычка: конкатенация — дешево.

А здесь это не так. Если в выражении (a ++ b ++ c ++ ...) правоассоциативен, то мы получаем O(n), а если левоассоциативен, то мы получаем O(n ^ 2).

Возьмем к примеру два вызова:

"Hello" !! 3

и

("Hello" ++ " world") !! 3

Вы утверждаете, что они должны выполняться с одинаковой скоростью, так как во втором случае конкатенация фактически не требуется, ведь мы не выходим за пределы слова «Hello».

Ленивость ленивостью, но что-то я вот сомневаюсь, что конкатенация будет опущена во втором вызове. Не будет ли там всё-таки две пробежки по списку «Hello»? Я совсем позабыл основы Haskell'я, пусть знающие люди пояснят.

Если в выражении (a ++ b ++ c ++ ...) правоассоциативен

Слово пропущено. Имелась ввиду ассоциативность оператора (++).

Watch out when repeatedly using the ++ operator on long strings

Хм, а вроде как в одном из лиспосрачей решили что оператор ++ тоже ленивый и на самом деле строки не будут складываться. Просто когда закончится первая строка итерация пойдёт по второй.

Короче, надо это проверить. Мне влом :(

где я не прав? или книжки тупят?

Окасаки, например, не тупит. Он даже понятие «амортизированная сложность» вводит для анализа функциональных структур данных.

Он даже понятие «амортизированная сложность» вводит для анализа функциональных структур данных.

Это понятие появилось задолго до его тезиса.

Конкатенацию списков можно реализовать и более эффективными методами.

Например, через стрелки. Единственный вариант, который я пока вижу. Нужно просто-типизированное LC это будет одна конструкция из стрелок/2-стрелок, нужно LC с зависимыми типами - другая, с субструктурными (линейными, в частности) - ещё третья. Т.е. фиксированное подмножество теории категорий само по себе довольно бедная метатеория, просто язык, в котором можно выразить все эти вещи. Мартин-Лёф предлагал формулировать разные теории типов в рамках метатеории LF, вот также это можно делать в рамках метатеории ТК.

Ну, например, берём декартово-замкнутую категорию Set, она же классический топос, т.е. категория всех малых множеств и тотальных функций, в agda она так и называется - «Set». Берём категорию всех малых категорий и функторов Cat (Set1 в agda) и утверждаем:

• Любой тип который может использоваться (ADTs, GADTs, Inductive families) это объект Set (объект топоса, в общем случае), т.е., как следствие, множество - множество всех термов данного типа.
• Любой параметрически-полиморфный тип это эндофунктор на Set, т.е. специального вида стрелка в Cat. (Непараметрический тип, который объект в Set, это вырожденный случай функтора из терминальной категории (как-то так)).
• Любой конструктор типа данных который может быть это стрелка в Set (стрелка в топосе, вообще).
• Любая функция которая может быть это тоже стрелка в Set, но отдельным классом (чтобы не путать стрелки-конструкторы и стрелки-функции). Как следствие, «функция» - тотальная функция между множествами.
• Любая композиция стрелок с учётом декартовых произведений и экспоненциалов это любой правильно составленный терм в данной системе (тут типизация из коробки).
• Любое определение конкретной редукции это 2-стрелка (струнная диаграмма).
• Любой конкретный ход редукций (вычислений) это композиции 2-стрелок (струнных диаграмм). + Правила построения редукций из коробки.

Например:

-- Тут рисуем коммутативную диаграмму:
ℕ : Set
0 : 1 → ℕ
s : ℕ → ℕ

-- Продолжаем коммутативную диаграмму:
+ : ℕ → (ℕ → ℕ)

-- Рисуем две струнных диаграммы, которые можно сочетать:
e₁(+) : + ∘ a ∘ 0 ⇒ a
e₂(+) : + ∘ a ∘ (s ∘ b) ⇒ s ∘ (+ ∘ a ∘ b)

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

Тут ещё интересно, что можно легко добавлять конструкторы и правила редукций (как если бы в хаскеле можно было дописывать ADT и pattern matching cases по разным модулям).

Сами по себе 2-стрелки это непосредственно струнные диаграммы, т.е., рисуя коммутативные диаграммы, получим схемы типов, рисуя струнные - flow chart.

• Любая конкретная оптимизация это 3-стрелка. Правила построения оптимизаций тоже из коробки.

Например, если есть линейная рекурсия:

f x = z
f y = g (f (h y))

(f не появляется в g и h), т.е.:

-- любая стрелка вида:
f : x + y → r

-- с 2-стрелками вида:
e₁(f) : f ∘ x ⇒ z
e₂(f) : f ∘ y ⇒ g ∘ f ∘ h ∘ y

то она убирается такой 3-стрелкой:

-- Рисуем диаграмму между струнными:
o(f, f′) : e(f) ≡> e(f′ ∘ z)

-- TCO форма:
e₁(f′) : f′ ∘ a ∘ x ⇒ a
e₂(f′) : f′ ∘ a ∘ y ⇒ f′ ∘ (g ∘ a) ∘ (h ∘ y)

и остаётся только TCO.

Процесс унификации по 3-стрелкам это процесс оптимизаций, а процесс унификации по 2-стрелкам - интерпретации или компиляции (тогда нужен target). Как компилировать в target - конструкторы, например, достаточно точно отражаются в си-подобные структуры и объединения в памяти, можно даже в случае (s : ℕ → ℕ) или (_:_ : a → [a] → [a]) или вообще (con : [no `t' appears] → t → t) пытаться делать не связные списки, а аллоцируемые/реаллоцируемые массивы. Про компиляцию редукций ничего не скажу - только, наверно, тут, в первую очередь, нужен критерий линейности представляемого терма и/или его линеаризация.

Ага, точняк.

Действительно.

спасибо!

Намного круче

> ([1..4] ++ undefined) !! 3
4
> ([1..3] ++ undefined) !! 3
*** Exception: Prelude.undefined

это не показывает, что конкатенация не проходится по всему первому списку

это не показывает, что конкатенация не проходится по всему первому списку

Ага, это показывает что конкатенация не вычисляется *вообще* :P

Вообще-то показывает.

purely functional data structures?

purely functional data structures?

Да

Ага, это показывает что конкатенация не вычисляется *вообще* :P

... не доходит до 2 аргумента

поправь, где ошибаюсь

как? я про

> ([1..4] ++ undefined) !! 3
4
> ([1..3] ++ undefined) !! 3
*** Exception: Prelude.undefined

... не доходит до 2 аргумента

Пардон, ошибся. Сейчас проверил — вычисляется.

... не доходит до 2 аргумента

Но можно еще ([1, 2, 3, 4, undefined] ++ [6, 7, 8, 9, undefined]) !! n

Тоже прикольные результаты получаются.

Как конкатенация проходит по списку проще пронаблюдать вот так:

λ> Prelude.last $ Prelude.foldr (\ x xs -> traceShow x (x : xs)) (trace "teh end" []) [0..3] <> [4]
0
1
2
3
teh end
4

quasimoto, залогинься

Я из под anonymousа не пишу.

Шутка же была.