недостаток чистой функции в функциональном программировании
Чистая функция в функциональном программировании — это та, которая не имеет побочных эффектов. Одним из значений этого является то, что он не может изменять значения входных параметров. Может ли это рассматриваться как недостаток использования памяти?
например Допустим, у меня есть функция, которая просто берет список и добавляет в него еще один элемент. В C ++ это может быть так просто, как
void addElem(std::vector& vec, int a)
{
vec.insert(a);
}
Эта функция явно не использует много памяти, чем уже занято переданным объектом.
Но то же самое в Хаскелле придет к чему-то подобному.
addElem :: [Int] -> Int -> [Int] addElem xs a = xs ++ [a]
Теперь в этом вычислении значение xs не меняет своего значения. Поэтому я прав, говоря, что в какой-то момент функция будет использовать в памяти двойной размер xs, один для xs и другой для возвращаемого значения. Или как-то ленивый вызов гарантирует, что на самом деле xs возвращается только путем добавления только одного элемента в конце?
Я знаю, что Monad — это способ получить что-то, что может иметь побочный эффект. Но можно ли использовать Monad для простого изменения ввода и возврата его значения?
Также может ли изменение xs ++ [a] на a: xs потреблять меньше памяти?
Решение
Чистота подразумевает, что функция не может делать разрушительные обновления, поэтому если
xs ++ [a]
полностью оценена, копия xs должны быть сделаны. Это может произойти в постоянном пространстве, если xs лениво генерируется и на него больше не ссылаются, так что его можно собирать мусором при его создании. Или это может понадобиться копия помимо xs — но чистота позволяет ячейкам обоих списков указывать на одни и те же данные, поэтому копировать данные не нужно, а только позвоночник (с поправками на последние доводы). Но если копия сделана, старое значение xs все еще доступен.
Также может ли изменение xs ++ [a] на a: xs потреблять меньше памяти?
Да, это можно просто использовать повторно xsвсе, что нужно, это создать новую ячейку списка и позволить указателю хвоста указывать на xs,
Из комментария:
Я не хочу, чтобы функция C ++ была чистой. Я хочу, чтобы это изменило состояние ввода. И это то, чем я хотел быть весь вопрос.
В этом случае вам нужно нечистый Функция / действие. Это возможно для некоторых структур данных, но для списков ячейки должны быть скопированы / созданы заново. Но добавление элемента в std::vector<T> может также потребоваться перераспределение.
Другие решения
Да, чистый FP может потреблять больше памяти, чем императивное программирование, хотя это зависит от того, как вы пишете свои программы и насколько умен ваш компилятор. Компиляторы Haskell, в частности, имеют очень сильные оптимизаторы и могут преобразовывать чистый код FP в довольно эффективный машинный код, который повторно использует выделенную память. Это требует написания хорошего кода FP, так как даже самый умный компилятор не будет включать в себя оптимизации для обработки программ, которые просто имитируют императивные с поверхностно подобными конструкциями FP.
Имейте в виду, ваш пример C ++ неверен. Если бы вы имели в виду
v[0] = a; // assuming v.size() > 0
тогда это не делает никакого распределения. Если бы вы имели в виду
v.append(a);
тогда это может или не может распределить, в зависимости от возможностей v,
Или как-то ленивый вызов гарантирует, что на самом деле xs возвращается только путем добавления только одного элемента в конце?
Зависит от реализации и использования выражения в его контексте. когда xs ++ [a] полностью оценен, копирует весь список xs, Если он частично оценен, он может выполнить любое количество распределений между len(xs),
Также может ли изменение xs ++ [a] на a: xs потреблять меньше памяти?
Да, это меняет его с O (n) наихудшего случая на O (1) наихудшего распределения / использования дополнительной памяти. То же самое касается сложности времени. При обработке списков в Haskell никогда не добавляйте в конец. Если это то, что вам нужно, используйте список различий.
Я думаю, что существенное различие между вашими двумя примерами заключается в выборе структуры данных, а не в вопросе «чистый против нечистого» сам по себе.
Вы можете иметь односвязные списки в обоих подходах, и вы можете иметь массивы с постоянным обновлением времени в обоих. В чистом случае обновление структуры данных может семантически сделать копию, но это не обязательно означает, что это так физически.
Канаты, например, представляют собой вариант неизменяемых массивов, который допускает конкатенацию с постоянным временем. Вы также можете иметь неизменную абстракцию массива с функциональным обновлением постоянного времени (где a.set (i, x) семантически возвращает копию), используя внутреннюю схему копирования при записи, которая выполняет физическое копирование, только если вы действительно обращаетесь к старый версия после создания новой (т. е. если вы используете возможность сохранения чистой структуры данных, которая недоступна в нечистом случае).
акт рассмотрения чего-либо как общего качества или характеристики, за исключением конкретных реальностей, конкретных объектов или реальных случаев.
балансировка факторов, которые все не достижимы одновременно
Все нетривиальные абстракции, в какой-то степени, негерметичны.
Функциональное программирование можно рассматривать как абстракцию, и поскольку все абстракции просачиваются, необходимо сделать некоторые компромиссы.
Теперь в этом вычислении значение xs не меняет своего значения. Поэтому я прав, говоря, что в какой-то момент функция будет использовать в памяти двойной размер xs, один для xs и другой для возвращаемого значения.
Не обязательно. Преимущество наличия неизменных данных заключается в том, что ими можно делиться. Таким образом, компиляторы могут оптимизировать, разделяя xs в таком случае. Таким образом, размер останется таким же, как в случае с ++.
Или как-то ленивый вызов гарантирует, что на самом деле xs возвращается только путем добавления только одного элемента в конце?
Лень просто означает оценку, когда значение действительно требуется, это не гарантирует меньшее использование памяти. С другой стороны, громоотводы, созданные из-за лени, могут использовать больше памяти.
Я знаю, что Monad — это способ получить что-то, что может иметь побочный эффект. Но можно ли использовать Monad для простого изменения ввода и возврата его значения?
Вы частично правы. Монады используются для составления кода, имеющего побочные эффекты. Вы можете очень хорошо использовать изменяемый вектор и писать код, очень похожий на ваш пример с ++ в монаде IO.
Также может ли изменение xs ++ [a] на a: xs потреблять меньше памяти?
Это зависит от компилятора, но я думаю, что он скопирует весь список и добавит элемент в конце. (Я не эксперт в этом).
Вы всегда можете профилировать свой код и проверить потребление памяти, что является лучшим способом узнать это.
Разные языки имеют разные общие идиомы, и
Разработчики работают, чтобы сделать эти идиомы максимально эффективными.
я мог бы не предположим, что потому что что-то влечет за собой
накладные расходы в C ++, то же самое было бы верно для другого языка,
так же, как я бы не предположил, что наиболее эффективные идиомы в
другой язык будет наиболее эффективным в C ++.
Сказав это: я в настоящее время работаю над большим, высоким
приложение производительности, куда мы часто возвращаемся std::vector, а также
мы не обнаружили в этом проблемы. Такие вещи, как NRVO и двигаться
семантика в конечном итоге означает, что это может быть очень эффективным в C ++
также.