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-мерному монте-карло, и рандом там нужен очень качественный и быстрый.
быстрее не будет, конечно
На 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
Оно?
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
У функциональных массивов интерфейс должен быть примерно такой:
type 'a farray
val get : 'a farray -> int -> 'a
val change : 'a farray -> int -> 'a -> ('a farray * 'a)
В книжке Окасаки приводятся реализации такого на деревьях, со сложностью
операций get и change порядка ln(длина).
А если нужны настоящие массивы, нужно писать императивно.
Обновления у любых типов данных деструктивные, на то они и обновления. Если в дереве заменить поддерево, то старое поддерево тоже теряется. Или я чего-то не понимаю? Рассматриваются не все обновления, а какие-то специфические?
> А если нужны настоящие массивы, нужно писать императивно
Как тогда выкручиваются чистые ФЯ?
Поэтому в чистых функциях обновлений не бывает.
> Если в дереве заменить поддерево, то старое поддерево тоже теряется.
Вместо этого создают новое дерево, разделяющее часть вершин (почти все) со старым.
> Как тогда выкручиваются чистые ФЯ?
Не знаю, я их не изучал.
Вместо этого создают новое дерево, разделяющее часть вершин (почти все) со старым.Каким образом это происходит? Заново ли создается ссылочная структура нового дерева? Или она тоже как-то разделяется?
функционализм в его исконном, от Джона Бекуса смысле.
См. SRFI 25.
---
...Я работаю антинаучным аферистом...
А, кажется, понял. То есть в случае дерева создать новое дерево с нужными изменением - быстрая операция (O(1) время) и поэтому так делают. А в случае массива создать новый массив и одним измененным элементом требует O(N) памяти и времени, и поэтому так не делают. Правильно?
То есть разница не в каком-то принципиальном отличии в структуре данных, а в том, сколько времени требуется на единичное недеструктивное обновление? Если бы время выполнения не играло роли то ФЯ легко бы реализовывали массивы?
а не поэлементно. ILP в действии.
---
...Я работаю антинаучным аферистом...
Процедуры работы с массивами? В ФЯ? А как же отсуствие side effects? Или массивы каждый раз конструируются заново(при добавлении/изменении элементов)?
в случае дерева создать новое дерево с нужными изменением - быстрая операция (O(1) время)Может быть я туплю, но как это возможно?
Ответы на два твоих последних поста оставляются в качестве домашнего упражнения.
---
"Narrowness of experience leads to narrowness of imagination."
Rob Pike
Но вот это IMHO как раз простая задача. В каждую клетку встраивается какой-нибудь reference counter, и потом делается copy-on-write. Если refcount=1, то меняем. Если >1 ,то создаем копию и ее меняем, у оргининала refcount уменьшается. Довольно традиционный метод не связанный с ФЯ.
По первому вопросу у меня есть единственное предложение - новое дерево создается с корнем в новой вершине. По второму - это полный бред. Классические массивы невозможны(с более менее нормальной эффективностью) в ФЯ.
> эффективностью) в ФЯ.
Про Джона Бекуса что-нибудь слышал?
---
"Narrowness of experience leads to narrowness of imagination."
Rob Pike
Ну вот, можешь же, если захочешь.
> Классические массивы невозможны(с более менее нормальной эффективностью) в ФЯ.
Точнее, некоторые алгоритмы на массивах не реализуются с нормальной эффективностью без
использования элементов императивного программирования.
Поправки принимаю. Суть претензии от этого не меняется. Понятное дело что если мне нужно последовательно обойти массив, это одно, а если мне нужен произвольный доступ на чтение/запись - это совсем другое.
Ну тут вроде никто не призывает полностью отказаться от императивного программирования, это и невозможно.
как для списков, набор примитивов.
---
...Я работаю антинаучным аферистом...
с журналированием, основанным на этом принципе.
Вся файловая система лежит в дереве, а модификации приводят к копированию вершин,
начиная с данной и вверх. Таким образом, получается второй корень, из которого вырастает
дерево, в основном совпадающее со старым.
В какой-то момент просто берём и атомарно меняем в суперблоке указатель на корень,
после чего устаревшие части дерева можно удалять.
Некто Daniel Phillips этим занимался, и называл это phase tree, но похоже забил.
> как для списков, набор примитивов.
Который не очень эффективно отображается на низкоуровневые операции,
поддерживаемые процессором?
---
...Я работаю антинаучным аферистом...
Я не знаю, про какие примитивы ты говоришь, но в SRFI-25 описаны обычные императивные массивы.
как это должно работать.
Возьмём для примера набор от Джона Бекуса, со свёртками,
массовыми отображениями и т. п.
Что именно сильно хуже ложится на процессор по сравнению с Фортраном?
---
...Я работаю антинаучным аферистом...
Какая из них ведёт прямо на эти мифические примитивы?
ну в общем да, я примерно к такому варианту и склонился сам в итоге. просто говорю же, как-то некомфортно от этого, но похоже с random по-другому не получится.

