mapAccumR類似於Fix的遞歸方案？

我在玩recursion-schemes的功能，並努力弄清楚它是否提供了一些推廣的東西mapAccumR。一些強大到足以實現如：mapAccumR類似於Fix的遞歸方案？

f :: [Int] -> (Int,[Int]) 
f [] = (0,[]) 
f (x:xs) = let (sz,xs') = f xs in (sz+x, x*sz : xs')

...在一次通過的Fix -ed結構，如：

data L a as = Empty | C a as 

input :: Fix (L Int) 
input = Fix (C 1 (Fix (C 2 (Fix Empty))))

zygo似乎接近我想要的東西，但我需要訪問最後的b（上面例子中的最後一筆）。

我的實際使用案例是在註釋時類型檢查AST，並返回表達式的類型。

來源

2016-12-19 jberryman

你期待什麼類型的簽名？ – dfeuer

另外，你應該看看'para'。 – dfeuer

但回到我的第一個問題，'mapAccumR'是'Traversable'函數的一個已知概念;它對於任意類型的固定點應該表示什麼意義還不太清楚。 – dfeuer

你想通過Fix f向上下行調整值，同時跟蹤一個狀態爲mapAccumR嗎？這是cataM爲上行順序，與State monad狀態以跟蹤。在您的例子：

f :: Fix (L Int) -> (Fix (L Int), Int) 
f = (`runState` 0) $ cataM $ ((.) . fmap) Fix $ \case 
    Empty -> pure Empty 
    C x xs -> do 
    sz <- get 
    put $ sz+x 
    return $ C (x*sz) xs

使用lens：

makeClassyPrisms ''L 

f = (`runState` 0) . transformMOf . _Fix . _C . _1 $ \x -> do 
    sz <- id <<+= x 
    return $ x*sz

所有未經測試。

還是你想讓州成爲每個分支的本地？

來源

2016-12-28 23:34:11 Gurkenglas

謝謝，我的實際例子是一個AST，我在一次通過類型檢查和註釋樹。因此，在每個級別，我們都需要訪問子類型併爲父類返回一個類型。這裏有幾點，但我很欣賞答案 – jberryman

mapAccumR類似於Fix的遞歸方案？

回答

相關問題