Abstract datatypes


The use of abstract data types is to build ways of storing values in a compact 
form using a single reference. Data types are implemented at a lower level
than the program where it is so it is generally not necessary to know how they are implemented. 

In general only a certain number of functions are made visible to the user 
of the data type which enables him to store and retrieve data without finding
out about the inner representation.

   

------------------------------------------------------------------------------

The data statement



      ----------------------------------------------------------

                   Enumerated datatypes


>     data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
      
   This defines a data type Day whose possible values are (Sun,Mon..Sat)      
   We can define our versions of Equality and Ord on these type values  


                 ------------------------------

    Writing functions involving user defined datatypes:

>       weekday :: Day -> Bool
>       weekday Sun = False
>       weekday Sat = False
>       weekday _   = True

         Deriving type classes using the deriving statement

>      data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
>        deriving (Eq, Ord, Show)

        Eq and Ord define a certain way of ordering type values by the default 
        order in which they are enumerated 
        Eg deriving(Ord)
           (Sun < Mon) = True  

        Refer to program (/haskell/trial/Day.hs)

      Displaying these values requires Show: (show can be modified)

>      nextday :: Day -> Day

      Show guarantees a function

>        show :: Day -> String -- Show is a function defined in Class Show

      Can redefine show: e.g. show Sun = "Sunday" etc

         -------------------------------------------------

 However these data types can have more structure than just enumerations


Eg

>    data Shape = Square Float | Circle Float | Rectangle Float Float

>      area :: Shape -> Float

>      area (Square x)      = x*x
>      area (Circle r)      = pi*r*r
>      area (Rectangle l w) = l*w

>      where
>         pi = 3.1415927

 Note: In this case the data type stores a structure that the data type can take
        


Recursive data types

      data Mylist = Empty | Listof Int Mylist


-- Empty, Listof etc are constructors that "combine" their arguments

-- Constructors can have zero arguments : constants like Empty,
   Sun, Mon


Trees

      data Tree = Nil | Node Int Tree Tree

-- Each node has two children, left and right

-- Draw trees, explain size, height

-- Recursive functions on trees: size, height, listout



Supplying your own definition to make a dataype an instance of a
class

  instance Show Day where
    show :: Day -> String
    show Sun = "Sunday"
    ...
    show Sat = "Saturday"

Hiding details of the implementation using modules
       
  Define a stack
  Only push, pop, isempty and empty should be visible
  Export only these functions

Recursive polymorphic datatypes

  Mylist a = Empty | Listof a (Mylist a)

  Tree a = Nil | Node a (Tree a) (Tree a)

Infix constructors can be used: must start with ":"


Stacks and queues

  Using stacks for expression evaluation

  Implementing stacks and queues as lists

  Hiding details about the implementation

  An efficient implementation of queues with two lists with
  amortised linear time complexity