如何让"时间机器"在Haskell中运行？

Question

我听说在Haskell中我们可以MonadFix用来访问将来要评估的值.但我认为Monads只是语法糖,所以应该有类似的东西,可以在纯函数中实现.所以我尝试了以下方法:

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基于折叠而不是基于它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)]