Haskell rec關鍵字如何工作？

在箭頭符號中，可以使用rec關鍵字來編寫遞歸定義。例如：Haskell rec關鍵字如何工作？

rec 
    name <- function -< input 
    input <- otherFunction -< name

這怎麼能評估？它似乎會進入一個無限循環或什麼東西。我知道它評估到循環箭頭組合器，但我不明白這是如何工作。

編輯：這個權力的例子真的很有幫助。儘管如此，你會如何寫這個符號？我假設你需要使用rec。

來源

2011-03-23 Jeff Burka

[案例]（http://www.haskell.org/haskellwiki/Keywords#rec）之前有人沒有聽說過「rec」。 – 2012-10-19 13:00:50

由於haskells懶惰，這一點神奇的作品。正如您可能知道的那樣，Haskell在需要時評估一個值，而不是在定義時評估。因此，如果您不需要直接輸入的值，或者稍後輸入值，則此功能可以正常工作。

rec使用loop函數ArrowLoop實現。這是其次的定義：

class Arrow a => ArrowLoop a where 
     loop :: a (b,d) (c,d) -> a b c 

instance ArrowLoop (->) where 
     loop f b = let (c,d) = f (b,d) in c

你可以看到：輸出只是反饋作爲輸入。它只會計算一次，因爲Haskell在需要時只會評估d。

下面是如何直接使用loop組合子的實際示例。此函數計算它的參數的所有權力：

powers = loop $ \(x,l) -> (l,x:map(*x)l)

（你也可以寫像這樣代替：powers x = fix $ (x :) . map (*x)）

它是如何工作的？那麼，權力的無限列表是在l的論點。評價是這樣的：

powers = loop $ \(x,l) -> (l,x:map(*x)l) ==> 
powers b = let (c,d) = (\(x,l) -> (l,x:map(*x)l)) (b,d) in c ==> 
powers b = let (c,d) = (d,b:map(*b)d) in d ==> -- Now we apply 2 as an argument 
powers 2 = let (c,d) = (d,2:map(*2)d) in d ==> 
     = let (c,(2:d)) = (d,2:map(*2)d) in c ==> 
     = let (c,(2:4:d)) = ((2:d),2:map(*2)(2:d)) in c ==> 
     = let (c,(2:4:8:d)) = ((2:4:d),2:map(*2)(2:4:d)) in ==> -- and so on

來源

2011-03-23 13:33:10 fuz

我明白，但是它從哪裏得到第一個輸出樣本？是否有基地案件定義的地方，因爲我沒有看到。如果我的示例中沒有提供輸入或名稱，那麼如何評估？還是必須提供其中的一個？ – 2011-03-23 13:58:53

訣竅是，Haskell不會評估未使用的參數。只是控制流程沒有必要與您想象的一樣。 – fuz 2011-03-23 15:20:42

'f（b，_）'在計算輸出'd'時只能使用輸入'b'。 'f'在構建'c'時可以同時使用'b'和'd'，只要它不強迫評估'd'使其掛起。你可以這樣想：當'c'被強制時，'d'從'b'計算，然後'c'從'b'和'd'計算。 – 2011-03-23 20:50:44

這裏是一個真正的十歲上下的例子：

loop f b = let (c,d) = f (b,d) in c 

f (b,d) = (drop (d-2) b, length b) 

main = print (loop f "Hello World")

該程序輸出「LD」。函數'loop f'需要一個輸入'b'並創建一個輸出'c'。 'f'正在做的是研究'b'來產生'長度b'，這個長度被返回到循環並綁定到'd'。

在'循環'中，'d =長度b'被輸入到'f'中，並在drop中用於計算。

這對於像構建一個不可變的雙向鏈表（這也可能是循環）這樣的技巧很有用。它也可用於遍歷'b'，既產生一些分析'd'（如長度或最大元素），又構建一個依賴於'd'的新結構'c'。懶惰避免了必須遍歷'b'兩次。

來源

2011-03-23 20:46:12

Haskell rec關鍵字如何工作？

回答

相關問題