Wie erstellt man einen Pfeil, der "Verbindungen zählt"?

Question

Ich hatte vor kurzem die Idee, eine Monade zu bauen, die die Anzahl der Bindungen zählt, die eine Berechnung durchläuft. Ich kam mit der folgenden auf:

newtype K a = K { runK :: Int -> (a, Int) } 

instance Functor K where 
    fmap f k = K $ \s -> 
    let (iv, s') = runK k s 
    in (f iv, s') 

instance Applicative K where 
    pure x = K $ \s -> (x, s) 
    f <*> b = K $ \s -> 
    let (f', s') = runK f s 
     (ih, s'') = runK b s' 
    in (f' ih, s'') 

instance Monad K where 
    return x = K $ \s -> (x, s) 
    a >>= f = K $ \s -> 
    let (iv, s') = runK a s 
    in runK (f iv) (s' + 1) 

die später erkannte ich war nur der State Monade und nicht sehr interessant. Dann hatte ich die Idee zu versuchen, einen Pfeil zu bauen, der "Verbindungen" zählte. Hier bin ich ein bisschen ratlos.

newtype L a b = L { runL :: Int -> (a -> b, Int) } 

instance Category L where 
    id = arr Prelude.id 
    b . a = L $ \s -> 
    let (f1, s') = runL a s 
     (f2, s'') = runL b s' 
    in (f2 Prelude.. f1, s'' + 1) 

instance Arrow L where 
    arr f = L $ \s -> (f, s + 1) 
    first a = L $ \s -> 
    let (f1, s') = runL a s 
    in (\(x, y) -> (f1 x, y), s') 

kam ich mit dem, über den würde die Anzahl der Verbindungen zählen, aber die Anzahl der Verbindungen eine Berechnung geht nicht durch zählen. Vorschläge?

Answer 1

(Dies ist wirklich das gleiche wie Daniel Wagner Beobachtung, aber ich dachte, dass ich es freundlicher machen würde.)

Sie auf das, was die Bedeutung ist meditieren sollte Gesetze wie die Monade Gesetze zu haben. Dies ist ein Thema, das subtil und kompliziert, aber eine sehr einfache Daumenregel erhalten kann, die Sie anwenden können, ist dies:

• Wenn ein Typ oder Funktion verspricht, dass es ein Gesetz gehorcht, das sagt x = y, Kunden dieser Klasse sollte nicht x und y auseinander unterscheiden können.
• Das heißt, Sie sollten nicht Lage sein, eine Funktion f so zu schreiben, dass:
  • Das Gesetz sagt, dass x = y;
  • Aber f x /= f y

Jetzt kann dies keine absolute Regel sein. Nehmen wir zum Beispiel das Sortieren; merge sort und bubble sort sind beide stabile Sortieralgorithmen und somit "die gleiche Funktion" in dem Sinne, dass man sie nicht von den Ein- und Ausgaben unterscheiden kann. Aber wenn Sie einen "Seitenkanal" wie Timing verwenden, könnten Sie sie immer noch unterscheiden, aber wir schließen das normalerweise aus der Betrachtung aus, wenn wir fragen, ob irgendein Code einem bestimmten Gesetz gehorcht.

Jetzt, wenn wir dies auf Ihre K Art anwenden, dann ist das Problem, dass Sie ein Programm schreiben können, das zwei Ausdrücke unterscheidet, die die Monadengesetze sagen, sollte nicht unterscheidbar sein. Zum Beispiel in der documentation for the Monad class heißt es, dass:

, Darüber hinaus sind die Monad und Applicative Operationen wie folgt beziehen sollten:

pure = return 
(<*>) = ap 

Und wir können leicht die zweite von diesen mit einem Quick Check widerlegen Test wie folgt aus:

import Control.Monad (ap) 
import Test.QuickCheck 
import Test.QuickCheck.Function 

-- Snipped your code for `K` 

prop_ap :: Fun Int Int -> Int -> Bool 
prop_ap f x = runK applicative 0 == runK monadic 0 
    where applicative = pure (apply f) <*> pure x 
      monadic = return (apply f) `ap` return x 

Testing dies nicht sofort:

>>> quickCheck prop_ap 
*** Failed! Falsifiable (after 1 test and 2 shrinks): 
{_->0} 
0 

Der hier Grund dafür ist, dass Ihre Monad Instanz des +1 tut, aber Ihr Applicative man nicht etwas Derartiges tut.So können wir zwischen äquivalenten Berechnungen unterscheiden, aber einer von ihnen wurde mit <*> und der andere mit ap gebaut.

Answer 2

Wie von anderen beschrieben, können Sie keine "Verbindungen" wie Binds oder Pfeilbindungsoperationen zählen, weil sie dann nicht die Monad/Pfeil-Gesetze erfüllen.

Aber was Sie können tun ist, um einen Pfeil zu erstellen, wo Sie Größen Ihren Bausteinen explizit geben und dann die Größe einer solchen Schaltung berechnen können. Um ein Beispiel zu geben: {- # -Sprache Arrows # -}

import Control.Arrow 
import qualified Control.Category as C 

data A a b c = A { runA :: a b c, sizeA :: !Int } 

Hier definiert man einen Pfeil Transformator, der einen vorhandenen Pfeil Wraps und fügt seine Größe.

instance (C.Category a) => C.Category (A a) where 
    id = A C.id 0 
    (A a1 s1) . (A a2 s2) = A (a1 C.. a2) (s1 + s2) 

instance (Arrow a) => Arrow (A a) where 
    arr f = A (arr f) 0 
    first (A f s) = A (first f) s 

instance (ArrowChoice a) => ArrowChoice (A a) where 
    left (A f s) = A (left f) s 

-- instance (Arrow a) => ArrowTransformer A a where 
--  lift a = A a 0 

Die Standardgröße muss immer 0 sein, um die Gesetze zu erfüllen. Zum Beispiel id muss eine Größe von 0 haben, wie x . id === x dank Gesetz arr id === id wir haben, dass arr f auch Größe von 0 usw.

haben muß Aber wir können eine benutzerdefinierte Funktion definieren, die eine bestimmte Größe zu einem darunter liegenden Pfeil weist:

sized :: Int -> a b c -> A a b c 
sized = flip A 

Um ein Beispiel zu geben, lassen Sie uns einige Pfeile des Typs A (->) konstruieren. Das heißt, die zugrunde liegenden Pfeile sind nur Funktionen.

-- * Example (adapted from https://wiki.haskell.org/Arrow_tutorial) 

-- | Both 'f' and 'g' are constructed to have a size of 1. 
f, g :: A (->) Int Int 
f = sized 1 $ arr (`div` 2) 
g = sized 1 $ arr (\x -> x*3 + 1) 

h :: A (->) Int Int 
h = proc x -> do 
     fx <- f -< x 
     gx <- g -< x 
     returnA -< (fx + gx) 

Sie können h zum Beispiel als runA h 5 laufen. Aber Sie können auch seine Größe durch sizeA h messen, die wie erwartet 2 zurückgibt. Beachten Sie, dass Sie den Pfeil nicht ausführen müssen, um seine Größe zu erhalten. Sie können es sich als eine Schaltung vorstellen, und Sie müssen nicht wirklich eine Schaltung einschalten, um nur seine Größe zu sehen.

Beachten Sie, dass wir dies nicht für eine Monade tun können, also können wir keine Instanz ArrowChoice A haben. In einer Monade können wir den nächsten "Effekt" aus einem vorherigen Ergebnis berechnen, was bedeutet, dass wir niemals die Größe berechnen können, ohne die monadische Berechnung tatsächlich auszuführen.