Запоминание эффективной функции

Я начал работать над проектом, определяющим клеточный автомат как локальную функцию перехода:

newtype Cellular g a = Cellular { delta :: (g -> a) -> a }

Всякий раз, когда g является Monoid, можно определить глобальный переход, сместив фокус перед применением локального перехода. Это дает нам следующую функцию step:

step :: Monoid g => Cellular g a -> (g -> a) -> (g -> a)
step cell init g = delta cell $ init . (g <>)

Теперь мы можем просто запустить автомат, используя iterate. И мы можем сэкономить много (и я действительно имею в виду много: это буквально экономит часы) повторных вычислений, memoизируя каждый из шагов:

run :: (Monoid g, Memoizable g) => Cellular g a -> (g -> a) -> [g -> a]
run cell = iterate (memo . step cell)

Моя проблема в том, что я обобщил Cellular до CelluarT, чтобы иметь возможность использовать побочные эффекты в локальных правилах (например, копирование случайного соседа):

newtype CellularT m g a = Cellular { delta :: (g -> m a) -> m a }

Однако я хочу, чтобы эффекты запускались один раз, чтобы, если вы спросите ячейку несколько раз, каково ее значение, все ответы были согласованы. memo подводит нас здесь, потому что сохраняет эффективные вычисления, а не их результат.

Я не ожидаю, что это будет достижимо без использования небезопасных функций. Я попытался попробовать это, используя unsafePerformIO, IORef и Map g a для хранения уже вычисленных значений:

memoM :: (Ord k, Monad m) => (k -> m v) -> (k -> m v)
memoM =
  let ref = unsafePerformIO (newIORef empty) in
  ref `seq` loopM ref

loopM :: (Monad m, Ord k) => IORef (Map k v) -> (k -> m v) -> (k -> m v)
loopM ref f k =
  let m = unsafePerformIO (readIORef ref) in
  case Map.lookup k m of
    Just v  -> return v
    Nothing -> do
      v <- f k
      let upd = unsafePerformIO (writeIORef ref $ insert k v m)
      upd `seq` return v

Но он ведет себя непредсказуемым образом: memoM putStrLn правильно запоминается, в то время как memoM (\ str -> getLine) продолжает извлекать строки, несмотря на то, что ему передается тот же аргумент.


memoization haskell unsafe-perform-io
person gallais    schedule 11.09.2015    source источник
comment
Какую библиотеку заметок вы используете? запоминать?   -  person Cirdec    schedule 11.09.2015
comment
Ваши типы данных эквивалентны Cont и ContT. type Cellular g a = Cont a g и type CellularT m g a = ContT a m g   -  person Cirdec    schedule 11.09.2015

Ответы (2)


arrow_upward
2
arrow_downward

Этого можно добиться безопасно, если вы дадите себе возможность выделить ссылку на карту.

import Control.Monad.IO.Class

memoM :: (Ord k, MonadIO m) => (k -> m v) -> m (k -> m v)
                 |                           |
                 |        opportunity to allocate the map
                 get to IO correctly

Я собираюсь использовать MVar вместо IORef, чтобы получить большую часть правильного параллелизма. Это для корректности, если он используется одновременно, а не для производительности. Для производительности мы могли бы быть более изощренными и использовать блокировки с двойной проверкой или параллельную карту с более тонкой детализацией блокировки.

import Control.Concurrent    
import Control.Monad.IO.Class    
import qualified Data.Map as Map

memoM :: (Ord k, Monad m, MonadIO m) => (k -> m v) -> m (k -> m v)
memoM once = do 
    mapVar <- liftIO $ newMVar Map.empty    
    return (\k -> inMVar mapVar (lookupInsertM once k))

-- like withMVar, but isn't exception safe   
inMVar :: (MonadIO m) => MVar a -> (a -> m (a, b)) -> m b
inMVar mvar step = do
    (a, b) <- liftIO (takeMVar mvar) >>= step
    liftIO $ putMVar mvar a
    return b

