Hátrányok

A programozásban a hátrányok (/ˈkɒnz/ vagy /ˈkɒns/) alapvető jellemzők a Lisp programozási nyelv legtöbb dialektusában . cons két értéket vagy két értékmutatót tartalmazó memóriaobjektumokat hoz létre [1] . A függvény neve a cons truct , azaz az építés szó rövidítéseként alakult ki . Ez azt jelentette, hogy a cons egy új objektumot hoz létre a memóriában a meglévő kettőből. Ezeket az objektumokat cons celláknak, cons-oknak, nem atomi S-kifejezéseknek ("NATS") vagy cons pároknak is nevezik. Az angolban a LISP programozók szakzsargonjában a cons szót is igeként használják. A "to cons x to y " kifejezés" ugyanaz, mint az "új objektum létrehozása a következő kóddal: ". (cons x y)

A funkcionális programozási nyelvek felhasználói körében és a listákkal való munka összefüggésében a "cons"-t szleng kifejezésként is használják a hasonló célú, hasonló célú operátorokra, amelyeket meglehetősen eltérően írnak. Jó példa erre az ML , Scala , F# és Elm :: operátora, vagy a Haskel l : operátora, amelyek egy elemet adnak a lista fejéhez.

Használat

Bár a hátrányos cellák felhasználhatók rendezett adatpárok tárolására , gyakrabban használják összetettebb összetett adatszerkezetek, például listák és bináris fák létrehozására .

Rendezett párok

Például a Lisp-kifejezés (cons 1 2) olyan cellát hoz létre, amely 1-est tartalmaz a bal felében (úgynevezett autó mező), és egy 2-t a jobb felében (a cdr mezőben). A Lisp jelölésben az érték (cons 1 2) így néz ki:

(12)

Figyelje meg a pontot 1 és 2 között; ez azt jelzi, hogy az S-kifejezés egy "pont-pár" (úgynevezett "cons-pair"), és nem egy "lista".

Listák

A Lisp-ben a listák a hátránypárok tetején vannak implementálva. Pontosabban, a Lisp bármely listája a következőképpen néz ki:

  1. Az üres lista, amelyet () jelölünk, egy speciális objektum. Általában nullának is nevezik .
  2. Az egyelemű lista egy kons-pár, amelynek első cellája az egyetlen elemét tartalmazza, a második cella pedig nullára utal.
  3. A két vagy több elemből álló lista egy cons-pair, amelynek első eleme a lista első eleme, a második pedig arra a listára vonatkozik, amely a fő lista vége.

A bemutatott nézet egy egyszeresen linkelt lista legegyszerűbb formája, amelynek tartalma könnyen kezelhető a cons, car , cdr parancsokkal . Képzeljünk el például egy listát 1, 2 és 3 elemekkel. Egy ilyen listát három lépésben lehet létrehozni:

hátrányok (3 nulla) Hátrányok (2 eredménye az előző műveletből) Hátrányok (1 eredménye az előző műveletből)

vagy ugyanaz, egy kifejezésben:

( cons 1 ( cons 2 ( cons 3 nil )

a cons műveletek ugyanazt a sorozatát rövidítik:

( lista 1 2 3 )

ennek eredményeként létrehozunk egy listát:

(1 . (2 . (3 . null)))

a következő szerkezettel:

*--*--*--nulla | | | 1 2 3

a következőképpen lehet rövidíteni:

(1 2 3)

A fentiek alapján a hátrányokkal új elemet lehet hozzáadni egy meglévő linkelt lista elejére. Például, ha x a fent definiált lista, akkor (kons 5 x) létrehoz egy listát:

(5 1 2 3)

Fák

A bináris fák , amelyek csak a leveleikben tárolják az adatokat, szintén könnyen megvalósíthatók hátrányokkal. Példa:

( cons ( cons 1 2 ) ( cons 3 4 ))

létrehozza a fa listaábrázolását:

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

vagyis

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

Technikailag a lista (1 2 3) az előző példában is egy kiegyensúlyozatlan bináris fa. Ennek ellenőrzésére egyszerűen átrajzoljuk a diagramot

*--*--*--nulla | | | 1 2 3

az egyenértékűre:

* / \ egy* / \ 2* / \ 3 nulla

Funkcionális megvalósítás

Mivel a Lisp első osztályú függvényeket tartalmaz , minden adatstruktúra, beleértve a hátrányos cellákat is, megvalósítható függvények segítségével. Példa a séma nyelvén :

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

Ezt a technikát " egyházi kódolásnak " nevezik . Lehetővé teszi a cons , car és cdr műveletek végrehajtásának felülbírálását "cons cellák" segítségével. Az egyházi kódolás elterjedt módja az adatstruktúrák meghatározásának tiszta lambda-számításban .

Egy ilyen megvalósítás, bár tudományos szempontból érdekes, nem praktikus, mert a hátrányos cellákat megkülönböztethetetlenné teszi bármely más Scheme eljárástól, és szükségtelen számítási hatékonyságot okoz. Ugyanez a megközelítés azonban alkalmazható összetettebb algebrai adattípusokhoz is, változatokkal . Ebben az esetben valóban hatékonyabb lehet, mint az adatok memóriában való megjelenítésének egyéb módjai [2] .

Lásd még

Linkek

  • SDRAW , Common Lisp kód hátrányos cellákból álló adatszerkezetek rajzolásához. Szerző: David S. Touretzky.

Jegyzetek

  1. ↑ E. I. Bolshakova, N. V. Gruzdeva. A programozás alapjai Lispben. - Moszkva: M. V. Lomonoszovról elnevezett Moszkvai Állami Egyetem CMC karának kiadói osztálya; MAKS Press, 2010, 2010.
  2. ↑ Archivált másolat (downlink) . Letöltve: 2009. március 1. Az eredetiből archiválva : 2010. március 31.. 
 Adattípusok
Értelmezhetetlen
Numerikus
Szöveg
Referencia
Összetett
absztrakt
Egyéb
Kapcsolódó témák