Haskell: монадическая фиксированная точка на RWS зацикливается при переходе по аргументу

Question

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

type M = RWS () String [Int]

run a = evalRWS a () []

prepend s = tell (foldMap show s)

act = do
  tell "a"
  modify (1:)
  tell "b"

comp = mfix $ \s -> prepend s >> act >> get

Здесь я использую MonadFix изменить прошлое, записав в журнал перед actкогда-либо случалось. И работает безупречно, возвращая"1ab". Однако, если я используюM чтобы пройти по состоянию, он зависает:

prepend s = forM_ s (tell . show)

Такое поведение очень странно для меня, я не понимаю, почему эти вычисления расходятся. Оправдать еще труднее, потому чтоprependво втором варианте никак не меняет состояние. Почему эта программа не сходится? Могу ли я что-нибудь сделать, чтобы это исправить (inb4 "хе-хе исправил")?

Я знаю, что могу обойти это, используя State часть RWS, но мне почему-то хотелось этого избежать.

Answer 1

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

---

Когда вы запускаете это рекурсивное вычисление, оно занимает три шага (т.е. три монадических связывания): prepend, тогда act, а потом get, и в результате вы получите примерно следующее значение:

[foldMap show s, "a", "b"]

Где foldMap show s кусок еще не оценен - ​​т.е. он указывает на s, которое является конечным состоянием того же вычисления. Можно указать состояние, чтобы включить его вfoldMap show sвыражение до того, как состояние будет оценено, потому что Haskell ленив. Это лень на работе.

Однако если вы замените prepend с foldM_, у вас больше нет трех шагов (трех монадических привязок) в ваших вычислениях. Теперь у вас есть один шаг для каждого элемента результирующего списка состояний. Это означает, что для того, чтобы даже построить вычисление (то есть определить его шаги, также известные как привязки), вам необходимо изучить его собственное результирующее состояние.

Answer 2

forM_ s u определяется, только если s определено, но здесь s это заполнитель, пройденный мимо mfix, который будет определен только после того, как все вычисление prepend s >> act >> get прекращается.

Ваша первая версия работает, потому что ей не нужно проверять состояние, чтобы поместить ее в пару.

mfix :: (a -> m a) -> m a не принимает строгие функции f :: a -> m a (т. е. такие, что f undefined = undefined).

Если у вас есть список вещей, tell, то более ленивый способ - объединить их перед тем, как сказать им:

prepend s = tell (concatMap show s)