Frage Fix gegen ArrowLoop


Beschreibung von loop von Control.Arrow:

Der Schleifenoperator drückt Berechnungen aus, bei denen ein Ausgangswert als Eingabe zurückgeführt wird, obwohl die Berechnung nur einmal erfolgt. Es liegt dem Rec-Wert-Rekursionskonstrukt in Pfeilnotation zugrunde.

Sein Quellcode und seine Instantiierung für (->):

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

Das erinnert mich sofort an fix, der Fixpunktkombinator:

fix :: (a -> a) -> a
fix f = let x = f x in x

Also meine Frage ist:

  1. Ist es möglich, das zu implementieren? loop über fix?
  2. Wie unterscheiden sich ihre Funktionalitäten?

7
2017-08-09 03:27


Ursprung


Antworten:


  1. Aber natürlich. Jede rekursive Definition kann mit geschrieben werden fix:

    loop f b = let (c, d) = f (b, d) in c
    loop f b = fst $ let (c, d) = f (b, d) in (c, d)
    loop f b = fst $ let x = f (b, d) in x
    loop f b = fst $ let x = f' x in x
      where f' (_, d) = f (b, d)
    loop f b = fst $ fix $ f . (b,) . snd
    

    Und es funktioniert umgekehrt:

    fix f = loop (join (,) . f . snd) ()
    
  2. Das obige sollte Sie davon überzeugen loop und fix sind äquivalent mächtig, wenn man darüber spricht (->). Warum also, wenn Pfeile dazu gedacht sind, Funktionen zu verallgemeinern? ArrowLoop nicht so definiert?

    class Arrow a => ArrowLoop a where
      fix :: a b b -> b
    

    Pfeile verallgemeinern auch den Begriff "Prozess": wann Arrow a, a b c ist ein Weg, um ein zu berechnen c von einem b. Ob ArrowLoop wurde definiert, um direkt zu verallgemeinern fixdann wäre es stark verkrüppelt. fix müsste den Prozess ohne Kontext "ausführen" und direkt einen Wert vom Typ erzeugen b, was den "Prozess" bedeutet a b b kann nicht z.B. ausführen IO. Oder betrachte den Pfeil

    newtype LT i o = LT { runLT :: [i] -> [o] }
    

    Du würdest es mögen wenn fix würde produzieren a [b] von einem LT b baber das tut es nicht.

    loop ist ein Weg um diese Einschränkungen. Es nimmt einen Prozess als Argument und erzeugt einen Prozess als Ergebnis. In gewissem Sinne kann der gesamte mit dem ersten Prozess verbundene Kontext in der zweiten überlebt werden, was nicht möglich wäre, wenn loop waren mehr wie fix.

    Beachten Sie, dass ich ein Analog von implementieren kann fix zum ArrowLoops:

    -- resulting process ignores its input
    fix' :: ArrowLoop a -- taking an impl of loop as argument
         => a b b -> a u b
    fix' f = loop ((id &&& id) . f . arr snd)
    -- take off the outer application to () (application means (->), after all)
    -- and arrowify: join (,) = id &&& id; snd = arr snd; (Prelude..) = (Control.Category..)
    -- but the RHSs are more general
    

    Aber ich glaube nicht

    loop' :: Arrow a => (forall x u. a x x -> a u x) -- taking an impl of fix' as argument
          -> a (b, d) (c, d) -> a b c
    

    ist implementierbar, also können wir nicht basieren ArrowLoop auf fix' entweder.


8
2017-08-09 05:04