Obserwowalna rekursja (lub wiązanie) w strzałkach

Question

Próbuję znaleźć sposób na przetłumaczenie normalnej notacji rekurencyjnej, takiej jak jako | fib | funkcja poniżej do strzałki, zachowując jak najwięcej struktury zapisu rekursywnego. Ponadto chciałbym jak sprawdzić strzałkę. Do tego utworzone typ danych zawierającą dla każdego konstruktora Strzałka {..} klasy:

Fib:

fib 0 = 0 
fib 1 = 1 
fib n = fib (n-2) + fib (n-1) 

My R typu danych, przypadki dla tego typu danych składa się z mapowania do odpowiedniego konstruktora :

data R x y where 
    -- Category 
    Id  :: R a a 
    Comp  :: R b c -> R a b   -> R a c 
    -- Arrow 
    Arr  :: (a -> b) -> R a b 
    Split :: R b c -> R b' c'  -> R (b,b') (c,c') 
    Cache :: (a -> a -> Bool) -> R a a 
    -- ArrowChoice 
    Choice :: R b c -> R b' c' -> R (Either b b') (Either c c') 
    -- ArrowLoop 
    Loop  :: R (b, d) (c, d) -> R b c 
    -- ArrowApply 
    Apply :: R (R b c, b) c 

Tłumaczenie | fib | funkcja z powyższego skutkuje najpierw następującą definicją: . Nie jest to jednak dozwolone ze względu na proklamację RHS deklaracji dla | fibz |. Wiem, że gramatyka zapisywania strzałek zapobiega temu, ale co to jest podstawowy powód?

fib' :: (ArrowChoice r, ArrowLoop r) => r Int Int 
fib' = proc x -> do 
    rec fibz <- proc n -> case n of 
          0 -> returnA -< 0 
          1 -> returnA -< 1 
          n' -> do l <- fibz -< (n'-2) 
            r <- fibz -< (n'-1) 
            returnA -< (l+r) 
    fibz -<< x 

Przepisanie powyższej funkcji w celu użycia kompilacji let. Jednak tutaj pojawia się mój drugi problem: . Chcę móc sprawdzić rekurencję, w której się znajduje. Jednak w tym przypadku | fibz | to nieskończone drzewo . Chciałbym uchwycić rekursję do fibz, I nadzieję, że rec pomoże mi w połączeniu z pętlą | ale może się mylę?

fib'' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int 
fib'' = proc x -> do 
    let fibz = proc n -> case n of 
          0 -> returnA -< 0 
          1 -> returnA -< 1 
          n' -> do l <- fibz -< (n'-2) 
            r <- fibz -< (n'-1) 
            returnA -< (l+r) 
    fibz -<< x 

Zasadniczo, czy można zaobserwować ten rodzaj rekurencji? (Być może nawet w granicach Notacji Strzał) mógłbym dodać innego konstruktora takiego jak fix. Może powinienem być w stanie obserwować wiązanie zmiennych, aby odnoszenie się do nich stało się możliwe. To jednak wykracza poza zakres Arrows.

Jakieś przemyślenia na ten temat?

Aktualizacja 1: Wymyślam ten formularz poza spisem strzałki. To ukrywa rekursję wewnątrz app i dlatego kończę z skończoną reprezentacją Strzałki. Nadal jednak chcę mieć możliwość np. zamień wywołanie na fib wewnątrz app na zoptymalizowaną wersję fib.

fib :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int 
fib 
    = (arr 
     (\ n -> 
      case n of 
       0 -> Left() 
       1 -> Right (Left()) 
       n' -> Right (Right n')) 
     >>> 
     (arr (\() -> 0) ||| 
      (arr (\() -> 1) ||| 
      (arr (\ n' -> (n', n')) >>> 
       (first (arr (\ n' -> app (fib, n' - 2))) >>> 
        arr (\ (l, n') -> (n', l))) 
        >>> 
        (first (arr (\ n' -> app (fib, n' - 1))) >>> 
        arr (\ (r, l) -> (l + r)))))))         

Ten kod odpowiada z następujących w notacji strzałka:

