Как Вы делаете универсальную функцию memoize в Haskell?
NullPointerException s - исключения, возникающие при попытке использовать ссылку, которая указывает на отсутствие местоположения в памяти (null), как если бы она ссылалась на объект. Вызов метода по нулевой ссылке или попытка получить доступ к полю нулевой ссылки вызовет функцию NullPointerException. Они наиболее распространены, но другие способы перечислены на странице NullPointerException javadoc.
Вероятно, самый быстрый пример кода, который я мог бы придумать для иллюстрации NullPointerException, be:
public class Example {
public static void main(String[] args) {
Object obj = null;
obj.hashCode();
}
}
В первой строке внутри main я явно устанавливаю ссылку Object obj равной null. Это означает, что у меня есть ссылка, но она не указывает на какой-либо объект. После этого я пытаюсь обработать ссылку так, как если бы она указывала на объект, вызывая метод на нем. Это приводит к NullPointerException, потому что нет кода для выполнения в местоположении, на которое указывает ссылка.
(Это техничность, но я думаю, что она упоминает: ссылка, которая указывает на null, равна 't то же, что и указатель C, указывающий на недопустимую ячейку памяти. Нулевой указатель буквально не указывает на в любом месте , который отличается от указаний на местоположение, которое оказывается недопустимым.)
4 ответа
Это в основном следует http://www.haskell.org/haskellwiki/Memoization .
Вы хотите функцию типа (-> b). Если это не называет себя, то можно просто записать простую обертку, это кэширует возвращаемые значения. Лучший способ сохранить это отображение зависит от того, что могут использовать свойства Вас. Упорядочивание является в значительной степени минимумом. С целыми числами можно создать бесконечный ленивый список или дерево, содержащее значения.
type Cacher a b = (a -> b) -> a -> b
positive_list_cacher :: Cacher Int b
positive_list_cacher f n = (map f [0..]) !! n
или
integer_list_cacher :: Cacher Int b
integer_list_cacher f n = (map f (interleave [0..] [-1, -2, ..]) !!
index n where
index n | n < 0 = 2*abs(n) - 1
index n | n >= 0 = 2 * n
Так, предположите, что это рекурсивно. Тогда Вам нужен он для вызова не, но мемоизованной версии, таким образом, Вы передаете это во вместо этого:
f_with_memo :: (a -> b) -> a -> b
f_with_memo memoed base = base_answer
f_with_memo memoed arg = calc (memoed (simpler arg))
мемоизованная версия, конечно, что мы пытаемся определить.
, Но мы можем запустить путем создания функции, которая кэширует ее исходные данные:
Мы могли создать один уровень путем передачи в функции, которая создает структуру, это кэширует значения. Кроме мы должны создать версию f, который уже имеет , кэшируемая функция передала в.
Благодаря лени, это не проблема:
memoize cacher f = cached where
cached = cacher (f cached)
тогда все, в чем мы нуждаемся, должно использовать его:
exposed_f = memoize cacher_for_f f
статья дает подсказки относительно того, как использовать выбор класса типа на входе к функции, чтобы сделать вышеупомянутое, вместо того, чтобы выбрать явную функцию кэширования. Это может быть действительно хорошо - вместо того, чтобы явно создать кэш для каждой комбинации входных типов, мы можем неявно объединить кэши для типов a и b в кэш для функции, берущей a и b.
Один заключительный протест: использование этой ленивой техники означает, что кэш никогда не уменьшается, это только растет. Если Вы вместо этого используете монаду IO, можно управлять этим, но выполнение ее мудро зависит от шаблонов использования.
Данные-memocombinators пакета по hackage обеспечивают много допускающих повторное использование memoization стандартных программ. Основная идея:
type Memo a = forall r. (a -> r) -> (a -> r)
Т.е. это может memoize любая функция от a. Модуль тогда обеспечивает некоторые примитивы (как unit :: Memo () и integral :: Memo Int), и combinators для создания более сложных таблиц записки (как pair :: Memo a -> Memo b -> Memo (a,b) и list :: Memo a -> Memo [a]).
Делая прямой перевод с более императивных языков, я придумал это.
memoize :: Ord a => (a -> IO b) -> IO (a -> IO b)
memoize f =
do r <- newIORef Map.empty
return $ \x -> do m <- readIORef r
case Map.lookup x m of
Just y -> return y
Nothing -> do y <- f x
writeIORef r (Map.insert x y m)
return y
, Но это так или иначе неудовлетворительно. Кроме того, Данные. Карта вынуждает параметр быть экземпляром Порядок .
Если Ваши аргументы будут натуральными числами, можно сделать просто:
memo f = let values = map f [0..]
in \n -> values !! n
Однако, который действительно не помогает Вам с переполнением стека, и оно не работает с рекурсивными вызовами. Вы видите некоторые более необычные решения в http://www.haskell.org/haskellwiki/Memoization .