Skip to content

Latest commit

 

History

History
234 lines (154 loc) · 5.77 KB

ADTs.md

File metadata and controls

234 lines (154 loc) · 5.77 KB

Algebraic Data Types (ADTs)


Георги Наков, nakov.gl at gmail com
Марин Маринов, marinov.ms+tues at gmail com

Технологично училище "Електронни Системи"
23 Ноември 2016г.

Какво са ADTs?


  • механизъм за създане на изброен тип - enum
  • механизъм за групиране на данни - struct
  • механизъм за създаване на изброен тип от групирани данни

Защо ADTs?


  • компилаторът се оплаква ако всички случаи не са обработени
  • подпомагат описването на проблема като предварително очаквани ситуации
  • предпазват от подаване на невалидни данни

ADTs като enum

Създаване на тип от предварително очаквани стойности. Компилаторът гарантира, че различна от изборените стойности не може да бъде присвоена на променлива от съответния тип.


data Answer = Yes | No

data CoinSides = Head | Tail

data DayOfWeek = Monday   | Tuesday | Wednesday |
                 Thursday | Friday  | Saturday  | Sunday

Pattern matching


scottishAnswer :: Answer -> String
scottishAnswer Yes = "Ay!"
scottishAnswer No  = "Naw!"

> scottishAnswer Yes  -- using the value `Yes`
"Ay!"
isWeekend :: DayOfWeek -> Bool
isWeekend Saturday = True
isWeekend Sunday   = True
isWeekend _        = False

> isWeekend Monday  -- using the value `Monday`
False

ADTs - групиране на данни


Също както tuples ADTs могат да се използват за групиране на данни. Разликата е, че те добавят и "таг". По този начин две структури с еднакви подтипове, дори еднакви данни, се третират по различен начин.


Синтаксис:

data URL = URLPath  String
--    |       |        |
--   Type    Tag   the value

Създаване на стойности

Тагът също така се нарича Value constructor. Той се използва като функция и създава стойност от съответния тип.


data Password = PasswordText String
data Email    = EmailText    String

pwd :: Password
pwd = PasswordText "secure"

email :: Email
email = EmailText "[email protected]"
email' :: Email
email' = PasswordText "[email protected]"  -- Error

Създаване на стойности ...


Важно: Value конструкторът не е тип!

asEmail :: String -> EmailText  -- Error!
asEmail str = EmailText str

Pattern matching - destructuring


--            Tag    x     y
data Point = Point  Int   Int

zero :: Point
zero = Point 0 0

translateX :: Int -> Point -> Point
translateX offset (Point x y) = Point (x + offset) y


Важно: В случая Point се използва в 2 контекта - за създаване на стойност Point 0 0 и като тип zero :: Point. Това е чест прийом, когато съществува само една дефиниция.

ADTs - изброени групирани стойности

Силата на ADTs е в комбиниране на предходните две употреби. Така се създава комбинация от очаквани ситуации, които могат да носят и контекст (данни) със себе си.


--                             longitude  latitude
data Coordinates = Coordinates    Int        Int

--                           city   street   #
data Address = TextAddress  String  String  Int
             | Location     Coordinates

ADTs - рекурсивни типове

Value конструкторите могат да реферират към типа за създаване на вгнездени, рекурсивни структури.

data XMLElement = Text String
                | Tag  String XMLElement


stringify :: XMLElement -> String
stringify (Text text)  = text
stringify (Tag tag el) = open ++ stringify el ++ close
    where open  = "<"  ++ tag ++ ">"
          close = "</" ++ tag ++ ">"

> stringify (Tag "book" (Tag "title" (Text "1984")))
"<book><title>1984</title></book>"

Автоматично генериране на Eq

Тъй като ADT стойностите са предварително дефинирани, нормално очакване е да могат да бъдат сравнявани с ==. Това по подразбиране не е така, но тъй като те са immutable Haskell може автоматично да генерира кода за сравнение. Това става чрез ключовата дума deriving.

Автоматично генериране на Eq - пример

data Color = Red
           | Green
           | Blue
           | RGB Int Int Int
           deriving (Eq)

isBlack :: Color -> Bool
isBlack (RGB 0 0 0) = True
isBlack _           = False
> Red == Red
True

> RGB 11 22 33  == RGB 11 22 33
True

> isBlack (RGB 0 0 0)
True