Вот некий гуру дисков (забыл фамилию, в соседнем разделе я как-то линк постил обещал такие диски.
То есть ёмкость можно повысить примерно в 1000 раз относительно нынешних, а скорость - только в 10 раз.
Забить полностью такой диск - грубо говоря, месяц непрерывной записи.
Поэтому файловая система (почти) без операций удаления придётся как нельзя кстати.
ведь уже написан код на C
преимущество ты сможешь получить там, где будут сложные преобразования,
которые на С написать трудно
если таких в задаче нет - правильно написал
если есть - ты сможешь сэкономить на времени проектирования и отладки
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 ;;
А с рандомом - это вообще говоря был больше академический чем практический интерес.
Никогда не использовал потоки, интересно

"Функциональное программирование," насколько помню.
Отголоски можно найти, разумеется на DMoz:
http://dmoz.org/Computers/Programming/Languages/Functional/
ссылка "FP".
Есть ещё страшные языки APL, J, K, R, S и т. п.
---
...Я работаю антинаучным аферистом....
Так что остаюсь при своём мнении.
и получить чистый интерфейс.
Этого состояния там всего 1088 бит, если не ошибаюсь, так что по сравнению
с этим ужасом - ничего страшного.
Да, теряется, если нет других ссылок.
>Как тогда выкручиваются чистые ФЯ?
В чистых ФЯ используются или монады (Хаслель) или специальный синтаксис в языке (Clean где ты прямо указываешь компилятору, что на массив есть только одна ссылка.
Кстати, меня сильно впечатлило, как в Хаскель происходит сопряжение IO монады с Real World. Я думал, это сделано на уровне компилятора, а оказывается там действительно все чисто функционально.
В обычных ФЯ массивы императивны (хотя есть и copy-on-write для извращенцев). В чистых ФЯ обеспечивается наличие только одной ссылки на массив, что позволяет их модифицировать без копирования.
Я как-то пытался сделать хитрый массив для переборных алгоритмов.
Типа чтоб интерфейс чистый, как я выше написал, но обновление и выборка за O(1).
Хитрость в том, что откат назад (то есть доступ по старой ссылке) дольше чем O(1
а именно O(число шагов отката). Таким образом, откат назад на 1 шаг, как нужно в переборе, тоже быстрый.
Идея такая, что есть один императивный массив, а от каждой ссылки к нему тянется цепочка обновлений,
то есть типа журнал.
Не доделал, заломало

Возможны даже в чистых ФЯ (У меня решето Эратосфена на haskell работало всего в пару-тройку раз медленнее чем на С, а у другого чувака на Clean работало почти также быстро). Но работать с ними там труднее.
В OCaml разве не такие массивы (со следом изменений каждого элемента)?
Там обычные массивы.
это сдвиг Бернулли, множитель 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."
---
...Я работаю антинаучным аферистом...
Лучше писать так
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
а то, как оно используется, описывается словами так:
ia um* im um/mod drop.
---
"Истина грядёт --- её ничто не остановит!"
На первый взгляд (я смотрю в 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.
> и отдаётся наружу не целиком, а только частями, таким образом гарантируется отсутствие
> внешних ссылок на состояние и его можно менять непосредственно,
> иначе пришлось бы отслеживать число ссылок и производить копирование по необходимости
Насколько я понимаю, у функций осуществляющих ввод/вывод, генерацию случайных чисел итп. возвращаемое значение меняется, вместо 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 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.
---
...Я работаю антинаучным аферистом...
А у тебя там всякие ref, !x Они сюда не не укладываются.
> буду за исключением, пожалуй, этого:
Размер программы имеет большое значение. Мелкие программы для себя можно писать как угодно. Но программ размером в миллионы строк кода, которые разрабатывают одновременно сотни людей, требуют специальных методов. Иначе их разработка превратится в полный хаос. Непонимание этого обычно приводит к печальным последствиям.
Меня интересуют возможности ФЯ для написания больших программ, поэтому и возник такой вопрос. В частности, в больших программных системах очень важным становится гибкость, возможность изменения одного компонента независимого от других. ООП позволяет делать это путем разделения интерфейса (абстрактного предка) и реализаций в наследниках. В данном случае такой метод невозможен. Меня интересуют какие альтернативы предлагают ФЯ.
>> Возникает очевидное противоречие с ОО-подходом.
>ну и хуй с ним!
То есть, ФЯ не совместимо с ООП?
> например (f rgs где f:: RandomGeneratorState -> (Double->Double)->Double->Double->Double
> т.е. то же самое, что и в случае плюсов и даже лучше, т.к. нет уродского наследования
> монады будут использоваться внутри f для описания последовательности действий над объектом
Это опять возвращает нас к вопросу: если у меня есть некий MapleServerIO Double как я из него получу нормальный Double? Ведь вроде бы эти самые IO никак нельзя снять? Интересует возможность этого в чистых ФЯ, очевидно, что языки с императивными фичами легко позволяют это сделать.
>> ну и хуй с ним!
> То есть, ФЯ не совместимо с ООП?
совместимо, но я не фанат этой религии
её "прелести" в том числе и наследование обсуждаются в соседнем треде
> Ведь вроде бы эти самые IO никак нельзя снять?
ещё раз:
unsafePerformIO :: IO a -> a
Это кроме того, что на ФЯ программы получаются заметно короче.
---
...Я работаю антинаучным аферистом...
Как совместить конкретно в этом случае?
Подмена терминов: ООый - подход, а не религия.
> unsafePerformIO :: IO a -> a
Это низкоуровневый грязный императивный хак или это "официальная" функция, которую рекомендуют для использования в таких случаях (нужен одинаковый интерфейс для функций решающих общую задачу но по-разному)? Меня интересуют не конкретные названия в конкретном языке, а общая идеология ФП. Если доставать Int из IO Int не противоречит канонам ФП - тогда вопрос решен.
Звучит заманчиво.
Можешь привести пример как с помощью этих средств правильно сделать такую вещь:
Выделить интегрирование в отдельный модуль. Причем нужно чтобы было несколько взаимозаменяемых модулей и подключались бы разные в зависимости от настроек, доступности внешних программ итп. Тот кто вызывает модуль не должен знать какая реализация работает именно сейчас.
Нечистые языки не замечают этой замены, что так же может привести к проблемам в большом проекте.
То есть, один разработчик думал, что функция без побочных эффектов, а второй незаметно этот эффект вставил.
Похожую проблему описал Fj в соседнем треде.
Что делать, я не знаю, пусть отвечает

Интерфейс понимается в ФЯ шире чем в обычных языках. Надо это обдумать.
именно религия, так как в своей основе опирается на постулат об устройстве внешнего мира
постулат, надо заметить, хреновый, и внешний мир он описывает неадекватно,
но ООП-идолопоклонники в него истинно веруют
>> совместимо, но я не фанат этой религии
> Как совместить конкретно в этом случае?
я ж показал, как
ОО оказалось ни при делах, что очень даже ОО-совместимо, если не ставить задачу,
аналогичную забиванию гвоздей мобильным телефоном (использовать ООП любой ценой)
>> 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;
---
...Я работаю антинаучным аферистом...
Однако чем этот код отличается от такого:
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)?
> постулат, надо заметить, хреновый, и внешний мир он описывает неадекватно,
> но ООП-идолопоклонники в него истинно веруют
где такую траву берешь?
Сравни количество употреблённых слов.
fun trapec ... = ...;
fun simps ... = ...;
let val integr = if ... then trapec else symps in ... end;
Зачем тебе понадобилось делать "new Simpson"?
Тебе одного не хватило?
Haskell = LazyML.
---
...Я работаю антинаучным аферистом...
Это было бы смешно, если б не было так печально.....
_________
Странная тема "pseudorandom на ФЯ".
Я-то думал псевдорандом - задача алгоритмическая и вобщем имеющая отношение скорее к математике... Причём здесь Ф и ОО?
Меня здесь интересовало изначально совсем другое - как концептуально правильно реализовать pseudorandom на ФЯ, по возможности чистой функцией.
Именно! Читатье его не просто неудобно, а вообще невозможно.
Было бы очень хорошо, если бы какие-нибудь модераторы/авторы постов/энтузиасты попытались собрать выводы из него и выделить в отдельный тред. Или хотя бы снести флудовые посты во флуд.
Вот обсуждение именно этого вопроса в c.l.f
Большое спасибо за ссылку, прочитал с большим интересом весь тред.
Оставить комментарий
shlyumper
А вот не подскажет ли кто, каким образом можно грамотно реализовать псевдослучайный генератор на ФЯ, что-либо более-менее нетривиальное, типа Ran1 из Numerical Recipies (см. ).Интересует реализация, лучше на ML, которой было бы удобно пользоваться. Вполне представляю, как это записать в "императивном стиле", но от этого образуется неприятная тяжесть на душе - все же ФЯ и все такое.