Как я могу работать во вложенных монадах чисто?

Я пишу переводчика для небольшого языка. Этот язык поддерживает мутацию, поэтому ее оценщик отслеживает Store для всех переменных (где type Store = Map.Map Address Value, type Address = Int и data Value - специфический для языка ADT).

Также возможно, чтобы вычисления выходили из строя (например, делясь на ноль), поэтому результат должен быть Either String Value.

Тогда тип моего интерпретатора

eval :: Environment -> Expression -> State Store (Either String Value)

где type Environment = Map.Map Identifier Address отслеживает локальные привязки.

Например, интерпретация постоянного литерала не нужно прикасаться к хранилищу, и результат всегда выполняется успешно, поэтому

eval _ (LiteralExpression v) = return $ Right v

Но когда мы применяем двоичный оператор, нам нужно рассмотреть хранилище. Например, если пользователь оценивает (+ (x <- (+ x 1)) (x <- (+ x 1))) и x изначально 0, конечный результат должен быть 3, а x должен быть 2 в полученном хранилище. Это приводит к случаю

eval env (BinaryOperator op l r) = do
    lval <- eval env l
    rval <- eval env r
    return $ join $ liftM2 (applyBinop op) lval rval

Обратите внимание, что do -notation работает в монаде State Store. Кроме того, использование return мономорфно в State Store, а использование join и liftM2 мономорфно в монаде Either String. То есть, здесь мы используем

(return . join) :: Either String (Either String Value) -> State Store (Either String Value)

и return . join не является no-op.

(Как видно, applyBinop :: Identifier -> Value -> Value -> Either String Value.)

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

Какие полезные рекомендации следует знать о том, чтобы мой код читался и записывался?

EDIT: Вот более типичный пример, который лучше демонстрирует уродство. Вариант NewArrayC имеет параметры length :: Expression и element :: Expression (он создает массив заданной длины со всеми элементами, инициализированными константой). Простым примером является (newArray 3 "foo"), который дает ["foo", "foo", "foo"], но мы также можем написать (newArray (+ 1 2) (concat "fo" "oo")), потому что мы можем иметь произвольные выражения в NewArrayC. Но когда мы на самом деле называем

allocateMany :: Int -> Value -> State Store Address,

который принимает количество элементов для распределения и значение для каждого слота и возвращает начальный адрес, нам нужно распаковать эти значения. В приведенной ниже логике вы можете увидеть, что я дублирую кучу логики, которая должна быть встроена в монаду Either. Все case должны просто связываться.

eval env (NewArrayC len el) = do
    lenVal <- eval env len
    elVal <- eval env el
    case lenVal of
        Right (NumV lenNum) -> case elVal of
            Right val   -> do
                addr <- allocateMany lenNum val
                return $ Right $ ArrayV addr lenNum  -- result data type
            left        -> return left
        Right _             -> return $ Left "expected number in new-array length"
        left                -> return left

Ответ 1

Для этого нужны монадные трансформаторы. Существует трансформатор StateT, чтобы добавить состояние в стек, и трансформатор EitherT, чтобы добавить Either -образный сбой в стек; однако я предпочитаю ExceptT (который добавляет Except -образный сбой), поэтому я дам свое обсуждение в терминах этого. Поскольку вы хотите, чтобы бит состояния оставался самым внешним, вы должны использовать ExceptT e (State s) в качестве вашей монады.

type DSL = ExceptT String (State Store)

Обратите внимание, что операции с состоянием могут быть записаны get и put, и они являются полиморфными во всех экземплярах MonadState; так что, в частности, они будут хорошо работать в нашей монаде DSL. Аналогичным образом, канонический способ повышения ошибки - это throwError, который является полиморфным во всех экземплярах MonadError String; и, в частности, будет работать в нашей монаде DSL.

Итак, теперь мы будем писать

eval :: Environment -> Expression -> DSL Value
eval _ (Literal v) = return v
eval e (Binary op l r) = liftM2 (applyBinop op) (eval e l) (eval e r)

Вы также можете рассмотреть возможность предоставления eval более полиморфного типа; он может вернуть (MonadError String m, MonadState Store m) => m Value вместо DSL Value. Фактически, для allocateMany важно, чтобы вы дали ему полиморфный тип:

allocateMany :: MonadState Store m => Int -> Value -> m Address

Здесь есть два вопроса об этом: во-первых, потому что он является полиморфным во всех экземплярах MonadState Store m, вы можете быть уверены, что он имеет только побочные эффекты с сохранением состояния, как если бы у него был тип Int -> Value -> State Store Address, который вы предложили, Однако, также потому, что он является полиморфным, он может быть специализирован для возврата DSL Address, поэтому его можно использовать (например) eval. Ваш пример eval code станет следующим:

eval env (NewArrayC len el) = do
    lenVal <- eval env len
    elVal  <- eval env el
    case lenVal of
        NumV lenNum -> allocateMany lenNum elVal
        _           -> throwError "expected number in new-array length"

Я думаю, что это вполне читаемо, на самом деле; там нет ничего лишнего.