26

アロー do 記法では、rec キーワードを使用して再帰的な定義を記述できます。たとえば、次のようになります。

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

これはどのように評価できますか？無限ループか何かに陥りそうです。ループ矢印コンビネータに評価されることは知っていますが、それがどのように機能するかはわかりません。

編集：その力の例は本当に役に立ちます。しかし、それを do 表記でどのように記述しますか? recを使用する必要があると思います。

4

2 に答える 2

27

このちょっとした魔法は、haskells の怠惰のために機能します。ご存知かもしれませんが、Haskell は値を定義したときではなく、必要なときに評価します。したがって、これは、値を直接入力する必要がない場合、または後で入力する必要がない場合に機能します。

recloopの関数を使用して実装され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-23T13:33:10.113 に答える
14

これは実際の例です：

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」を出力します。関数「ループ f」は、1 つの入力「b」を取り、1 つの出力「c」を作成します。「f」が行っているのは、「b」を調べて「長さ b」を生成することです。これは、ループに戻されて「d」にバインドされます。

'loop' では、この 'd=length b' が 'f' に入力され、drop の計算に使用されます。

これは、不変の二重連結リスト (循環することもある) を作成するようなトリックに役立ちます。また、'b' を 1 回トラバースして、分析的な 'd' (長さや最大要素など) を生成し、'd' に依存する新しい構造 'c' を構築する場合にも役立ちます。怠惰により、「b」を 2 回トラバースする必要がなくなります。

于 2011-03-23T20:46:12.033 に答える