list - 如何使 "time machine"在 Haskell 中工作？

Question

我听说在 Haskell 中我们可以使用 MonadFix 来访问一个值，该值将在未来计算。但我认为 Monad 只是语法糖，所以应该有类似的东西可以用纯函数实现。所以我尝试了以下方法:

timemachine :: [a] -> (a -> Int -> b -> b) -> b -> b
timemachine al f b = result where
    ~(total, result) = foldr app (0,b) al
    app a (i,b1) = (i+1, f a (total - i) b1)

main :: IO ()
main = print $ timemachine "ddfdfeef" (\x i y -> (x,i):y) []

但输出不是预期的:

[('d',1),('d',2),('f',3),('d',4),('f',5),('e',6),('e',7),('f',8)]

理想的结果应该是

[('d',8),('d',7),('f',6),('d',5),('f',4),('e',3),('e',2),('f',1)]

我是不是做错了什么？

Answer 1

跳过有关 MonadFix 的部分，您似乎想使用一个至少部分需要自己构造的值(total 是基于折叠的，而折叠又反过来基于总计)。

你实际上已经在这样做了，只是你的期望与你的弃牌不一致!要查看问题，您可以将 timemachine 更改为

timemachine al f b = result where
   ~(total, result) = foldr app (0,b) al
   app a (i,b1) = (i+1, f a i b1)

产生

[('d',7),('d',6),('f',5),('d',4),('f',3),('e',2),('e',1),('f',0)]

所以 total-i 是有效的，只是你累积的 i 不是你想要的。

现在，为什么？好吧，您使用的是 foldr，结果如下:

app 'd' (app 'd' (app 'f' ... (app 'f' (0,b)))))))))

所以 app 正在做的计数是从列表的右边开始的。如果我们改为将它更改为 foldl 从另一侧处理列表，并更改其余部分代码以与其对齐:

timemachine :: [a] -> (a -> Int -> b -> b) -> b -> b
timemachine al f b = result where
  ~(total, result) = foldl app (0,b) al
  app (i,b1) a = (i+1, f a (total-i) b1)

main :: IO ()
main = print $ timemachine "ddfdfeef" (\x i y -> y++[(x,i)]) []

你得到你想要的:

[('d',8),('d',7),('f',6),('d',5),('f',4),('e',3),('e',2),('f',1)]