如何使“时间机器”在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是基于这又是基于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 S中的不是你想要的。

现在，为什么？那么，你使用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)]