LINUX.ORG.RU

[haskell] функция memo

 


0

0

Раньше в GHC была нестандартная функция memo :: (a -> b) -> (a -> b). В Hugs была (может быть, есть до сих пор) похожая функция memo1. Для моей задачи мне было бы достаточно последней. Как установить ее в GHC? Какой пакет взять? Гугл дает слишком старые ссылки. Может быть, эти функции уже того, т.е. deprecated?

P.S. Монада ST скорее всего не подойдет. Пробовал. Не получилось. В смысле, что мой код работает не так, как я того хотел. У меня там жесткая обратная связь. Такие ф-ции могут вызывать друг друга(свойство исходной задачи - динамика). Как результат, монада ST плодится в типах черезмерно. И вероятно все обламывается на том, что снаружи вызывается какая-нибудь функция (внутри >>= той же монады ST), которая и портит всю мемоизацию. Подозреваю, что с этой монадой скорее всего никак не получится...

★★★★★

Вообще-то мемоизация (если речь о ней) возможна во многих вариантах, причём в каждом из них она пишется довольно легко. А вот универсальной функции типа (a -> b) -> a -> b быть не может, это фантастика. Примерно как не может быть кнопки "сделать пиздато".

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

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

На самом деле, мне нужно две мемо-функции на двух разных уровнях. Но мне кажется, что на втором уровне можно использовать уже массив для мемоизации. Видел такой прием в книге Algorithms - A Functional Programming Approach.

Сейчас постараюсь описать задачу подробнее.

dave ★★★★★
() автор топика
Ответ на: комментарий от jtootf

Есть идея записывать уравнения системной динамики на хаскеле. Благодаря леновости можно красиво и легко задавать интегралы типа

	x = integ (x + 10.0) 100.0

Внешним параметром являются спеки, задающие метод и сетку интегрирования:

	data Conditions t = Conditions {cndStartTime :: t, cndStopTime :: t, cndDT :: t, cndMethod :: Method}

	data Method = Euler | RungeKutta2 | RungeKutta4

Само интегрирование представляет из себя итерационный процесс:

	data Process t a = Process {runProcess :: (Conditions t) -> Iteration -> a }

	type Iteration = Int

Это так выглядит в упрощенном виде. На самом деле есть еще зависимость от «фазы» интегрирования. Например, в методе Рунге-Кутта их четыре. В методе Эйлера - одна. Но это никак не влияет на саму задачу.

Есть три проблемы.

Во-первых, диапазон Iteration зависит от Conditions t. Здесь как бы можно создать бесконечный поток (stream) в виде списка, но это не решает второй проблемы.

Во-вторых, результат а, что сидит в монаде, также может зависеть от Conditions t. Например, starttime :: (Process t t) обертывает в себя значение cndStartTime.

Третья проблема состоит в том, что интегралы зависят от своего прошлого состояния. Они просто вызывают самим себя, параметр Conditions t остается тем же самым, а Iteration уменьшается на единицу. При нулевой итерации срабатывает граничное условие, и рекурсия завершается.

Так вот, значения интеграла по сетке Iteration -> a нужно мемоизировать. По-моему это можно сделать с помощью массива. Но проблема в том, что снаружи есть еще зависимость от параметра Conditions t. Поэтому от него тоже нужно мемоизироваться. Иначе предыдущая мемоизация окажется бесполезной. И получится та же экспоненциальная сложность как и в вычислении чисел Фибоначчи в-лоб, что и показывают мои тесты.

К счастью известно, что параметр Conditions t будет один и тот же в пределах запуска монады (Process t a) через функцию runProcess. Мне кажется, что если бы была ф-ция memo :: (a->b)->(a->b) хотя бы в виде memo1 (Hugs), то все бы получилось.

dave ★★★★★
() автор топика
Ответ на: комментарий от Miguel

> А вот универсальной функции типа (a -> b) -> a -> b быть не может, это фантастика.

В хаскелле, это фантастика, да.

anonymous
()
Ответ на: комментарий от dave

Дополнение. Вот, набросок реализации интеграла в-лоб. Эффективность без мемоизации чудовищно низкая.

integ :: (Num t) => Process t t -> Process t t -> Process t t
integ (Process f) (Process i) = Process y where
    y c 0 = i c 0
    y c n = y (n-1) 0 + (cndDT c) * f c (n-1)
dave ★★★★★
() автор топика
Ответ на: комментарий от dave
integ :: (Num t) => Process t t -> Process t t -> Process t t
integ (Process f) (Process i) = Process y where
    y c 0 = i c 0
    y c n = y c (n-1) + (cndDT c) * f c (n-1)
dave ★★★★★
() автор топика
Ответ на: комментарий от Waterlaz

А как ее определить?

Судя по всему, такая ф-ция раньше была. Даже без ограничения Ord а. Но похоже, что ее забанили.

Еще нашел описание Data.MemoCombinators. Увы, не походит.

Думаю, стоит еще раз попробовать с монадой ST. Хотя нет уверенности в разрешимости задачи таким способом.

dave ★★★★★
() автор топика
Ответ на: комментарий от Miguel

> А вот универсальной функции типа (a -> b) -> a -> b быть не может, это фантастика. Примерно как не может быть кнопки "сделать пиздато".

А почему?

www_linux_org_ru ★★★★★
()
Ответ на: комментарий от Miguel

Хотелось бы избежать использования unsafePerformIO. Пока у меня получилось

newtype Process s t a = 
    Process (ST s ((Conditions t) -> ST s (Iteration -> ST s a)))

runProcess :: (Ord t, Num t) => Process s t a -> Conditions t -> ST s [a]

но при этом где-то обламывается мемоизация... :(

dave ★★★★★
() автор топика
Ответ на: комментарий от dave

Установил с помощью простых тестов, что такая конструкция с [внешней] монадой ST работать не будет. Теперь пытаюсь осознать. Понимаю, что это связано с внутренним устройством ST, которое близко к устройству монады State. И там, и там внутри сидит функция.

Ну что же. Остается unsafePerformIO вместе с IORef.

dave ★★★★★
() автор топика
Ответ на: комментарий от psv1967

Все очень просто. Помогла статья, ссылку на которую дал Мигель. Правда там возникает утечка пространства, но я использовал Maybe (a, b) вместо таблицы, т.е. запоминаю только последнюю пару. Это накладывает некоторые ограничения на использование, но жить с этим можно. Что касается мемоизации итераций, то прием описан в книге "Algorithms: A functional programming approach": создаю массив, элементы которого ссылаются друг на друга - они сами мемоизируются. Итак, имеем двойную вложенную мемоизацию. Считает быстро.

dave ★★★★★
() автор топика
Ответ на: комментарий от mannaz

В некотором смысле. Там держится мемоизируемой функцией указатель на последний объект. Теряешь ссылку на эту функцию - и закешированный объект удаляется с помощью gc. Разумный компромисс.

dave ★★★★★
() автор топика
Ответ на: комментарий от mannaz

Но есть еще weak references. С ними память не течет. Но я их еще не освоил :)

dave ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.