AFAIK в функциональных языках одной из ключевых фич является отсутствие переменных. Все данные передаются из функции в функцию, нет никаких побочных эффектов в виде изменения данных по какому-то конкретному адресу в памяти. Это позволяет делать оптимизации недоступные компиляторам других ЯП.
Но возникает вопрос — как быть с большими структурами данных? Если мне нужно поменять единственный элемент в большом массиве даных, то неужели мне придётся копировать все элементы, которые остались неизменными? (Вообще, доступ к элементам в середине списков в ФЯ выглядит жутковато — судя по коду, приводимому в разных туториалах, требуется перелопатить пол-массива, чтоб добраться до нужного элемента. Я конечно понимаю, что компилятор сможет оптимизировать такой элеметарный случай, но где проходит граница той сложности, при которой компилятор перестанет вмешиваться?)
В качестве примера можно привести игру Конвея — Жизнь. Погуглив я нашёл пример её реализации, в которой основной цикл выглядел как вот такая функция:

evaluate w :: World -> World

Где World — это тип, включающий в себя описание всей среды Жизни, в том числе большущий двумерный массив с клеточками. Получается, что на каждом шаге происходит копирование всего содержимого этой матрицы.
В качестве второго примера можно рассмотреть реализацию быстрой сортировки, про которую говорил Gaperton в Q&A

Автор: Gaperton
Дата: 06.06.05

:

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

Хотя пример с Жизнью, мне кажется более общим.
Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?

Здравствуйте, Mazay, Вы писали:

M>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?

Как вариант, в Clean используется Uniqueness typing

Здравствуйте, Mazay, Вы писали:

M>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?

Краткий ответ — применяются другие структуры данных, построенные не на базе массивов, а на базе списков. Кроме того, ленивые вычисления позволяют в ряде случаев улучшить асимптотику. Смотри список публикаций Криса Окасаки, а также его диссертацию Purely Functional Data Structures.

Перед тем как посмотришь — небольшая задачка, попробуй решить ее сам (у тебя получится, и ты словишь просветление).

Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

Это сделать можно.

http://www.eecs.usma.edu/webs/people/okasaki/pubs.html

Здравствуйте, Gaperton, Вы писали:

G>Здравствуйте, Mazay, Вы писали:

M>>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?

G>Краткий ответ — применяются другие структуры данных, построенные не на базе массивов, а на базе списков. Кроме того, ленивые вычисления позволяют в ряде случаев улучшить асимптотику. Смотри список публикаций Криса Окасаки, а также его диссертацию Purely Functional Data Structures.

Ну и как вариант, наверное Zipper

Здравствуйте, Mazay, Вы писали:

M>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?

Второй ответ — состоит в оптимизации с single threaded object. Если у тебя есть объект, на который только одна ссылка, то его можно безопасно модифицировать. В Хаскеле это делается посредством монад. Обрати внимание на STAray.

Кроме того, есть прием программирования, суть которого — отложить фактическое изменение объекта на потом, чтобы провести все изменения кучей (bulk update), отложив их. Это также выправляет асимптотику.

И кроме того, коль скоро у нас все копируется, сам процесс детального проектирования в ФЯ другой. В обычном языке ты озабочен выбором долгоживущей структуры данных, которая обеспечит тебе все сценарии. В ФЯ ты думаешь не так. Коль скоро у тебя все копируется, ты раскладываешь алгоритм на стадии, и выбираешь для каждой стадии наиболее оптимальное представление данных. Таким образом, у тебя нет единой долгоживущей структуры, и ты концентрируешься на алгоритмах, а не структурах данных.

Здравствуйте, Gaperton, Вы писали:

G>Перед тем как посмотришь — небольшая задачка, попробуй решить ее сам (у тебя получится, и ты словишь просветление).

G>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

В голову такой вариант приходит: есть однонаправленный список, указатели в элементах идут от хвоста до головы, на хвост неуказывает никто, указатель в голове указывает в никуда, есть переменная-"указатель на хвост", есть переменная-"указатель на голову".
put делается в голову, при этом меняется указатель в голове и переменная-"указатель на голову".
get делается из хвоста, при этом в переменную-"указатель на хвост" пишется адрес, который был в изымаемом хвостовом элементе.
Переменные-указатели нужны, чтоб знать откуда делать get и put.
Укладывется ли это решение в условия задачи?
Не торкнуло. Наверное надо читать японца.

Здравствуйте, Gaperton, Вы писали:

G>Перед тем как посмотришь — небольшая задачка, попробуй решить ее сам (у тебя получится, и ты словишь просветление).

G>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

