2016-12-19 72 views
4

我在玩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,並返回表達式的類型。

+1

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

+1

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

+1

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

回答

0

你想通過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 

所有未經測試。

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

+0

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