fib :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int 
fib = proc n -> 
    case n of 
    0 -> returnA -< 0 
    1 -> returnA -< 1 
    n' -> 
      do l <- fib -<< (n'-2) 
       r <- fib -<< (n'-1) 
       returnA -< (l+r) 

Answer 1

Możesz napisać fib pod względem pętli na przykład tak:

fib'' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int 
fib'' = loop $ proc (i, r) -> do 
    i' <- r -<< i 
    returnA -< (i', proc j -> case j of 
     0 -> returnA -< 0 
     1 -> returnA -< 1 
     _ -> do 
      a <- r -< j-2 
      b <- r -< j-1 
      returnA -< a + b) 

Ale to jest naprawdę tylko wprowadzenie sztuczna pętla do problemu, który jej nie potrzebuje, i tak naprawdę nie kupuje cię zbytnio pod względem obserwowalności. Możesz powiedzieć, że istnieje jakaś pętla, ale myślę, że nie da się dokładnie określić, gdzie odbywa się rekursja.

W reifikowanej reprezentacji wszelkie połączenia z innymi strzałkami będą w zasadzie "zakreślone", w tym także połączenia z tą samą strzałką. Na początku nie można wykryć tych witryn wywoływania, nie wspominając już o tym, która z nich jest wywoływana. Kolejny problem z reifikacją strzałek polega na tym, że wiele interesujących informacji o tym, w jaki sposób przekazywane są dane wejściowe, gubi się w dziurce odwiertu Arr.

Z pewnością nie jestem ekspertem od strzały i mam nadzieję, że ktoś mi wykaże błąd, ale jestem skłonny sądzić, że to, co próbujesz osiągnąć, jest niemożliwe do wykonania niezawodnie lub co najmniej wysoce niepraktyczne. Jednym z zasobów, które mogę o tym pomyśleć, może być pakiet Type-Safe Observable Sharing in Haskell i .

Answer 2

Możesz w pełni powtórzyć kłamstwo z kategorią, w zakresie, w jakim możesz zdefiniować funkcje, aby zapisać swój kod na dysku i załadować go z powrotem. Jest to jednak trochę brzydkie.

{-# LANGUAGE GADTs, RankNTypes #-} 

module Main where 

import Control.Category 

data RRef s1 s2 = RRef Int 

data R s1 s2 where 
    Id :: forall s. R s s 
    Compose :: forall s1 s2 s3. R s2 s3 -> R s1 s2 -> R s1 s3 
    Lit :: forall s a. a -> R s (a,s) 
    Dup :: forall s a. R (a,s) (a,(a,s)) 
    Drop :: forall s b. R (b,s) s 
    Add :: forall s a. Num a => R (a,(a,s)) (a,s) 
    Decrement :: forall s. R (Int,s) (Int,s) 
    Deref :: forall s1 s2. RRef s1 s2 -> R s1 s2 
    Rec :: forall s1 s2. (RRef s1 s2 -> R s1 s2) -> R s1 s2 
    IsZero :: forall s. R (Int,s) (Bool,s) 
    If :: forall s1 s2. R s1 s2 -> R s1 s2 -> R (Bool,s1) s2 
    Swap :: forall s a b. R (a,(b,s)) (b,(a,s)) 
    Over :: forall s a b. R (a,(b,s)) (a,(b,(a,s))) 
    Rot :: forall s a b c. R (a,(b,(c,s))) (b,(c,(a,s))) 

instance Category R where 
    id = Id 
    (.) = Compose 

fib :: R (Int,()) (Int,()) 
fib = 
    Lit 0 >>> 
    Lit 1 >>> 
    Rot >>> 
    Rot >>> 
    Rec (\ref -> 
    Dup >>> IsZero >>> (
     If 
     (Drop >>> Swap >>> Drop) 
     (Decrement >>> Rot >>> Rot >>> Over >>> Add >>> Rot >>> Rot >>> (Deref ref)) 
    ) 
) 

R tutaj jest indeksowana monoid, który okazuje się być tak samo jak Category. Dwa parametry typu: R reprezentują sygnaturę stosu przed operacją i po niej. Stos jako stos programu, podobnie jak w kodzie zespołu. Krotki w typach stosów tworzą niejednorodną listę do wpisania każdego z elementów na stosie. Wszystkie operacje (z wyjątkiem If) przyjmują parametry zerowe i po prostu manipulują stosem. If pobiera dwa bloki kodu i zwraca kod, który nie przyjmuje parametrów i tylko manipuluje stosem.

Rec służy do rekursji. Interpreter znajdzie unikalną nazwę (jako liczbę całkowitą) dla funkcji rekursywnej, wtedy funkcja rekursywna odnosiłaby się do tej nazwy z Deref, aby powrócić do siebie tworząc rekursję.

Tego rodzaju rzeczy można uważać za konkatenatywny język programowania (jak EDSL), taki jak Forth, z wyjątkiem tego, że ma on typ bezpieczeństwa dla wartości na stosie.