Есть однонаправленный список. Указатели идут от хвоста к голове: на хвостовой элемент никто не указывает, указатель в голове не указывает никуда. get делается из хвоста, put — в голову. Есть переменная-"указатель на хвост". Когда нужно взять элемент, мы смотрим его адрес в этой переменной, потом берём указатель из него и кладём его в эту переменную — теперь хвостом стал тот элемент, на который указывал извлечённый. Есть переменная-"указатель на голову". Когда делаем put — берём адрес головы из этой переменной и кладём в указатель головного элемента адрес добавляемого. Этот же адрес калдём в переменную-"указатель на голову".
Удовлетворяет ли это решение условиям задачи?
Прихода нет, не торкает. Наверное надо читать японца.

Здравствуйте, Mazay, Вы писали:

M>Здравствуйте, Gaperton, Вы писали:

G>>Перед тем как посмотришь — небольшая задачка, попробуй решить ее сам (у тебя получится, и ты словишь просветление).

G>>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

M>Есть однонаправленный список. Указатели идут от хвоста к голове: на хвостовой элемент никто не указывает, указатель в голове не указывает никуда. get делается из хвоста, put — в голову. Есть переменная-"указатель на хвост". Когда нужно взять элемент, мы смотрим его адрес в этой переменной, потом берём указатель из него и кладём его в эту переменную — теперь хвостом стал тот элемент, на который указывал извлечённый. Есть переменная-"указатель на голову". Когда делаем put — берём адрес головы из этой переменной и кладём в указатель головного элемента адрес добавляемого. Этот же адрес калдём в переменную-"указатель на голову".
M>Удовлетворяет ли это решение условиям задачи?
M>Прихода нет, не торкает. Наверное надо читать японца.

Эээ, никаких указателей нет, всё что ты можешь со списком по сути — взять голову и/или передвинуться на след. элемент списка.

Здравствуйте, Gaperton, Вы писали:

M>>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?

G>Второй ответ — состоит в оптимизации с single threaded object. Если у тебя есть объект, на который только одна ссылка, то его можно безопасно модифицировать.
Это не часом не есть Uniqueness typing? Если нет, то как это выглядит в ФЯ?
G>В Хаскеле это делается посредством монад. Обрати внимание на STAray.
Про монады почитаю.

G>Кроме того, есть прием программирования, суть которого — отложить фактическое изменение объекта на потом, чтобы провести все изменения кучей (bulk update), отложив их. Это также выправляет асимптотику.
Для некоторых случаев может помочь.

G>И кроме того, коль скоро у нас все копируется, сам процесс детального проектирования в ФЯ другой. В обычном языке ты озабочен выбором долгоживущей структуры данных, которая обеспечит тебе все сценарии. В ФЯ ты думаешь не так. Коль скоро у тебя все копируется, ты раскладываешь алгоритм на стадии, и выбираешь для каждой стадии наиболее оптимальное представление данных. Таким образом, у тебя нет единой долгоживущей структуры, и ты концентрируешься на алгоритмах, а не структурах данных.
Совсем забывать про структуру данных нельзя, потому что могут родиться вот такие кошмары: evaluate w :: World -> World. Очень, кстати, математическое выражение, только не учитывающе реалии железа.
Но в общем идея понятна — надо менять мышление.

Здравствуйте, Mazay, Вы писали:

M>Здравствуйте, Gaperton, Вы писали:

G>>Перед тем как посмотришь — небольшая задачка, попробуй решить ее сам (у тебя получится, и ты словишь просветление).

G>>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

M>Есть однонаправленный список. Указатели идут от хвоста к голове: на хвостовой элемент никто не указывает, указатель в голове не указывает никуда. get делается из хвоста, put — в голову. Есть переменная-"указатель на хвост". Когда нужно взять элемент, мы смотрим его адрес в этой переменной, потом берём указатель из него и кладём его в эту переменную — теперь хвостом стал тот элемент, на который указывал извлечённый. Есть переменная-"указатель на голову". Когда делаем put — берём адрес головы из этой переменной и кладём в указатель головного элемента адрес добавляемого. Этот же адрес калдём в переменную-"указатель на голову".
M>Удовлетворяет ли это решение условиям задачи?
M>Прихода нет, не торкает. Наверное надо читать японца.

Как правильно заметил Курилка, никаких указателей у тебя нет. Что такое однонаправленный список — думай о нем как о стеке. Ты можешь добавлять элемент туда, и забирать элемент оттуда. Все.

Здравствуйте, Mazay, Вы писали:

M>Здравствуйте, Gaperton, Вы писали:

