如何使「時間機器」在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)]