pseudorandom на ФЯ
Лень zip распаковывать, давай сюда описание.
описания нет под руками, только код:
DP NR::ran1(int &idum)
{
const int IA=16807,IM=2147483647,IQ=127773,IR=2836,NTAB=32;
const int NDIV=(1+(IM-1)/NTAB);
const DP EPS=3.0e-16,AM=1.0/IM,RNMX=(1.0-EPS);
static int iy=0;
static Vec_INT iv(NTAB);
int j,k;
DP temp;
if (idum <= 0 || !iy) {
if (-idum < 1) idum=1;
else idum = -idum;
for (j=NTAB+7;j>=0;j--) {
k=idum/IQ;
idum=IA*(idum-k*IQ)-IR*k;
if (idum < 0) idum += IM;
if (j < NTAB) iv[j] = idum;
}
iy=iv[0];
}
k=idum/IQ;
idum=IA*(idum-k*IQ)-IR*k;
if (idum < 0) idum += IM;
j=iy/NDIV;
iy=iv[j];
iv[j] = idum;
if temp=AM*iy) > RNMX) return RNMX;
else return temp;
}
Чисто функциональных массивов не бывает, нужно менять на дерево или типа того.
Не понял, зачем idum вынесено в параметр, в то время как остальное состояние спрятано внутри.
Ну, я copy-paste сделал. idum вынесено в параметр, я так понимаю, только потому, что значительная часть других, более или менее примитивных генераторы из этой книги не имеют своего скрытого в static состояния. В общем-то на этом зацикливаться не стоит.
вопрос тогда вот в чем: будет ли такая правильная в плане идеологии реализация более быстрой, чем как бы "императивная"?
Просто мне захотелось вкусить всех прелестей ФЯ, и для этого переписать какую-нибудь задачку с C/C++ на Ocaml чтобы сравнить. А так уж получается что задачки у меня почти все сводятся к N-мерному монте-карло, и рандом там нужен очень качественный и быстрый.
Просто мне захотелось вкусить всех прелестей ФЯ, и для этого переписать какую-нибудь задачку с C/C++ на Ocaml чтобы сравнить. А так уж получается что задачки у меня почти все сводятся к N-мерному монте-карло, и рандом там нужен очень качественный и быстрый.
я бы написал на С, а наружу вынес чистый интерфейс
быстрее не будет, конечно
быстрее не будет, конечно
На RAN1 забей, возьми что-нибудь поприличнее.
На ML сразу не скажу.
Делал такое, работает.
На ML надо подумать.
---
...Я работаю антинаучным аферистом...
На ML сразу не скажу.
(define rng
(let state ...
(lambda ' (set! state ...)
(ret-val state
Делал такое, работает.
На ML надо подумать.
---
...Я работаю антинаучным аферистом...
> Чисто функциональных массивов не бывает, нужно менять на дерево или типа того.
Можно пояснить? Вроде же в большинстве ФЯ есть массивы. Или они там какие-то не полноценные?
Чем дерево лучше чем массив?
Можно пояснить? Вроде же в большинстве ФЯ есть массивы. Или они там какие-то не полноценные?
Чем дерево лучше чем массив?
Standard ML of New Jersey v110.52 [built: Fri Feb 4 23:33:34 2005]
- local val x = ref 1 in fun gen = (x:=(!x)+1; !x) end;
val gen = fn : unit -> int
- gen ;
val it = 2 : int
- gen ;
val it = 3 : int
- gen ;
val it = 4 : int
- gen ;
val it = 5 : int
Оно?
---
...Я работаю антинаучным аферистом...
Поясняю: "Акела промахнулся!.."
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
В массивах обновления деструктивные: изменяя значение элемента - теряем старое значение.
У функциональных массивов интерфейс должен быть примерно такой:
В книжке Окасаки приводятся реализации такого на деревьях, со сложностью
операций get и change порядка ln(длина).
А если нужны настоящие массивы, нужно писать императивно.
У функциональных массивов интерфейс должен быть примерно такой:
type 'a farray
val get : 'a farray -> int -> 'a
val change : 'a farray -> int -> 'a -> ('a farray * 'a)
В книжке Окасаки приводятся реализации такого на деревьях, со сложностью
операций get и change порядка ln(длина).
А если нужны настоящие массивы, нужно писать императивно.
> В массивах обновления деструктивные: изменяя значение элемента - теряем старое значение.
Обновления у любых типов данных деструктивные, на то они и обновления. Если в дереве заменить поддерево, то старое поддерево тоже теряется. Или я чего-то не понимаю? Рассматриваются не все обновления, а какие-то специфические?
> А если нужны настоящие массивы, нужно писать императивно
Как тогда выкручиваются чистые ФЯ?
Обновления у любых типов данных деструктивные, на то они и обновления. Если в дереве заменить поддерево, то старое поддерево тоже теряется. Или я чего-то не понимаю? Рассматриваются не все обновления, а какие-то специфические?
> А если нужны настоящие массивы, нужно писать императивно
Как тогда выкручиваются чистые ФЯ?
> Обновления у любых типов данных деструктивные, на то они и обновления.
Поэтому в чистых функциях обновлений не бывает.
> Если в дереве заменить поддерево, то старое поддерево тоже теряется.
Вместо этого создают новое дерево, разделяющее часть вершин (почти все) со старым.
> Как тогда выкручиваются чистые ФЯ?
Не знаю, я их не изучал.
Поэтому в чистых функциях обновлений не бывает.
> Если в дереве заменить поддерево, то старое поддерево тоже теряется.
Вместо этого создают новое дерево, разделяющее часть вершин (почти все) со старым.
> Как тогда выкручиваются чистые ФЯ?
Не знаю, я их не изучал.
Вместо этого создают новое дерево, разделяющее часть вершин (почти все) со старым.Каким образом это происходит? Заново ли создается ссылочная структура нового дерева? Или она тоже как-то разделяется?
Если обеспечить примитивы работы с массивами, то получим
функционализм в его исконном, от Джона Бекуса смысле.
См. SRFI 25.
---
...Я работаю антинаучным аферистом...
функционализм в его исконном, от Джона Бекуса смысле.
См. SRFI 25.
---
...Я работаю антинаучным аферистом...
> Вместо этого создают новое дерево, разделяющее часть вершин (почти все) со старым.
А, кажется, понял. То есть в случае дерева создать новое дерево с нужными изменением - быстрая операция (O(1) время) и поэтому так делают. А в случае массива создать новый массив и одним измененным элементом требует O(N) памяти и времени, и поэтому так не делают. Правильно?
То есть разница не в каком-то принципиальном отличии в структуре данных, а в том, сколько времени требуется на единичное недеструктивное обновление? Если бы время выполнения не играло роли то ФЯ легко бы реализовывали массивы?
А, кажется, понял. То есть в случае дерева создать новое дерево с нужными изменением - быстрая операция (O(1) время) и поэтому так делают. А в случае массива создать новый массив и одним измененным элементом требует O(N) памяти и времени, и поэтому так не делают. Правильно?
То есть разница не в каком-то принципиальном отличии в структуре данных, а в том, сколько времени требуется на единичное недеструктивное обновление? Если бы время выполнения не играло роли то ФЯ легко бы реализовывали массивы?
"Выкручиваются" обычным образом: обрабатываются массивы целиком,
а не поэлементно. ILP в действии.
---
...Я работаю антинаучным аферистом...
а не поэлементно. ILP в действии.
---
...Я работаю антинаучным аферистом...
Процедуры работы с массивами? В ФЯ? А как же отсуствие side effects? Или массивы каждый раз конструируются заново(при добавлении/изменении элементов)?
в случае дерева создать новое дерево с нужными изменением - быстрая операция (O(1) время)Может быть я туплю, но как это возможно?
Ответы на два твоих последних поста оставляются в качестве домашнего упражнения.
Прикинь, да?
---
"Narrowness of experience leads to narrowness of imagination."
Rob Pike
---
"Narrowness of experience leads to narrowness of imagination."
Rob Pike
Сразу скажу что я в ФЯ не разбираюсь, тем более не знаю как они реализуются.
Но вот это IMHO как раз простая задача. В каждую клетку встраивается какой-нибудь reference counter, и потом делается copy-on-write. Если refcount=1, то меняем. Если >1 ,то создаем копию и ее меняем, у оргининала refcount уменьшается. Довольно традиционный метод не связанный с ФЯ.
Но вот это IMHO как раз простая задача. В каждую клетку встраивается какой-нибудь reference counter, и потом делается copy-on-write. Если refcount=1, то меняем. Если >1 ,то создаем копию и ее меняем, у оргининала refcount уменьшается. Довольно традиционный метод не связанный с ФЯ.
Хммм... Почему-то от вас, функциональщиков очень сложно получить ответы на прямо поставленные вопросы... К чему бы это?
По первому вопросу у меня есть единственное предложение - новое дерево создается с корнем в новой вершине. По второму - это полный бред. Классические массивы невозможны(с более менее нормальной эффективностью) в ФЯ.
По первому вопросу у меня есть единственное предложение - новое дерево создается с корнем в новой вершине. По второму - это полный бред. Классические массивы невозможны(с более менее нормальной эффективностью) в ФЯ.
> Классические массивы невозможно (с более-менее нормальной
> эффективностью) в ФЯ.
Про Джона Бекуса что-нибудь слышал?
---
"Narrowness of experience leads to narrowness of imagination."
Rob Pike
> эффективностью) в ФЯ.
Про Джона Бекуса что-нибудь слышал?
---
"Narrowness of experience leads to narrowness of imagination."
Rob Pike
> По первому вопросу у меня есть единственное предложение - новое дерево создается с корнем в новой вершине.
Ну вот, можешь же, если захочешь.
> Классические массивы невозможны(с более менее нормальной эффективностью) в ФЯ.
Точнее, некоторые алгоритмы на массивах не реализуются с нормальной эффективностью без
использования элементов императивного программирования.
Ну вот, можешь же, если захочешь.
> Классические массивы невозможны(с более менее нормальной эффективностью) в ФЯ.
Точнее, некоторые алгоритмы на массивах не реализуются с нормальной эффективностью без
использования элементов императивного программирования.
Поправки принимаю. Суть претензии от этого не меняется. Понятное дело что если мне нужно последовательно обойти массив, это одно, а если мне нужен произвольный доступ на чтение/запись - это совсем другое.
Ну тут вроде никто не призывает полностью отказаться от императивного программирования, это и невозможно.
Точнее, для работы с массивами нужен немного иной, не такой,
как для списков, набор примитивов.
---
...Я работаю антинаучным аферистом...
как для списков, набор примитивов.
---
...Я работаю антинаучным аферистом...
Вот кстати в linux-kernel одно время обсуждали план создания новой файловой системы,
с журналированием, основанным на этом принципе.
Вся файловая система лежит в дереве, а модификации приводят к копированию вершин,
начиная с данной и вверх. Таким образом, получается второй корень, из которого вырастает
дерево, в основном совпадающее со старым.
В какой-то момент просто берём и атомарно меняем в суперблоке указатель на корень,
после чего устаревшие части дерева можно удалять.
Некто Daniel Phillips этим занимался, и называл это phase tree, но похоже забил.
с журналированием, основанным на этом принципе.
Вся файловая система лежит в дереве, а модификации приводят к копированию вершин,
начиная с данной и вверх. Таким образом, получается второй корень, из которого вырастает
дерево, в основном совпадающее со старым.
В какой-то момент просто берём и атомарно меняем в суперблоке указатель на корень,
после чего устаревшие части дерева можно удалять.
Некто Daniel Phillips этим занимался, и называл это phase tree, но похоже забил.
> Точнее, для работы с массивами нужен немного иной, не такой,
> как для списков, набор примитивов.
Который не очень эффективно отображается на низкоуровневые операции,
поддерживаемые процессором?
> как для списков, набор примитивов.
Который не очень эффективно отображается на низкоуровневые операции,
поддерживаемые процессором?
Кто тебе такое сказал?
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
Я не знаю, про какие примитивы ты говоришь, но в SRFI-25 описаны обычные императивные массивы.
Из SRFI 25 есть ссылка на библиотеку, показывающую,
как это должно работать.
Возьмём для примера набор от Джона Бекуса, со свёртками,
массовыми отображениями и т. п.
Что именно сильно хуже ложится на процессор по сравнению с Фортраном?
---
...Я работаю антинаучным аферистом...
как это должно работать.
Возьмём для примера набор от Джона Бекуса, со свёртками,
массовыми отображениями и т. п.
Что именно сильно хуже ложится на процессор по сравнению с Фортраном?
---
...Я работаю антинаучным аферистом...
Там довольно много ссылок.
Какая из них ведёт прямо на эти мифические примитивы?
Какая из них ведёт прямо на эти мифические примитивы?
ну в общем да, я примерно к такому варианту и склонился сам в итоге. просто говорю же, как-то некомфортно от этого, но похоже с random по-другому не получится.
Кстати, при наличии диска бесконечной ёмкости, старые деревья удалять не надо 
Вот некий гуру дисков (забыл фамилию, в соседнем разделе я как-то линк постил обещал такие диски.
То есть ёмкость можно повысить примерно в 1000 раз относительно нынешних, а скорость - только в 10 раз.
Забить полностью такой диск - грубо говоря, месяц непрерывной записи.
Поэтому файловая система (почти) без операций удаления придётся как нельзя кстати.
Вот некий гуру дисков (забыл фамилию, в соседнем разделе я как-то линк постил обещал такие диски.
То есть ёмкость можно повысить примерно в 1000 раз относительно нынешних, а скорость - только в 10 раз.
Забить полностью такой диск - грубо говоря, месяц непрерывной записи.
Поэтому файловая система (почти) без операций удаления придётся как нельзя кстати.
ну то есть это не то место, где ты получишь преимущества от ФП
ведь уже написан код на C
преимущество ты сможешь получить там, где будут сложные преобразования,
которые на С написать трудно
если таких в задаче нет - правильно написал
если есть - ты сможешь сэкономить на времени проектирования и отладки
ведь уже написан код на C
преимущество ты сможешь получить там, где будут сложные преобразования,
которые на С написать трудно
если таких в задаче нет - правильно написал
если есть - ты сможешь сэкономить на времени проектирования и отладки
ran1 в данном случае - как наиболее простой представитель. кроме того, в том коде который переписать для эксперимента захотелось имеено он и использовался. а так, конечно, более сложные вещи тоже использую.
P.S. Как-то коряво, но сейчас пользуюсь такой реализацией, практически императивной, на родных Ocaml'евских массивах:
P.S. Как-то коряво, но сейчас пользуюсь такой реализацией, практически императивной, на родных Ocaml'евских массивах:
class random_number init_idum =
let ntab = 32 in
let iq = 127773l in
let im = 2147483647l in
let ir = 2836l in
let ia = 16807l in
let am = 1.0 /. (Int32.to_float im) in
let ndiv = Int32.succ (Int32.div (Int32.pred im) (Int32.of_int ntab in
let rnmx = 1.0 -. 1.2e-7 in
object (self)
val mutable idum = Int32.of_int init_idum
val mutable iy = 0l
val mutable iv = Array.create ntab 0l
method init_random =
let rec loop j =
if j >= 0 then
begin
let k = Int32.div idum iq in
idum <- (Int32.sub (Int32.mul ia (Int32.sub idum (Int32.mul k iq (Int32.mul ir k) );
idum <- if idum < 0l then Int32.add idum im else idum ;
if ( j < ntab ) then ( iv.(j) <- idum ) ;
loop (j-1)
end
in
idum <- if( idum = 0l ) then 1l else (Int32.neg idum) ;
loop (ntab+7) ;
iy <- iv.(0)
method random1 =
if ( iy = 0l or idum < 0l ) then self#init_random ;
let k = Int32.div idum iq in
idum <- Int32.sub (Int32.mul ia (Int32.sub idum (Int32.mul k iq (Int32.mul ir k) ;
if idum < 0l then ( idum <- (Int32.add idum im) ) ;
let j = Int32.to_int (Int32.div iy ndiv) in
iy <- iv.(j);
iv.(j) <- idum;
let temp = am *. (Int32.to_float iy) in
if temp > rnmx then rnmx else temp
end ;;
Да да, это я тоже прекрасно понимаю. В задаче есть преобразования, которые на C записываются весьма громоздко, так что дальше будет интереснее.
А с рандомом - это вообще говоря был больше академический чем практический интерес.
А с рандомом - это вообще говоря был больше академический чем практический интерес.
Я бы наверное попытался обернуть в виде потока (который stream, реализованный на camlp4).
Никогда не использовал потоки, интересно
Никогда не использовал потоки, интересно
"Мифические примитивы" описаны, например, у Хендерсона.
"Функциональное программирование," насколько помню.
Отголоски можно найти, разумеется на DMoz:
http://dmoz.org/Computers/Programming/Languages/Functional/
ссылка "FP".
Есть ещё страшные языки APL, J, K, R, S и т. п.
---
...Я работаю антинаучным аферистом....
"Функциональное программирование," насколько помню.
Отголоски можно найти, разумеется на DMoz:
http://dmoz.org/Computers/Programming/Languages/Functional/
ссылка "FP".
Есть ещё страшные языки APL, J, K, R, S и т. п.
---
...Я работаю антинаучным аферистом....
Пока у меня нет желания просматривать по очереди сотни ссылок, не зная, на что обращать внимание.
Так что остаюсь при своём мнении.
Так что остаюсь при своём мнении.
Ещё наверное имеет смысл сделать копирование всего состояния,
и получить чистый интерфейс.
Этого состояния там всего 1088 бит, если не ошибаюсь, так что по сравнению
с этим ужасом - ничего страшного.
и получить чистый интерфейс.
Этого состояния там всего 1088 бит, если не ошибаюсь, так что по сравнению
с этим ужасом - ничего страшного.
>Обновления у любых типов данных деструктивные, на то они и обновления. Если в дереве заменить поддерево, то старое поддерево тоже теряется. Или я чего-то не понимаю? Рассматриваются не все обновления, а какие-то специфические?
Да, теряется, если нет других ссылок.
>Как тогда выкручиваются чистые ФЯ?
В чистых ФЯ используются или монады (Хаслель) или специальный синтаксис в языке (Clean где ты прямо указываешь компилятору, что на массив есть только одна ссылка.
Кстати, меня сильно впечатлило, как в Хаскель происходит сопряжение IO монады с Real World. Я думал, это сделано на уровне компилятора, а оказывается там действительно все чисто функционально.
Да, теряется, если нет других ссылок.
>Как тогда выкручиваются чистые ФЯ?
В чистых ФЯ используются или монады (Хаслель) или специальный синтаксис в языке (Clean где ты прямо указываешь компилятору, что на массив есть только одна ссылка.
Кстати, меня сильно впечатлило, как в Хаскель происходит сопряжение IO монады с Real World. Я думал, это сделано на уровне компилятора, а оказывается там действительно все чисто функционально.
>>Процедуры работы с массивами? В ФЯ? А как же отсуствие side effects? Или массивы каждый раз конструируются заново(при добавлении/изменении элементов)?
В обычных ФЯ массивы императивны (хотя есть и copy-on-write для извращенцев). В чистых ФЯ обеспечивается наличие только одной ссылки на массив, что позволяет их модифицировать без копирования.
В обычных ФЯ массивы императивны (хотя есть и copy-on-write для извращенцев). В чистых ФЯ обеспечивается наличие только одной ссылки на массив, что позволяет их модифицировать без копирования.
> В обычных ФЯ массивы императивны (хотя есть и copy-on-write для извращенцев).
Я как-то пытался сделать хитрый массив для переборных алгоритмов.
Типа чтоб интерфейс чистый, как я выше написал, но обновление и выборка за O(1).
Хитрость в том, что откат назад (то есть доступ по старой ссылке) дольше чем O(1
а именно O(число шагов отката). Таким образом, откат назад на 1 шаг, как нужно в переборе, тоже быстрый.
Идея такая, что есть один императивный массив, а от каждой ссылки к нему тянется цепочка обновлений,
то есть типа журнал.
Не доделал, заломало
Я как-то пытался сделать хитрый массив для переборных алгоритмов.
Типа чтоб интерфейс чистый, как я выше написал, но обновление и выборка за O(1).
Хитрость в том, что откат назад (то есть доступ по старой ссылке) дольше чем O(1
а именно O(число шагов отката). Таким образом, откат назад на 1 шаг, как нужно в переборе, тоже быстрый.
Идея такая, что есть один императивный массив, а от каждой ссылки к нему тянется цепочка обновлений,
то есть типа журнал.
Не доделал, заломало
>>По первому вопросу у меня есть единственное предложение - новое дерево создается с корнем в новой вершине. По второму - это полный бред. Классические массивы невозможны(с более менее нормальной эффективностью) в ФЯ.
Возможны даже в чистых ФЯ (У меня решето Эратосфена на haskell работало всего в пару-тройку раз медленнее чем на С, а у другого чувака на Clean работало почти также быстро). Но работать с ними там труднее.
Возможны даже в чистых ФЯ (У меня решето Эратосфена на haskell работало всего в пару-тройку раз медленнее чем на С, а у другого чувака на Clean работало почти также быстро). Но работать с ними там труднее.
В OCaml разве не такие массивы (со следом изменений каждого элемента)?
Там обычные массивы.
Вот это вот:
Factor, factor and factor.
У меня где-то было оно.
Возможно, что в недоделанном виде.
---
...Я работаю антинаучным аферистом...
это сдвиг Бернулли, множитель ia, делитель im.
let iq = 127773l in
let im = 2147483647l in
let ir = 2836l in
let ia = 16807l in
Factor, factor and factor.
У меня где-то было оно.
Возможно, что в недоделанном виде.
---
...Я работаю антинаучным аферистом...
Да, общий вывод от написанного:
"Real Programmer can write FORTRAN in _any_ language."
---
...Я работаю антинаучным аферистом...
"Real Programmer can write FORTRAN in _any_ language."
---
...Я работаю антинаучным аферистом...
Лучше писать так
let ntab = 32 in
let iq = 127773l in
let im = 2147483647l in
let ir = 2836l in
let ia = 16807l in
let ntab = 32 and
iq = 127773l and
im = 2147483647l and
ir = 2836l and
ia = 16807l in
Лучше всего --- обнаружить, что ir = im mod ia, iq = im div ia,
а то, как оно используется, описывается словами так:
---
"Истина грядёт --- её ничто не остановит!"
а то, как оно используется, описывается словами так:
ia um* im um/mod drop.
---
"Истина грядёт --- её ничто не остановит!"
Может, тебе поможет.
На первый взгляд (я смотрю в GNU SL оно выглядит так:
---
"...Видный ретроград-новатор."
На первый взгляд (я смотрю в GNU SL оно выглядит так:
При условии, что "1 cells 4 =".
: next ia um* im um/mod drop ;
: shuffled ... ; ( то, зачем у тебя ntab, ndiv, j и т. д. )
: rand x @ next dup x ! shuffled ;
---
"...Видный ретроград-новатор."
>> А если нужны настоящие массивы, нужно писать императивно
> Как тогда выкручиваются чистые ФЯ?
inplace array update реализуется через монады
операции с монадами устроены так, что состояние объекта спрятано внутри некоторой структуры
и отдаётся наружу не целиком, а только частями, таким образом гарантируется отсутствие
внешних ссылок на состояние и его можно менять непосредственно,
иначе пришлось бы отслеживать число ссылок и производить копирование по необходимости
в частности, так устроен ввод/вывод, где состоянием является весь внешний мир,
тем не менее описывать этот внешний мир не нужно, т.к. он существует в единственном экземпляре,
а можно сразу производить над ним какие-нибудь действия
P.Wadler. Comprehending monads.
Imperative functional programming.
> Как тогда выкручиваются чистые ФЯ?
inplace array update реализуется через монады
операции с монадами устроены так, что состояние объекта спрятано внутри некоторой структуры
и отдаётся наружу не целиком, а только частями, таким образом гарантируется отсутствие
внешних ссылок на состояние и его можно менять непосредственно,
иначе пришлось бы отслеживать число ссылок и производить копирование по необходимости
в частности, так устроен ввод/вывод, где состоянием является весь внешний мир,
тем не менее описывать этот внешний мир не нужно, т.к. он существует в единственном экземпляре,
а можно сразу производить над ним какие-нибудь действия
P.Wadler. Comprehending monads.
Imperative functional programming.
> операции с монадами устроены так, что состояние объекта спрятано внутри некоторой структуры
> и отдаётся наружу не целиком, а только частями, таким образом гарантируется отсутствие
> внешних ссылок на состояние и его можно менять непосредственно,
> иначе пришлось бы отслеживать число ссылок и производить копирование по необходимости
Насколько я понимаю, у функций осуществляющих ввод/вывод, генерацию случайных чисел итп. возвращаемое значение меняется, вместо Int например она возвращает IO Int. Причем, нет совершенно никаких способов превратить этот IO Int обратно в Int. Если эта функция вызывается из другой функции, то та тоже вынуждена вовзвращать тип с префиксом IO.
В результате возникает такая проблема. Предположим у меня есть большая программа, с большим числом функций. Например A вызывает B, B вызывает C, С вызывает D итд до Z. Причем все функции обычные, без всяких IO. Пусть теперь реализация функции Z поменялась - она стала читать/писать файлы, использовать генератор случайных чисел итп. В результате поменяется тип ее возвращаемого значения: вместо Int станет IO Int или RangomGen Int или еще более сложный тип если она делает сразу много действий с разными объектами. То есть меняется интерфейс функции. Мало того, меняется интерфейс всех вышележащих функций Y, X, W, .. до A. Мы приходим к страшной вещи: изменение в деталях реализации одной мелкой низкоуровневой функции приводит к огромным изменениям во всей программе. Получается что мы не можем отделить интерфейс от реализации. Возникает очевидное противоречие с ОО-подходом.
Поясню: допустим у меня есть функция интегрирования:
f -> \int_a^b f(x) dx, которая на вход получает f:Double->Double, a, b и возвращает интеграл.
Я хочу написать несколько таких функций. Одна например интегрирует методом трапеций, другая - методом прямогоульников. Еще одна реализация использует метод Монте-Карло (случайные числа). Потом я захочу написать еще одну реализацию, которая запускает Maple, отдает ему функцию, считает в нем интгерал и получает результат.
В C++ можно объявить виртуальную функцию и потом ее перегружать в наследниках. Прототип будет всегда одинаков:
virtual double *integrate(double_fun_type f, double x, double y);
Здесь же получается что у одной функции результат IO Double, у другой RandomGen Double у третье - MapleServerIO Double. Я не могу упихать эти функции в один интерфейс. Что в результате делать с функциями Y, X, W, ... A ? Как быть с этой проблемой?
> и отдаётся наружу не целиком, а только частями, таким образом гарантируется отсутствие
> внешних ссылок на состояние и его можно менять непосредственно,
> иначе пришлось бы отслеживать число ссылок и производить копирование по необходимости
Насколько я понимаю, у функций осуществляющих ввод/вывод, генерацию случайных чисел итп. возвращаемое значение меняется, вместо Int например она возвращает IO Int. Причем, нет совершенно никаких способов превратить этот IO Int обратно в Int. Если эта функция вызывается из другой функции, то та тоже вынуждена вовзвращать тип с префиксом IO.
В результате возникает такая проблема. Предположим у меня есть большая программа, с большим числом функций. Например A вызывает B, B вызывает C, С вызывает D итд до Z. Причем все функции обычные, без всяких IO. Пусть теперь реализация функции Z поменялась - она стала читать/писать файлы, использовать генератор случайных чисел итп. В результате поменяется тип ее возвращаемого значения: вместо Int станет IO Int или RangomGen Int или еще более сложный тип если она делает сразу много действий с разными объектами. То есть меняется интерфейс функции. Мало того, меняется интерфейс всех вышележащих функций Y, X, W, .. до A. Мы приходим к страшной вещи: изменение в деталях реализации одной мелкой низкоуровневой функции приводит к огромным изменениям во всей программе. Получается что мы не можем отделить интерфейс от реализации. Возникает очевидное противоречие с ОО-подходом.
Поясню: допустим у меня есть функция интегрирования:
f -> \int_a^b f(x) dx, которая на вход получает f:Double->Double, a, b и возвращает интеграл.
Я хочу написать несколько таких функций. Одна например интегрирует методом трапеций, другая - методом прямогоульников. Еще одна реализация использует метод Монте-Карло (случайные числа). Потом я захочу написать еще одну реализацию, которая запускает Maple, отдает ему функцию, считает в нем интгерал и получает результат.
В C++ можно объявить виртуальную функцию и потом ее перегружать в наследниках. Прототип будет всегда одинаков:
virtual double *integrate(double_fun_type f, double x, double y);
Здесь же получается что у одной функции результат IO Double, у другой RandomGen Double у третье - MapleServerIO Double. Я не могу упихать эти функции в один интерфейс. Что в результате делать с функциями Y, X, W, ... A ? Как быть с этой проблемой?
> нет совершенно никаких способов превратить этот IO Int обратно в Int
есть, но в этом случае программист возлагает на себя ответственность
за отсутствие порядка выполнения между различными цепочками операций,
а также должен быть готов к приколам типа мемоизации
(наигрались с императивщиной? добро пожаловать обратно в функциональный мир)
эмоциональные передёргивания типа "большая программа", "маленькая функция" комментировать не буду
за исключением, пожалуй, этого:
> Возникает очевидное противоречие с ОО-подходом.
ну и хуй с ним!
> Здесь же получается что у одной функции результат IO Double,
> у другой RandomGen Double у третье - MapleServerIO Double.
> Я не могу упихать эти функции в один интерфейс.
> Что в результате делать с функциями Y, X, W, ... A ? Как быть с этой проблемой?
если делать по-нормальному, то такой проблемы нет
тип во всех случаях будет Double->Double)->Double->Double->Double)
а представлена она может быть в виде частичного применения какой-нибудь функции к некоторому объекту,
например (f rgs где f:: RandomGeneratorState -> (Double->Double)->Double->Double->Double
т.е. то же самое, что и в случае плюсов и даже лучше, т.к. нет уродского наследования
монады будут использоваться внутри f для описания последовательности действий над объектом
есть, но в этом случае программист возлагает на себя ответственность
за отсутствие порядка выполнения между различными цепочками операций,
а также должен быть готов к приколам типа мемоизации
(наигрались с императивщиной? добро пожаловать обратно в функциональный мир)
эмоциональные передёргивания типа "большая программа", "маленькая функция" комментировать не буду
за исключением, пожалуй, этого:
> Возникает очевидное противоречие с ОО-подходом.
ну и хуй с ним!
> Здесь же получается что у одной функции результат IO Double,
> у другой RandomGen Double у третье - MapleServerIO Double.
> Я не могу упихать эти функции в один интерфейс.
> Что в результате делать с функциями Y, X, W, ... A ? Как быть с этой проблемой?
если делать по-нормальному, то такой проблемы нет
тип во всех случаях будет Double->Double)->Double->Double->Double)
а представлена она может быть в виде частичного применения какой-нибудь функции к некоторому объекту,
например (f rgs где f:: RandomGeneratorState -> (Double->Double)->Double->Double->Double
т.е. то же самое, что и в случае плюсов и даже лучше, т.к. нет уродского наследования
монады будут использоваться внутри f для описания последовательности действий над объектом
А если ,
а не только просматривать,
то можно увидеть, что вовзращается тот же int.
---
...Я работаю антинаучным аферистом...
а не только просматривать,
то можно увидеть, что вовзращается тот же int.
---
...Я работаю антинаучным аферистом...
Если бы ты внимательно прочел, то заметил бы, что я говорю про чистые ФЯ.
А у тебя там всякие ref, !x Они сюда не не укладываются.
А у тебя там всякие ref, !x Они сюда не не укладываются.
> эмоциональные передёргивания типа "большая программа", "маленькая функция" комментировать не
> буду за исключением, пожалуй, этого:
Размер программы имеет большое значение. Мелкие программы для себя можно писать как угодно. Но программ размером в миллионы строк кода, которые разрабатывают одновременно сотни людей, требуют специальных методов. Иначе их разработка превратится в полный хаос. Непонимание этого обычно приводит к печальным последствиям.
Меня интересуют возможности ФЯ для написания больших программ, поэтому и возник такой вопрос. В частности, в больших программных системах очень важным становится гибкость, возможность изменения одного компонента независимого от других. ООП позволяет делать это путем разделения интерфейса (абстрактного предка) и реализаций в наследниках. В данном случае такой метод невозможен. Меня интересуют какие альтернативы предлагают ФЯ.
>> Возникает очевидное противоречие с ОО-подходом.
>ну и хуй с ним!
То есть, ФЯ не совместимо с ООП?
> например (f rgs где f:: RandomGeneratorState -> (Double->Double)->Double->Double->Double
> т.е. то же самое, что и в случае плюсов и даже лучше, т.к. нет уродского наследования
> монады будут использоваться внутри f для описания последовательности действий над объектом
Это опять возвращает нас к вопросу: если у меня есть некий MapleServerIO Double как я из него получу нормальный Double? Ведь вроде бы эти самые IO никак нельзя снять? Интересует возможность этого в чистых ФЯ, очевидно, что языки с императивными фичами легко позволяют это сделать.
> буду за исключением, пожалуй, этого:
Размер программы имеет большое значение. Мелкие программы для себя можно писать как угодно. Но программ размером в миллионы строк кода, которые разрабатывают одновременно сотни людей, требуют специальных методов. Иначе их разработка превратится в полный хаос. Непонимание этого обычно приводит к печальным последствиям.
Меня интересуют возможности ФЯ для написания больших программ, поэтому и возник такой вопрос. В частности, в больших программных системах очень важным становится гибкость, возможность изменения одного компонента независимого от других. ООП позволяет делать это путем разделения интерфейса (абстрактного предка) и реализаций в наследниках. В данном случае такой метод невозможен. Меня интересуют какие альтернативы предлагают ФЯ.
>> Возникает очевидное противоречие с ОО-подходом.
>ну и хуй с ним!
То есть, ФЯ не совместимо с ООП?
> например (f rgs где f:: RandomGeneratorState -> (Double->Double)->Double->Double->Double
> т.е. то же самое, что и в случае плюсов и даже лучше, т.к. нет уродского наследования
> монады будут использоваться внутри f для описания последовательности действий над объектом
Это опять возвращает нас к вопросу: если у меня есть некий MapleServerIO Double как я из него получу нормальный Double? Ведь вроде бы эти самые IO никак нельзя снять? Интересует возможность этого в чистых ФЯ, очевидно, что языки с императивными фичами легко позволяют это сделать.
>>> Возникает очевидное противоречие с ОО-подходом.
>> ну и хуй с ним!
> То есть, ФЯ не совместимо с ООП?
совместимо, но я не фанат этой религии
её "прелести" в том числе и наследование обсуждаются в соседнем треде
> Ведь вроде бы эти самые IO никак нельзя снять?
ещё раз:
unsafePerformIO :: IO a -> a
>> ну и хуй с ним!
> То есть, ФЯ не совместимо с ООП?
совместимо, но я не фанат этой религии
её "прелести" в том числе и наследование обсуждаются в соседнем треде
> Ведь вроде бы эти самые IO никак нельзя снять?
ещё раз:
unsafePerformIO :: IO a -> a
Для разработки больших программ придумали средства модульности.
Это кроме того, что на ФЯ программы получаются заметно короче.
---
...Я работаю антинаучным аферистом...
Это кроме того, что на ФЯ программы получаются заметно короче.
---
...Я работаю антинаучным аферистом...
> совместимо, но я не фанат этой религии
Как совместить конкретно в этом случае?
Подмена терминов: ООый - подход, а не религия.
> unsafePerformIO :: IO a -> a
Это низкоуровневый грязный императивный хак или это "официальная" функция, которую рекомендуют для использования в таких случаях (нужен одинаковый интерфейс для функций решающих общую задачу но по-разному)? Меня интересуют не конкретные названия в конкретном языке, а общая идеология ФП. Если доставать Int из IO Int не противоречит канонам ФП - тогда вопрос решен.
Как совместить конкретно в этом случае?
Подмена терминов: ООый - подход, а не религия.
> unsafePerformIO :: IO a -> a
Это низкоуровневый грязный императивный хак или это "официальная" функция, которую рекомендуют для использования в таких случаях (нужен одинаковый интерфейс для функций решающих общую задачу но по-разному)? Меня интересуют не конкретные названия в конкретном языке, а общая идеология ФП. Если доставать Int из IO Int не противоречит канонам ФП - тогда вопрос решен.
> Для разработки больших программ придумали средства модульности.
Звучит заманчиво.
Можешь привести пример как с помощью этих средств правильно сделать такую вещь:
Выделить интегрирование в отдельный модуль. Причем нужно чтобы было несколько взаимозаменяемых модулей и подключались бы разные в зависимости от настроек, доступности внешних программ итп. Тот кто вызывает модуль не должен знать какая реализация работает именно сейчас.
Звучит заманчиво.
Можешь привести пример как с помощью этих средств правильно сделать такую вещь:
Выделить интегрирование в отдельный модуль. Причем нужно чтобы было несколько взаимозаменяемых модулей и подключались бы разные в зависимости от настроек, доступности внешних программ итп. Тот кто вызывает модуль не должен знать какая реализация работает именно сейчас.
Я бы сказал, что при замене чистой функции на нечистую интерфейс как раз меняется.
Нечистые языки не замечают этой замены, что так же может привести к проблемам в большом проекте.
То есть, один разработчик думал, что функция без побочных эффектов, а второй незаметно этот эффект вставил.
Похожую проблему описал Fj в соседнем треде.
Что делать, я не знаю, пусть отвечает
Нечистые языки не замечают этой замены, что так же может привести к проблемам в большом проекте.
То есть, один разработчик думал, что функция без побочных эффектов, а второй незаметно этот эффект вставил.
Похожую проблему описал Fj в соседнем треде.
Что делать, я не знаю, пусть отвечает
Спасибо! Вот это уже более понятный ответ.
Интерфейс понимается в ФЯ шире чем в обычных языках. Надо это обдумать.
Интерфейс понимается в ФЯ шире чем в обычных языках. Надо это обдумать.
> Подмена терминов: ООый - подход, а не религия.
именно религия, так как в своей основе опирается на постулат об устройстве внешнего мира
постулат, надо заметить, хреновый, и внешний мир он описывает неадекватно,
но ООП-идолопоклонники в него истинно веруют
>> совместимо, но я не фанат этой религии
> Как совместить конкретно в этом случае?
я ж показал, как
ОО оказалось ни при делах, что очень даже ОО-совместимо, если не ставить задачу,
аналогичную забиванию гвоздей мобильным телефоном (использовать ООП любой ценой)
>> unsafePerformIO :: IO a -> a
> Это низкоуровневый грязный императивный хак или это "официальная" функция,
Что здесь императивного? Или "грязного"? Где здесь вообще "хак"?
> которую рекомендуют для использования в таких случаях (нужен одинаковый интерфейс
> для функций решающих общую задачу но по-разному)?
У таких функций одинаковый тип. Что ещё надо?
> Меня интересуют не конкретные названия в конкретном языке, а общая идеология ФП.
> Если доставать Int из IO Int не противоречит канонам ФП - тогда вопрос решен.
Статьи читал? State Reader monad видел? Так вот это оно.
именно религия, так как в своей основе опирается на постулат об устройстве внешнего мира
постулат, надо заметить, хреновый, и внешний мир он описывает неадекватно,
но ООП-идолопоклонники в него истинно веруют
>> совместимо, но я не фанат этой религии
> Как совместить конкретно в этом случае?
я ж показал, как
ОО оказалось ни при делах, что очень даже ОО-совместимо, если не ставить задачу,
аналогичную забиванию гвоздей мобильным телефоном (использовать ООП любой ценой)
>> unsafePerformIO :: IO a -> a
> Это низкоуровневый грязный императивный хак или это "официальная" функция,
Что здесь императивного? Или "грязного"? Где здесь вообще "хак"?
> которую рекомендуют для использования в таких случаях (нужен одинаковый интерфейс
> для функций решающих общую задачу но по-разному)?
У таких функций одинаковый тип. Что ещё надо?
> Меня интересуют не конкретные названия в конкретном языке, а общая идеология ФП.
> Если доставать Int из IO Int не противоречит канонам ФП - тогда вопрос решен.
Статьи читал? State Reader monad видел? Так вот это оно.
signature trapec = sig val integr: (real -> real)->(real*real)->real end;
structure trapec = struct fun integr _ = 0.0 end;
signature simps = sig val integr: (real -> real)->(real*real)->real end;
structure simps = struct fun integr _ = 1.0 end;
let val integr = if 1=0 then trapec.integr else simps.integr
in integr end;
---
...Я работаю антинаучным аферистом...
Код в целом очень понятный и вполне естественный.
Однако чем этот код отличается от такого:
Если нет, то чем тогда средства модульности отличаются от обычных ООП-средств?
Кстати, это код на ML? А есть ли такие же средства модульности на чистых ФЯ (например Haskell)?
Однако чем этот код отличается от такого:
typedef double (*fun_typedouble);Если отличия есть, в чем они?
class Integrator
{
public:
virtual void* integrate(fun_type f, double a, double b) = 0;
};
class Simpson : public Integrator { }
...
Intergator *integrator;
if (conifg.simpson) integrator = new Simpson; else integrator = new Trapec;
Если нет, то чем тогда средства модульности отличаются от обычных ООП-средств?
Кстати, это код на ML? А есть ли такие же средства модульности на чистых ФЯ (например Haskell)?
> именно религия, так как в своей основе опирается на постулат об устройстве внешнего мира
> постулат, надо заметить, хреновый, и внешний мир он описывает неадекватно,
> но ООП-идолопоклонники в него истинно веруют
где такую траву берешь?
> постулат, надо заметить, хреновый, и внешний мир он описывает неадекватно,
> но ООП-идолопоклонники в него истинно веруют
где такую траву берешь?
Его можно упростить дальше:
Зачем тебе понадобилось делать "new Simpson"?
Тебе одного не хватило?
Haskell = LazyML.
---
...Я работаю антинаучным аферистом...
Сравни количество употреблённых слов.
fun trapec ... = ...;
fun simps ... = ...;
let val integr = if ... then trapec else symps in ... end;
Зачем тебе понадобилось делать "new Simpson"?
Тебе одного не хватило?
Haskell = LazyML.
---
...Я работаю антинаучным аферистом...
Хе. И в этом треде идёт перепалка ООПистов и ФПистов.
Это было бы смешно, если б не было так печально.....
_________
Странная тема "pseudorandom на ФЯ".
Я-то думал псевдорандом - задача алгоритмическая и вобщем имеющая отношение скорее к математике... Причём здесь Ф и ОО?
Это было бы смешно, если б не было так печально.....
_________
Странная тема "pseudorandom на ФЯ".
Я-то думал псевдорандом - задача алгоритмическая и вобщем имеющая отношение скорее к математике... Причём здесь Ф и ОО?
Ф и ОО здесь не при чем. Просто тема всех захватила, а соответствующий тред разросся до неудобочитаемости.
Меня здесь интересовало изначально совсем другое - как концептуально правильно реализовать pseudorandom на ФЯ, по возможности чистой функцией.
Меня здесь интересовало изначально совсем другое - как концептуально правильно реализовать pseudorandom на ФЯ, по возможности чистой функцией.
> Просто тема всех захватила, а соответствующий тред разросся до неудобочитаемости.
Именно! Читатье его не просто неудобно, а вообще невозможно.
Было бы очень хорошо, если бы какие-нибудь модераторы/авторы постов/энтузиасты попытались собрать выводы из него и выделить в отдельный тред. Или хотя бы снести флудовые посты во флуд.
Именно! Читатье его не просто неудобно, а вообще невозможно.
Было бы очень хорошо, если бы какие-нибудь модераторы/авторы постов/энтузиасты попытались собрать выводы из него и выделить в отдельный тред. Или хотя бы снести флудовые посты во флуд.
Вот обсуждение именно этого вопроса в c.l.f
Большое спасибо за ссылку, прочитал с большим интересом весь тред.
Оставить комментарий
shlyumper
А вот не подскажет ли кто, каким образом можно грамотно реализовать псевдослучайный генератор на ФЯ, что-либо более-менее нетривиальное, типа Ran1 из Numerical Recipies (см. ).Интересует реализация, лучше на ML, которой было бы удобно пользоваться. Вполне представляю, как это записать в "императивном стиле", но от этого образуется неприятная тяжесть на душе - все же ФЯ и все такое.