Nackdelar

Inom programmering är nackdelar (/ˈkɒnz/ eller /ˈkɒns/) en grundläggande funktion i de flesta dialekter av programmeringsspråket Lisp . nackdelar skapar minnesobjekt som innehåller två värden eller två pekare till värden [1] . Namnet på funktionen bildades som en förkortning för ordet konstruktion , det vill säga konstruktion. Det innebar att cons konstruerar ett nytt objekt i minnet från de befintliga två. Dessa objekt kallas också för nackdelar, nackdelar, icke-atomära S-uttryck ("NATS") eller nackdelar. På engelska, i LISP-programmerares jargong, används ordet cons också som verb. Uttrycket "to cons x onto y " är ekvivalent med "konstruera ett nytt objekt med hjälp av följande kod: ". (cons x y)

Bland användare av funktionella programmeringsspråk och i samband med att arbeta med listor används "nackdelar" också som en slangterm för liknande operatörer med liknande syfte, som skrivs helt annorlunda. Bra exempel är ::-operatorerna i ML , Scala , F# och Elm , eller operatorn : i Haskel l, som lägger till ett element till huvudet på en lista.

Användning

Även om nackdelarceller kan användas för att lagra ordnade datapar , används de oftare för att bygga mer komplexa sammansatta datastrukturer, såsom listor och binära träd .

Beställda par

Till exempel konstruerar Lisp-uttrycket (nackdelar 1 2) en cell som innehåller en 1 i dess vänstra halva (kallas bilfältet) och en 2:a i dess högra halva (cdr-fältet). I Lisp-notation ser värdet (nackdelar 1 2) ut så här:

(12)

Notera punkten mellan 1 och 2; detta indikerar att S-uttrycket är ett "dot-pair" (så kallat "cons-pair") och inte en "lista".

Listor

I Lisp implementeras listor ovanpå cons-par. Mer specifikt ser strukturen för en lista i Lisp ut så här:

  1. Den tomma listan, betecknad som (), är ett speciellt objekt. Det kallas också vanligtvis noll .
  2. En enelementslista är ett cons-par vars första cell innehåller sitt enda element och den andra cellen refererar till noll.
  3. En lista med två eller flera element är ett cons-pair, vars första element är det första elementet i listan, och det andra hänvisar till listan som är huvudlistans svans.

Vyn som visas är den enklaste formen av en enkellänkad lista, vars innehåll är lätt att manipulera med kommandona nackdelar, bil , cdr . Föreställ dig till exempel en lista med element 1, 2 och 3. En sådan lista kan skapas i tre steg:

nackdelar (3 noll) Nackdelar (2 resultat av tidigare operation) Nackdelar (1 resultat av tidigare operation)

eller samma, i ett uttryck:

( nackdelar 1 ( nackdelar 2 ( nackdelar 3 noll )))

samma sekvens av nackdelar förkortas:

( lista 1 2 3 )

som ett resultat skapar vi en lista:

(1 . (2 . (3 . noll)))

med följande struktur:

*--*--*--noll | | | 1 2 3

det kan förkortas enligt följande:

(1 2 3)

Baserat på ovanstående kan nackdelar användas för att lägga till ett nytt element på framsidan av en befintlig länkad lista. Till exempel, om x är listan vi definierade ovan, kommer (nackdelar 5 x) att skapa en lista:

(5 1 2 3)

Träd

Binära träd , som endast lagrar data i sina löv, är också lätta att implementera med nackdelar. Exempel:

( nackdelar ( nackdelar 1 2 ) ( nackdelar 3 4 ))

skapar en listrepresentation av trädet:

((1 . 2) . (3 . 4))

det är

* / \ ** / \ / \ 1 2 3 4

Tekniskt sett är listan (1 2 3) i föregående exempel också ett obalanserat binärt träd. För att verifiera detta ritar vi helt enkelt om diagrammet

*--*--*--noll | | | 1 2 3

till motsvarande:

* / \ ett * / \ 2 * / \ 3 noll

Funktionell implementering

Eftersom Lisp innehåller förstklassiga funktioner kan alla datastrukturer, inklusive nackdelar, implementeras med funktioner. Exempel på schemaspråk :

( definiera ( cons x y ) ( lambda ( m ) ( m x y ))) ( definiera ( car z ) ( z ( lambda ( p q ) p )) ( definiera ( cdr z ) ( z ( lambda ( p q ) ) q )))

Denna teknik är känd som " kyrkokodning ". Det låter dig åsidosätta implementeringen av operationerna cons , car och cdr med hjälp av "cons celler". Kyrkokodning är ett vanligt sätt att definiera datastrukturer i ren lambda-kalkyl .

En sådan implementering, även om den är akademiskt intressant, är opraktisk eftersom den gör nackdelar celler omöjliga att skilja från någon annan Scheme-procedur och introducerar onödig beräkningsineffektivitet. Samma tillvägagångssätt kan dock användas för mer komplexa algebraiska datatyper med varianter . I det här fallet kan det verkligen vara mer effektivt än andra sätt att representera data i minnet [2] .

Se även

Länkar

  • SDRAW , Common Lisp -kod för att rita datastrukturer som består av nackdelar. Författare: David S. Touretzky.

Anteckningar

  1. ↑ E.I. Bolshakova, N.V. Gruzdeva. Grunderna i programmering i Lisp. - Moskva: Förlagsavdelning vid fakulteten vid CMC vid Moscow State University uppkallad efter M.V. Lomonosov; MAKS Press, 2010, 2010.
  2. ↑ Arkiverad kopia (nedlänk) . Hämtad 1 mars 2009. Arkiverad från originalet 31 mars 2010. 
 Datatyper
Otolkbart
Numerisk
Text
Referens
Sammansatt
abstrakt
Övrig
Relaterade ämnen