Typ rekurencyjny



Informacje, które udało nam się zgromadzić na temat Typ rekurencyjny, zostały starannie sprawdzone i uporządkowane, aby były jak najbardziej przydatne. Prawdopodobnie trafiłeś tutaj, aby dowiedzieć się więcej na temat Typ rekurencyjny. W Internecie łatwo zgubić się w gąszczu stron, które mówią o Typ rekurencyjny, a jednocześnie nie podają tego, co chcemy wiedzieć o Typ rekurencyjny. Mamy nadzieję, że dasz nam znać w komentarzach, czy podoba Ci się to, co przeczytałeś o Typ rekurencyjny poniżej. Jeśli informacje o Typ rekurencyjny, które podajemy, nie są tym, czego szukałeś, daj nam znać, abyśmy mogli codziennie ulepszać tę stronę.

.

W programowaniu komputerowym i typu teorii , o rodzaj rekurencyjny to typ danych , którego definicja wzywa samego typu, rekurencyjnie . Pozwala to midzy innymi na tworzenie struktur danych zawierajcych podstruktury tego samego typu. To pojcie naturalnie stosuje si do badania list i drzew .

Przykady

Typy algebraiczne

Typy algebraiczne s zdecydowanie najpowszechniejsz form typów rekurencyjnych. Klasycznym przykadem jest typ listy. W skadni Haskell (ze zmienn typu, aktóra sprawia, e ta definicja jest polimorficzna ):

data List a = Nil | Cons a (List a)

Innymi sowy, lista elementów typu ajest albo pust list, albo komórk zawierajc dane typu a(nagówek listy) i inn list (koniec listy).

Inny przykad, rodzaj liczb naturalnych (patrz arytmetyka Peano ) mona zdefiniowa przez:

  data Nat = Zero | Succ Nat

to znaczy, liczba naturalna to zero lub nastpca liczby naturalnej.

Rekurencyjne typy funkcji

Moemy potrzebowa funkcji, która przyjmuje siebie jako argument. Na przykad, jeli chcesz napisa sumator staych punktów Y , który pozwala zdefiniowa funkcje rekurencyjne:

-- ne compile pas!
fix :: ((a -> b) -> a -> b) -> a -> b
fix f = let g x a = f (x x) a in g g

tak wic, chocia fixsam nie ma typu rekurencyjnego, jego definicja obejmuje jeden. Rzeczywicie, zmienna xjest stosowana do samej siebie, wic jeli oznaczymy jej typ, to równie jest funkcj pobierajc argument typu . Nastpnie otrzymujemy typ rekurencyjny zdefiniowany równaniem dla okrelonego typu . x

Symetrycznie czasami warto napisa funkcj, która zwraca sam siebie lub inn funkcj tego samego typu (na przykad do zakodowania automatu lub programu obsugi zdarze). Uproszczony przykad w jzyku C  :

/* syntaxe C pour léquation de types «function_t = (int  function_t)» ;
 * ne compile pas! */
typedef function_t (*function_t) (int) ;

function_t f (int n)
{
	printf("%i", n) ;
	return f ;
}

int main (void)
{
	f(1)(2)(3) ; /* devrait écrire «123» */
	return 0 ;
}

Jeli oznaczymy typ funkcji , to jest to funkcja, która przyjmuje liczb cakowit (typ ) i zwraca sam siebie (typ ); jego typ jest zatem równie , std równanie . ff

W rzeczywistoci, jak wyjaniono póniej, takie typy rekurencyjne nie s dozwolone, jak to ma miejsce w jzykach C czy Haskell. Ponisze przykady dziaaj w jzyku OCaml z opcj kompilacji -rectypes :

(* fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b ;
 * requiert loption de compilation «-rectypes» *)