G>>И кроме того, коль скоро у нас все копируется, сам процесс детального проектирования в ФЯ другой. В обычном языке ты озабочен выбором долгоживущей структуры данных, которая обеспечит тебе все сценарии. В ФЯ ты думаешь не так. Коль скоро у тебя все копируется, ты раскладываешь алгоритм на стадии, и выбираешь для каждой стадии наиболее оптимальное представление данных. Таким образом, у тебя нет единой долгоживущей структуры, и ты концентрируешься на алгоритмах, а не структурах данных.
M>Совсем забывать про структуру данных нельзя, потому что могут родиться вот такие кошмары: evaluate w :: World -> World. Очень, кстати, математическое выражение, только не учитывающе реалии железа.
M>Но в общем идея понятна — надо менять мышление.

В том и дело, что в функциональном программировании структуры данных другие (и мышление тоже). А вещи типа evaluate w :: World -> World вполне себе работают в Clean, одном из наиболее шустрых функциональных языков (хоть и не сильно популярных), а монада IO как раз World и "оборачивает".

Здравствуйте, Курилка, Вы писали:


G>>>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>>>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

К>Эээ, никаких указателей нет, всё что ты можешь со списком по сути — взять голову и/или передвинуться на след. элемент списка.

А как в него помещаются элементы? К голове подклеиваются?

Здравствуйте, Mazay, Вы писали:

M>Здравствуйте, Курилка, Вы писали:


G>>>>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>>>>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

К>>Эээ, никаких указателей нет, всё что ты можешь со списком по сути — взять голову и/или передвинуться на след. элемент списка.

M>А как в него помещаются элементы? К голове подклеиваются?

Конечно, Гапертон правильную идею со стэком нарисовал.
Ну и плюс обход списка через рекурсию (если ты ещё не в курсе), как и почти все манипуляции со списками.

Здравствуйте, Курилка, Вы писали:

G>>>>>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>>>>>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

К>>>Эээ, никаких указателей нет, всё что ты можешь со списком по сути — взять голову и/или передвинуться на след. элемент списка.

M>>А как в него помещаются элементы? К голове подклеиваются?

К>Конечно, Гапертон правильную идею со стэком нарисовал.
К>Ну и плюс обход списка через рекурсию (если ты ещё не в курсе), как и почти все манипуляции со списками.

Хм. Может я неправильно понимаю абстракцию списка или задачу? Что значит "средневзвешенная сложность ... равна O(1)" ? Взвешенная по чему? Множитель сложности же игнорируется, как её вообще можно взешивать? Или это подразумевает, что время на get/put может в разных случаях значительно отличаться, но всё ранвно не зависит от N?
"обход списка через рекурсию" — это O(N) или O(N^2) ?

Здравствуйте, Mazay, Вы писали:

M>Здравствуйте, Курилка, Вы писали:

G>>>>>>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>>>>>>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

К>>>>Эээ, никаких указателей нет, всё что ты можешь со списком по сути — взять голову и/или передвинуться на след. элемент списка.

M>>>А как в него помещаются элементы? К голове подклеиваются?

К>>Конечно, Гапертон правильную идею со стэком нарисовал.
К>>Ну и плюс обход списка через рекурсию (если ты ещё не в курсе), как и почти все манипуляции со списками.

M>Хм. Может я неправильно понимаю абстракцию списка или задачу? Что значит "средневзвешенная сложность ... равна O(1)" ? Взвешенная по чему? Множитель сложности же игнорируется, как её вообще можно взешивать? Или это подразумевает, что время на get/put может в разных случаях значительно отличаться, но всё ранвно не зависит от N?
Про это объяснять, надеюсь не надо?
В данном случае будет справедливо последнее утверждение — "время на get/put может в разных случаях значительно отличаться, но всё равно не зависит от N"
M> "обход списка через рекурсию" — это O(N) или O(N^2) ?
Интересно, как ты хочешь обойти список длинной в N элементов, затратив на это N^2 операций? Точней интереснее — зачем?
Про обход — это было "вспомогательное" замечание, к задаче Гапертона не относящееся непосредственно, просто, складывается впечатление, что оперирование списками (как в ФП принято) для тебя не очень знакомо и ты "скатываешься" к императивным методам — указателям и т.п.

Здравствуйте, Курилка, Вы писали:

К>Здравствуйте, Mazay, Вы писали:

M>>Здравствуйте, Курилка, Вы писали:

G>>>>>>>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>>>>>>>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

К>>>>>Эээ, никаких указателей нет, всё что ты можешь со списком по сути — взять голову и/или передвинуться на след. элемент списка.

M>>>>А как в него помещаются элементы? К голове подклеиваются?

К>>>Конечно, Гапертон правильную идею со стэком нарисовал.
К>>>Ну и плюс обход списка через рекурсию (если ты ещё не в курсе), как и почти все манипуляции со списками.