lookupInsertM :: (Ord k, Monad m) => (k -> m v) -> k -> Map.Map k v -> m (Map.Map k v, v)
lookupInsertM once k map = 
    case Map.lookup k map of
        Just v -> return (map, v)
        Nothing -> do
            v <- once k
            return (Map.insert k v map, v)

На самом деле мы не используем IO, мы просто передаем состояние. Любая монада должна быть в состоянии сделать это с примененным к ней преобразователем, так почему мы дурачимся в IO? Это потому, что мы хотим иметь возможность распределять эти карты так, чтобы memoM можно было использовать более чем для одной другой функции. Если нас когда-либо заботит только одна запоминаемая эффективная функция, мы можем вместо этого просто использовать преобразователь состояния.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import Control.Applicative
import Control.Monad.Trans.Class
import Control.Monad.Trans.State

newtype MemoT k v m a = MemoT {getMemoT :: StateT (k -> m v, Map.Map k v) m a}
    deriving (Functor, Applicative, Monad, MonadIO)

instance MonadTrans (MemoT k v) where
    lift = MemoT . lift

Этот преобразователь добавляет возможность поиска значения из запомненной эффективной функции.

lookupMemoT :: (Ord k, Monad m) => k -> MemoT k v m v
lookupMemoT k = MemoT . StateT $ \(once, map) -> do
                                                    (map', v) <- lookupInsertM once k map
                                                    return (v, (once, map'))

Чтобы запустить его и получить базовую монаду, нам нужно предоставить эффективную функцию, которую мы хотим запомнить.

runMemoT :: (Monad m) => MemoT k v m a -> (k -> m v) -> m a
runMemoT memo once = evalStateT (getMemoT memo) (once, Map.empty)

Наш MemoT использует Map для каждой функции. Некоторые функции могут быть запомнены другим способом. Пакет monad-memo имеет mtl для монад, обеспечивающих мемоизацию для конкретной функции, и более сложный механизм их построения, который не обязательно использует Maps.

person Cirdec    schedule 11.09.2015
comment
Вам может понравиться sequenceA :: (Ord e, Finite e, Applicative f) => (e -> f a) -> f (e -> a), хотя он не так лениво заполняет свою таблицу поиска, как ваша. - person Daniel Wagner; 11.09.2015
comment
@DanielWagner Да. Лучший ответ, который у меня не было времени написать сегодня утром, состоит в том, чтобы добавить Traversable экземпляров к (:->:) a для конечного a в memo-trie. - person Cirdec; 11.09.2015

arrow_upward
0
arrow_downward

Во-первых, перестаньте пытаться использовать unsafePerformIO. Такое название он получил не просто так.

То, что вы пытаетесь сделать, это не мемоизация, это фактически управление вызовами внутренней монады. Часть подсказки заключается в том, что Cellular не является монадой, поэтому CellularT не является преобразователем монады.

Что, я думаю, вам нужно сделать, так это иметь чистую функцию, которая вычисляет требуемый эффект для каждой ячейки, а затем выполняет итерацию по ячейкам, чтобы упорядочить эффекты. Это отделяет вашу клеточную механику автометонов (которая у вас уже есть и выглядит хорошо) от вашей эффективной механики. На данный момент вы, кажется, пытаетесь выполнить эффекты одновременно с их вычислением, что приводит к вашим проблемам.

Возможно, ваши эффекты должны быть разделены на фазу ввода и фазу вывода или что-то в этом роде. Или, возможно, ваши эффекты на самом деле больше похожи на конечный автомат, в котором каждая итерация каждой ячейки дает результат и ожидает новых входных данных. В этом случае см. мой вопрос здесь для некоторых идей о том, как это сделать.

person Paul Johnson    schedule 11.09.2015
comment
Cellular и CellularT — известные монады и преобразователи монад (ContT), если поменять местами аргументы a и g. То, что что-то не является монадным преобразователем, не означает, что оно не должно быть эффективным; есть много вещей с (* -> *) в своем роде, которые могут располагаться поверх монады, не будучи при этом монадами. - person Cirdec; 11.09.2015