let fix f = let g x a = f (x x) a in g g
(* f :(int -> 'a) as 'a ;
 * requiert loption de compilation «-rectypes» *)
let rec f n =
  Format.printf "%i" n ;
  f

let _ =
  f 1 2 3 (* écrit «123» *)

Teoria

W teorii typów typ rekurencyjny ma posta . Intuicyjnie ta notacja oznacza typ reprezentowany przez wyraenie , w którym moe pojawi si zmienna typu , i wyznacza sam typ .

Na przykad jeli , to jest typem funkcji, która przyjmuje liczb cakowit i zwraca funkcj tego samego typu, co ona sama. Moemy rozszerzy to wyraenie typu, zastpujc w zmiennej typ (co zauwaamy ), który daje . Moemy powtórzy t operacj tyle razy, ile potrzeba:

Powyszy przykad naturalnych liczb cakowitych jest zapisany , w którym dwa ramiona typu sum reprezentuj konstruktory i bez pobierania argumentu (reprezentowanego przez jednostk typu ) i pobierania elementu samego typu (reprezentowanego przez zmienn typu ). ZeroSuccZeroSuccNat

Z kolei przykad list elementów typu jest napisany . Typ jednostki reprezentuje konstruktora bez argumentów, typ produktu reprezentuje konstruktor majcy jako argumenty warto typu i inn warto typu . Przewijajc: Nil Cons

, jest
, jest
, jest

Sukcesywnie uzyskujemy typ list o dugoci zero ( ), jeden ( ), dwa ( ), trzy ( ) i tak dalej.

Chodzi o to, e typ rekurencyjny spenia nastpujce nieformalne równanie:

W poprzednich przykadach jest napisane odpowiednio:

Gdybymy pozwolili sobie na nieskoczone wyraenia typu, moglibymy rozszerzy si do nieskoczonoci i napisa odpowiednio:

  • (funkcja curried akceptujca dowoln liczb argumentów typu )
  • (to jest rzeczywicie Unia rozczne od pojedynczych, które mog by nazwane , , itd.)
  • ( Gwiazda Kleene )

Te nieskoczone wyraenia s jednak le zdefiniowane, poniewa odzwierciedlaj tylko jeden typ rozwizania, podczas gdy równanie typów moe dopuszcza kilka. Niejednoznaczno rozwizujemy, wybierajc najmniejszy lub najwikszy stay punkt cigu, jak wyjaniono w sekcji Dane i wspódane .

Aby nada sens równoci tego typu, wyróniamy dwie formy rekurencji, które róni si sposobem wprowadzania i eliminowania typów rekurencyjnych: ekwirursj i izorekursj .

Typy ekwiruralne

W przypadku typów ekwirursywnych typ i jego przepyw s równe - to znaczy te dwa wyraenia typu oznaczaj ten sam typ. W rzeczywistoci wikszo teorii typu ekwiursywnego idzie dalej i stwierdza, e dwa wyraenia z tym samym nieskoczonym rozwiniciem s równowane. To komplikuje system typów znacznie bardziej ni w przypadku typów izorursywnych. Trudniejsze s równie problemy algorytmiczne, takie jak sprawdzanie typu lub wnioskowanie o typie . Poniewa proste porównanie skadniowe nie jest wystarczajce dla typów ekwirursywnych, naley je przekonwertowa do postaci kanonicznej, co mona zrobi w formacie .

Typy ekwirursywne przechwytuj odwoujcy si do siebie (lub wzajemnie odwoujcy) charakter definicji typów w jzykach proceduralnych i obiektowych . Wystpuj równie w semantyce obiektów i klas w teorii typów.

Typy izorursywne

W przypadku typów izorursywnych typ i jego rozwinicie s typami odrbnymi i rozcznymi, niemniej jednak czy je izomorfizm, który jest materializowany przez konstrukcje okrelonych terminów. Dokadniej, mamy funkcje odwrotne i .

Typy izorursywne s bardzo obecne w jzykach funkcyjnych w postaci typów algebraicznych. W rzeczywistoci jzyki Haskell i OCaml (z wyjtkiem opcji kompilatora -rectypes) zabraniaj rekursji w aliasach typów - to znaczy równowanoci. Dlatego nastpujce definicje s nielegalne w Haskell:

type Bad = (Int, Bad)
type Evil = Bool -> Evil

To ograniczenie istnieje, poniewa podobnie jak typedefw jzyku C iw przeciwiestwie do typów algebraicznych, aliasy typów s po prostu zastpowane ich definicj podczas kompilacji. Typy algebraiczne umoliwiaj obejcie tego ograniczenia poprzez zawijanie wyraenia rekurencyjnego w konstruktorze:

data Good = Pair Int Good
data Fine = Fun (Bool->Fine)

Jednym ze sposobów zrozumienia tego jest zauwaenie, e ten dodatkowy poziom porednictwa sprawia, e operacje zawijania i rozwijania typów s jawne: konstrukcja wartoci (zastosowanie konstruktora) zawija jej typ, podczas gdy jej zniszczenie (przez filtrowanie wzorców ) powoduje jej rozwinicie. W ostatnim przykadzie:

roll :: (Bool->Fine) -> Fine
roll x = Fun x

unroll :: Fine -> (Bool->Fine)
unroll (Fun x) = x

Dziki temu moliwe jest zapisanie w Haskell sumatora punktów staych widocznych powyej:

data FunctionTakingItself b = R (FunctionTakingItself b -> b)

fix :: ((a -> b) -> a -> b) -> a -> b
fix f = let g y@(R x) a = f (x y) a in g (R g)

Podobnie moemy napisa w jzyku C przykad funkcji, która zwraca si sama:

/* définition récursive du type encapsulée dans une structure */
struct function_t {
	struct function_t (*fun) (int) ;
};
typedef struct function_t function_t ;

/* définition mutuellement récursive de la fonction f et de son encapsulation g */
static function_t g ;
function_t f (int n)
{
	printf("%i", n) ;
	return g ;
}
static function_t g = { .fun = f } ;

int main (void)
{
	g.fun(1).fun(2).fun(3) ; /* écrit «123» */
	return 0 ;
}

Dane i wspólne dane

Algebraicznie moemy zdefiniowa typ jako stay punkt funkcji (który z typem wie typ). Chodzi o to, aby wybra ten stay punkt. Moemy wzi najmniejszy stay punkt lub najwikszy. Czasami mówimy o danych w pierwszym przypadku i wspódanych w drugim przypadku. To rozrónienie jest szczególnie wane w programowaniu cakowitym (in) , w którym chcemy zagwarantowa przerwanie wszystkich oblicze. Rzeczywicie, w przypadku typów algebraicznych:  

  • dane s dobrze ugruntowane i dlatego przedstawiaj zasad powtarzalnoci , która umoliwia ich niszczenie (definiowanie funkcji na tych danych) rekurencyjnie w sposób koczcy;
  • Wspódane przedstawiaj zasad wspówystpowania , która pozwala na ich konstruowanie (definiowanie takich wartoci) rekurencyjnie w produktywny sposób .

Te dwa pojcia s dwojakie .

W sumie s to jedyne dwie dozwolone formy rekurencji. Te dwa ograniczenia maj na celu zapewnienie dobrego dziaania programów.

  • To, e dane s z koniecznoci skoczone, zapewnia zakoczenie funkcji, które je przetwarzaj, dziki zasadzie powtarzalnoci.
  • Wprowadzenie potencjalnie nieskoczonych wspódanych umoliwia odzyskanie formy niezakoczenia niezbdnej do realizacji interaktywnych programów ptlowych , takich jak system operacyjny , które reaguj na przepyw zdarze zewntrznych. W tym przypadku dobre zachowanie jest gwarantowane przez produktywno definicji wspórekurencyjnych: kady krok obliczeniowy wytwarza cz (wspókonstruktor) wspódanych, które mog by nastpnie uyte.

Aby nie ryzykowa, e funkcja zdefiniowana przez indukcj na danych zostanie wywoana na nieskoczonych wspódanych, rozwaymy róne typy danych i typy wspólnych danych, z dwoma rónymi sowami kluczowymi do ich zdefiniowania.


W poprzednim przykadzie list funkcj typów bya .

  • Jego najmniejszym punktem staym jest , czyli rodzaj list skoczonych .
  • Jego najwikszym staym punktem jest zbiór potencjalnie nieskoczonych list .

Gdybymy nie mieli konstruktora Nil(pozwalajcego znale list), to funkcja wygldaaby nastpujco :

  • najmniejszym punktem staym jest typ pusty , bez wartoci (bez niego nie mona zbudowa skoczonej listy);Nil
  • najwikszym staym punktem jest rodzaj nieskoczonych list.

Podobnie w przykadzie liczb naturalnych rozwaymy  :

  • najmniejszy stay punkt to rodzaj liczb naturalnych;
  • najwikszym staym punktem jest .

Podobna uwaga dotyczy producenta Zero.

Zwyke jzyki kompletne Turinga ignoruj ten niuans i pozwalaj na niekontrolowan rekurencj. Dlatego jest tylko jedno sowo kluczowe do zdefiniowania typu rekurencyjnego, który jest niejawnie najwikszym staym punktem. Wic w Haskell:

data List a = Nil | Cons a (List a)

moemy uy tych list jako danych, z funkcj zdefiniowan przez indukcj (ta definicja jest dobrze uzasadniona: kade wywoanie rekurencyjne jest wykonywane na danych mniejszych strukturalnie):

length :: List a -> Int
length Nil           = 0
length (Cons _ tail) = 1 + length tail

lub jako ko-dane, z definicj przez wspóindukcj (ta definicja jest produktywna: kada iteracja tworzy konstruktora):

infinite_list :: List Int
infinite_list = Cons 1 infinite_list -- la liste [ 1, 1, 1,  ]
naturals :: List Int
naturals = naturals_from 0 where -- la liste [ 0, 1, 2,  ]
  naturals_from n = Cons n (naturals_from (n+1))

Ocena leniwy moe napisa t definicj bez wchodzenia w nieskoczonej ptli oceny. Widzimy zatem, e lenistwo jest niezbdne do konstruowania wspódanych w jzyku totalnym.

Ale moemy równie pisa definicje rekurencyjne, które nie s ani powtarzalne, ani wspówracajce, niezalenie od tego, czy s istotne, czy nie. Zatem poprzedni przykad mona przepisa w cakowicie poprawny sposób, zgodnie z obowizujcym idiomem w jzyku Haskell (ta definicja nie powtarza si w najbardziej powszechnym sensie z powodu wezwania do map):

naturals :: List Int
naturals = Cons 0 (map succ naturals) -- la liste [ 0, 1, 2,  ]

Ale nic nie stoi na przeszkodzie, aby pisa bdne programy:

stupid list = stupid (Cons 1 list)

idiot = length naturals

Zobacz te

Uwagi

  1. Rekursja typu kontrawariantnego , której jest przykadem, daje dostp do kompletnoci i niezakoczenia Turinga . Rzeczywicie, jak wanie widzielimy, umoliwia wpisanie sumatora staopozycyjnego Y, dziki któremu moemy zapisa wszystkie funkcje rekurencyjne. Moemy równie napisa termin nie koczcy (czyli ) bardziej bezporednio .
  2. jak w zapisie z rachunku lambda , zmienna jest zwizana w ekspresji  ; litera nie jest znaczca, jest czci skadni.

Bibliografia

  1. (in) sprawdzanie typów i typ rekurencyjny (pisanie Y Combinator w Haskell / OCaml)  " na programmers.stackexchange.com ,(dostp 20 lipca 2016 )
  2. (w) David A. Turner ,   Total Functional Programming   , Journal of Universal Computer Science , tom.  10, n o  7,, s.  751768 ( DOI  10.3217 / jucs-010-07-0751 , przeczytaj online [PDF] )
  3. (in)   System OCaml, § 6.4. Wyraenia typu  : typy aliasowane i rekursywne   , na caml.inria.fr (dostp 20 lipca 2016 r. )  :   Typy rekurencyjne, dla których istnieje cieka rekurencyjna, która nie zawiera konstruktora typu obiektu lub wariantu polimorficznego, s odrzucane, z wyjtkiem sytuacji, gdy -rectypeswybrany jest tryb.  "
  4. (w) Nadji Gauthier i François Pottier ,   Numbering Matters: First-Order Canonical Forms for Second-Order Recursive Types   , Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP) , vol.  39 N O  9,, s.  150-161 ( DOI  10.1145 / 1016850.1016872 , przeczytaj online [PDF] )