M>>Хм. Может я неправильно понимаю абстракцию списка или задачу? Что значит "средневзвешенная сложность ... равна O(1)" ? Взвешенная по чему? Множитель сложности же игнорируется, как её вообще можно взешивать? Или это подразумевает, что время на get/put может в разных случаях значительно отличаться, но всё ранвно не зависит от N?
К>Про это объяснять, надеюсь не надо?
ну может и надо. Да ладно, я просто к словам придрался, понятно что имелось ввиду среднее время, а не сложность.
К>В данном случае будет справедливо последнее утверждение — "время на get/put может в разных случаях значительно отличаться, но всё равно не зависит от N"
M>> "обход списка через рекурсию" — это O(N) или O(N^2) ?
К>Интересно, как ты хочешь обойти список длинной в N элементов, затратив на это N^2 операций? Точней интереснее — зачем?
Нууу Самый тупой подход — мне нужен последний элемент в списке, значит нужно N рекурентных вызовов чтоб пропустить N элементов впереди. Каждый вызов имеет сложность N, так как вызывает копирование массива при передаче его в качестве параметра (у нас же по указателю передачи нет, так?).

К>Про обход — это было "вспомогательное" замечание, к задаче Гапертона не относящееся непосредственно, просто, складывается впечатление, что оперирование списками (как в ФП принято) для тебя не очень знакомо и ты "скатываешься" к императивным методам — указателям и т.п.
К императивщине я скатываюсь потому что не понимаю как в ФЯ считать сложность. Конечно, я интуитивно понимаю, что так считать сложность, как я это сделал с обходом списка, нельзя, но как тогда?

Здравствуйте, Mazay, Вы писали:

M>Здравствуйте, Курилка, Вы писали:

К>>Здравствуйте, Mazay, Вы писали:

M>>> "обход списка через рекурсию" — это O(N) или O(N^2) ?
К>>Интересно, как ты хочешь обойти список длинной в N элементов, затратив на это N^2 операций? Точней интереснее — зачем?
M>Нууу Самый тупой подход — мне нужен последний элемент в списке, значит нужно N рекурентных вызовов чтоб пропустить N элементов впереди. Каждый вызов имеет сложность N, так как вызывает копирование массива при передаче его в качестве параметра (у нас же по указателю передачи нет, так?).

Нет, каждый вызов есть переход на 1 шаг, т.к. шагов N, то и сложность O(N)
Я могу код привести, но если ты с не с одним языком не знаком, то хз на чём
Ну вот допустим на чём-то сиподобном:

A last(List list) {
  (Head, Rest) = list.cut_head(); // тут мы список "делим" на "голову" и остаток, в ФП это делается обычно при помощи pattern matching
  if(Rest.is_empty()) {
    return Head; // последняя "голова" и есть последний элемент списка
  } else {
    return last(Rest);
  }
}

В общем — попробуй пописать на каком-нибудь функциональном языке, а то я так совсем элементарные вещи объясняю, лучше их по туториалам смотреть.

К>>Про обход — это было "вспомогательное" замечание, к задаче Гапертона не относящееся непосредственно, просто, складывается впечатление, что оперирование списками (как в ФП принято) для тебя не очень знакомо и ты "скатываешься" к императивным методам — указателям и т.п.
M>К императивщине я скатываюсь потому что не понимаю как в ФЯ считать сложность. Конечно, я интуитивно понимаю, что так считать сложность, как я это сделал с обходом списка, нельзя, но как тогда?
Сложность в императиве и функциональщине считается одинаково, если есть операция, то её надо учитывать.

Здравствуйте, Mazay, Вы писали:

Речь шла об иммутабельных списках. Никаких переменных и "при этом в ... пишется"

Здравствуйте, Mazay, Вы писали:

M>Совсем забывать про структуру данных нельзя, потому что могут родиться вот такие кошмары: evaluate w :: World -> World. Очень, кстати, математическое выражение, только не учитывающе реалии железа.
M>Но в общем идея понятна — надо менять мышление.

Это НЕ кошмар

Например, операция вставки в Map (или другую чистую структуру данных) создаёт новый Map. Простой пример, чтобы было понятно о чём речь — вставка в голову списка — операция O(1), а ведь мы получаем новый список!

Здравствуйте, Mazay, Вы писали:

M>Нууу Самый тупой подход — мне нужен последний элемент в списке, значит нужно N рекурентных вызовов чтоб пропустить N элементов впереди. Каждый вызов имеет сложность N, так как вызывает копирование массива при передаче его в качестве параметра (у нас же по указателю передачи нет, так?).

Указателей нет, но есть неизменяемые и неподдающиеся адресной арифметике ссылки на объекты.