[haskell] функция memo

ты хоть бы задачу привёл, что ли

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

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

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

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

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

	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), то все бы получилось.

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

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

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

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)

Хм.. вообще возможна такая почти универсальная функция

memo :: Ord a => (a -> b) -> (a -> b)

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

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

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

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

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

А почему?

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1948

Хотелось бы избежать использования 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]

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

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

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

Всем спасибо. Задачу решил.

так не спортивно! :) немедленно расскажите!

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

> Правда там возникает утечка пространства

Это альтернатива утечкам памяти в Ъ-языках? :)

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

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

спасибо, очень интересно!