(fr) Ten artyku zawiera fragmenty z Free On-line Dictionary of Computing, który zezwala na korzystanie z jego treci na podstawie licencji GFDL .

Mamy nadzieję, że informacje, które zgromadziliśmy na temat Typ rekurencyjny, były dla Ciebie przydatne. Jeśli tak, nie zapomnij polecić nas swoim przyjaciołom i rodzinie oraz pamiętaj, że zawsze możesz się z nami skontaktować, jeśli będziesz nas potrzebować. Jeśli mimo naszych starań uznasz, że informacje podane na temat _title nie są całkowicie poprawne lub że powinniśmy coś dodać lub poprawić, będziemy wdzięczni za poinformowanie nas o tym. Dostarczanie najlepszych i najbardziej wyczerpujących informacji na temat Typ rekurencyjny i każdego innego tematu jest istotą tej strony internetowej; kierujemy się tym samym duchem, który inspirował twórców Encyclopedia Project, i z tego powodu mamy nadzieję, że to, co znalazłeś o Typ rekurencyjny na tej stronie pomogło Ci poszerzyć swoją wiedzę.

Opiniones de nuestros usuarios

Bart Stasiak

Myślałem, że wiem już wszystko o zmiennej, ale w tym artykule zweryfikowałem, że pewne szczegóły, które uważałem za dobre, nie były tak dobre. Dziękuję za informacje.

Maria Walczak

Wreszcie! W dzisiejszych czasach wydaje się, że jeśli nie piszą artykułów składających się z dziesięciu tysięcy słów, to nie są szczęśliwi. Panowie autorzy treści, to TAK to dobry artykuł o Typ rekurencyjny.

Piotr Pawlak

Zgadza się. Zawiera niezbędne informacje o Typ rekurencyjny.

Greg Michalik

Wpis _zmienna bardzo mi się przydał.