Algebraic Data Types

Table of Contents

  • Index
  • Repository
    •

    1 Algebraic Data Types

    [Under Construction]

    1.1 Overview

    Algebraic data type is a type formed by combining types. It can be used to implement Records, Enumerated Sets, option types and Recursive types. Note: Algebraic data types must not be confused with Abstract data types.

    • Applications of Algebraic Data Types
      • Build Embedded Domain specific languages - EDSLs
      • Build Interpreters
      • Self Documenting code
      • Avoid Null checking error / Null reference bug
    • Product Types
      • Tuples of types - (Int, Float)
      • Records
    • Sum Types
      • Tagged or disjoint unions or variant types
    • Enumerated types
    • Option Type

    Option type is useful in functional programming to avoid boilerplate null checking bug on non-deterministic computations.

    Language Syntax  
    Haskell data Maybe a = Nothing Just a
    OCaml and F# type 'a option = None Some of 'a
    Standard ML datatype 'a option = NONE SOME of 'a
    Java 8 the option type is defined as parameterized final class Optional<T>  

    See also:

    Selected Wikipedia Pages

    1.2 Enumerated Data Type

    Example: Days of Week

    Enumerated sets is type which can only have a limited number of values. 

    data Weekday = Monday
             | Tuesday
             | Wednesday
             | Thursday
             | Friday
             | Saturday
             | Sunday
  deriving (Eq, Ord, Enum)

fromDay :: Weekday -> Int
fromDay = fromEnum

toDay :: Int -> Weekday
toDay = toEnum

> map (Monday<) [Tuesday, Friday, Sunday]
[True,True,True]

> map (Thursday<) [Monday, Tuesday, Friday, Sunday]
[False,False,True,True]

>
> Monday == Tuesday
False
> Tuesday == Tuesday
True
>

>
> fromDay Saturday
5

> 1 + fromDay Monday
1
> 1 + fromDay Saturday
6
> Saturday
Saturday
>
> toDay 0
Monday
> toDay 6
Sunday
>
>

    Example: Colors 

    data Color
    = Red
    | Orange
    | Yellow
    | Green
    | Blue
    | Purple
    | White
    | Black
    | CustomColor Int Int Int -- R G B components
    deriving (Eq)

colorToRGB Red    = (255,0,0)
colorToRGB Orange = (255,128,0)
colorToRGB Yellow = (255,255,0)
colorToRGB Green  = (0,255,0)
colorToRGB Blue   = (0,0,255)
colorToRGB Purple = (255,0,255)
colorToRGB White = (255,255,255)
colorToRGB Black = (0,0,0)
colorToRGB (CustomColor r g b) = (r,g,b)   -- this one is new


>
> Red == White
False
>
> Red == Red
True
>

> let b = CustomColor 120 240 100
> colorToRGB b
(120,240,100)

> map colorToRGB [ Blue, White, Yellow ]
[(0,0,255),(255,255,255),(255,255,0)]
>

    Example: Shapes 

    data Shape = Circle  Float
           | Rect    Float Float
    deriving Show

square   :: Float -> Shape
square n =  Rect n n

area            :: Shape -> Float
area (Circle r)  = pi * r^2
area (Rect x y)  = x  * y

is_circle (Circle _ ) = True
is_circle _           = False

is_rect   (Rect _ _)  = True
is_rect   _           = False

describe (Circle radius) = putStrLn $ "Circle of radius : " ++ show(radius)
describe (Rect h w)      = putStrLn $ "Rectangle of " ++ show(h) ++ " x " ++ show(w)

> area $  Rect 20 30
600.0
> area $ Circle 20
1256.6371
> area $ square 20
400.0
>
> [Rect 20.0 30.0, Rect 10.0 30.0, Circle 3.0, Circle 4.0]
[Rect 20.0 30.0,Rect 10.0 30.0,Circle 3.0,Circle 4.0]
>
> map area [Rect 20.0 30.0, Rect 10.0 30.0, Circle 3.0, Circle 4.0]
[600.0,300.0,28.274334,50.265484]
>

> :t is_rect
is_rect :: Shape -> Bool
> :t is_circle
is_circle :: Shape -> Bool
>

> filter is_rect [Rect 20.0 30.0, Rect 10.0 30.0, Circle 3.0, Circle 4.0]
[Rect 20.0 30.0,Rect 10.0 30.0]

> filter is_circle [Rect 20.0 30.0, Rect 10.0 30.0, Circle 3.0, Circle 4.0]
[Circle 3.0,Circle 4.0]

> :t describe
describe :: Shape -> IO ()
>

> describe (Rect 20 30)
Rectangle of 20.0 x 30.0

> describe (Circle 3.60)
Circle of radius : 3.6
>

> mapM_ describe [Rect 20.0 30.0, Rect 10.0 30.0, Circle 3.0, Circle 4.0]
Rectangle of 20.0 x 30.0
Rectangle of 10.0 x 30.0
Circle of radius : 3.0
Circle of radius : 4.0
>

> let describe_list = mapM_ describe
>
> describe_list [Rect 20.0 30.0, Rect 10.0 30.0, Circle 3.0, Circle 4.0]
Rectangle of 20.0 x 30.0
Rectangle of 10.0 x 30.0
Circle of radius : 3.0
Circle of radius : 4.0
>

    1.3 Typeclass without Record Syntax

    Example: Students GPA 

    data Student = USU String Float
             deriving (Show)

get_gpa :: Student -> Float
get_gpa (USU _ grade) = grade

get_name :: Student -> String
get_name (USU name _ ) = name

class_gpa :: [Student] -> Float
class_gpa myclass = (sum c) / fromIntegral (length c)
                  where
                  c = map get_gpa myclass


> let myke = USU "Mike" 4.0
>
>  get_name myke
"Mike"
>  get_gpa myke
4.0
>

>  let myclass = [USU "Mike" 3.7, USU "Steve" 3.9, USU "Fred" 2.9, USU "Joe" 1.5]
>

>  class_gpa myclass
3.0

    1.4 Record Syntax

    Example: Typeclass with record Syntax 

    data Person = Person { firstName :: String,
                       lastName :: String,
                       age :: Int
                     }
                     deriving (Eq, Show, Read)


people = [ Person { firstName = "Ayn",  lastName = "Rand",  age =50},
           Person { firstName = "John", lastName = "Galt",  age =28},
           Person { firstName = "Adam", lastName = "Smith", age =70}]


{- Get someone from the people database -}
getPerson n = people !! n

{- Show Person -}
showPerson :: Person -> String
showPerson person  = "Name: " ++ show(firstName person) ++ " - Last Name: " ++ show(lastName person) ++ " - Age " ++ show(age person)

> people
[Person {firstName = "Ayn", lastName = "Rand", age = 50},Person {firstName = "John", lastName = "Galt", age = 28},Person {firstName = "Adam", lastName = "Smith", age = 70}]
>

> map firstName people
["Ayn","John","Adam"]
>

> map (\el ->  fst el ++ " " ++  snd el) $ zip (map firstName people) (map lastName people)
>  ["Ayn Rand","John Galt","Adam Smith"]


> people !! 1
Person {firstName = "John", lastName = "Galt", age = 28}
> people !! 2
Person {firstName = "Adam", lastName = "Smith", age = 70}
>

> "person 0 is " ++ show (people !! 0)
"person 0 is Person {firstName = \"Ayn\", lastName = \"Rand\", age = 50}"
>
> "person 1 is " ++ show (people !! 1)
"person 1 is Person {firstName = \"John\", lastName = \"Galt\", age = 28}"
>


> let person = read "Person {firstName =\"Elmo\", lastName =\"NA\", age = 0}" :: Person
> person
Person {firstName = "Elmo", lastName = "NA", age = 0}
>
> firstName person
"Elmo"
> last
last      lastName
> lastName person
"NA"
> age person
0
>

> let tesla = Person { firstName = "Nikola", lastName = "Tesla", age =30}
> tesla
Person {firstName = "Nikola", lastName = "Tesla", age = 30}
>

> showPerson tesla
"Name: \"Nikola\" - Last Name: \"Tesla\" - Age 30"
>

    1.5 Recursive Data Types

    Example: Custom List Implementation

    File: list_cons.hs 

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

is_empty :: List t -> Bool
is_empty Nil =  True
is_empty _   =  False

is_empty2  lst = case lst of
                    Nil -> True
                    _   -> False

count :: List t -> Int
count lst =
    case lst of
        Nil             -> 0
        Cons a next_lst -> 1 + count next_lst

suml lst =
    case lst of
        Nil             -> 0
        Cons a next_lst -> a + suml next_lst

headl (Cons a _) = a
headl Nil        = error "Empty List"

safe_headl (Cons a _) = Just a
safe_headl Nil        = Nothing

lastl Nil           = error "Failed: Empty List"
lastl (Cons a Nil)  = a
lastl (Cons _ t)    = lastl t

{- Converts to Haskell List -}
to_list Nil         = []
to_list (Cons x xs) = x:(to_list xs)


takel n lst =
    case (n, lst) of
    (_, Nil      )  -> Nil
    (0, _        )  -> Nil
    (k, Cons h  t)  -> Cons h (takel (n-1) t)


nth lst n =
    case (n, lst) of
    (_, Nil)       -> error "Index too large"
    (0, Cons a _)  -> a
    (k, Cons h t)  -> nth t (n-1)


mapl f Nil          = Nil
mapl f (Cons h t)   = Cons (f h) (mapl f t)

filterl  f  Nil        = Nil
filterl  f (Cons h t)  =
    if f h
        then  Cons h (filterl f t)
        else  filterl f t

{- Empty List [] -}
list0 = Nil

{- Single element list -}
list1 = Cons 10 Nil
list2 = Cons "Haskell" Nil

list3 = Cons 10 (Cons 20 (Cons 30 Nil))
list4 = Cons 1.25 (Cons 0.65 (Cons 8.123 ( Cons 9.434 Nil)))

    Running in ghci 

    > :l list_cons.hs
[1 of 1] Compiling Main             ( list_cons.hs, interpreted )
Ok, modules loaded: Main.

> :t is_empty
is_empty :: List t -> Bool
> :t count
count :: List t -> Int


> list0
Nil
> list1
Cons 10 Nil
> list2
Cons "Haskell" Nil
> list3
Cons 10 (Cons 20 (Cons 30 Nil))
> list4
Cons 1.25 (Cons 0.65 (Cons 8.123 (Cons 9.434 Nil)))

> :t list0
list0 :: List a
> :t list1
list1 :: List Integer
> :t list2
list2 :: List [Char]
> :t list3
list3 :: List Integer
> :t list4
list4 :: List Double

> Cons 10.23 list0
Cons 10.23 Nil
>
> Cons 30 list1
Cons 30 (Cons 10 Nil)
>
> Cons 40 list3
Cons 40 (Cons 10 (Cons 20 (Cons 30 Nil)))
>
> Cons 50 (Cons 40 list3)
Cons 50 (Cons 40 (Cons 10 (Cons 20 (Cons 30 Nil))))


> is_empty list0
True
> is_empty list1
False
> is_empty list2
False
> is_empty list3
False
>

> is_empty2 list0
True
> is_empty2 list1
False
> is_empty2 list3
False
>


> count list0
0
> count list1
1
> count list2
1
> count list3
3

{- Getting the first element -}
> headl list0

*Example: Custom List Implementation*

File: list_cons.hs

#+BEGIN_SRC haskell

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

is_empty :: List t -> Bool
is_empty Nil =  True
is_empty _   =  False

is_empty2  lst = case lst of
                    Nil -> True
                    _   -> False

count :: List t -> Int
count lst =
    case lst of
        Nil             -> 0
        Cons a next_lst -> 1 + count next_lst

suml lst =
    case lst of
        Nil             -> 0
        Cons a next_lst -> a + suml next_lst

headl (Cons a _) = a
headl Nil        = error "Empty List"

safe_headl (Cons a _) = Just a
safe_headl Nil        = Nothing

lastl Nil           = error "Failed: Empty List"
lastl (Cons a Nil)  = a
lastl (Cons _ t)    = lastl t

{- Converts to Haskell List -}
to_list Nil         = []
to_list (Cons x xs) = x:(to_list xs)


takel n lst =
    case (n, lst) of
    (_, Nil      )  -> Nil
    (0, _        )  -> Nil
    (k, Cons h  t)  -> Cons h (takel (n-1) t)


nth lst n =
    case (n, lst) of
    (_, Nil)       -> error "Index too large"
    (0, Cons a _)  -> a
    (k, Cons h t)  -> nth t (n-1)


mapl f Nil          = Nil
mapl f (Cons h t)   = Cons (f h) (mapl f t)

filterl  f  Nil        = Nil
filterl  f (Cons h t)  =
    if f h
        then  Cons h (filterl f t)
        else  filterl f t

{- Empty List [] -}
list0 = Nil

{- Sigle element list -}
list1 = Cons 10 Nil
list2 = Cons "Haskell" Nil

list3 = Cons 10 (Cons 20 (Cons 30 Nil))
list4 = Cons 1.25 (Cons 0.65 (Cons 8.123 ( Cons 9.434 Nil)))
```

Running in ghci
```haskell

> :l list_cons.hs
[1 of 1] Compiling Main             ( list_cons.hs, interpreted )
Ok, modules loaded: Main.

> :t is_empty
is_empty :: List t -> Bool
> :t count
count :: List t -> Int


> list0
Nil
> list1
Cons 10 Nil
> list2
Cons "Haskell" Nil
> list3
Cons 10 (Cons 20 (Cons 30 Nil))
> list4
Cons 1.25 (Cons 0.65 (Cons 8.123 (Cons 9.434 Nil)))

> :t list0
list0 :: List a
> :t list1
list1 :: List Integer
> :t list2
list2 :: List [Char]
> :t list3
list3 :: List Integer
> :t list4
list4 :: List Double

> Cons 10.23 list0
Cons 10.23 Nil
>
> Cons 30 list1
Cons 30 (Cons 10 Nil)
>
> Cons 40 list3
Cons 40 (Cons 10 (Cons 20 (Cons 30 Nil)))
>
> Cons 50 (Cons 40 list3)
Cons 50 (Cons 40 (Cons 10 (Cons 20 (Cons 30 Nil))))


> is_empty list0
True
> is_empty list1
False
> is_empty list2
False
> is_empty list3
False
>

> is_empty2 list0
True
> is_empty2 list1
False
> is_empty2 list3
False
>


> count list0
0
> count list1
1
> count list2
1
> count list3
3

{- Getting the first element -}
> headl list0
 *** Exception: Empty List

> headl list1
10
> headl list2
"Haskell"
> headl list3
10
> headl list4
1.25
>

{- Safe version of headl -}
> safe_headl list0
Nothing
> safe_headl list1
Just 10
> safe_headl list2
Just "Haskell"
> safe_headl list3
Just 10
> safe_headl list4
Just 1.25
>
> :t safe_headl
safe_headl :: List a -> Maybe a
>

{- Getting the last element -}
> lastl list0

 *** Exception: Failed: Empty List

> lastl list1
10
> lastl list2
"Haskell"
> lastl list3
30
> lastl list4
9.434
>

{- Converting to Standard Haskell List -}
> to_list list0
[]
> to_list list1
 [ 10 ]
> to_list list2
["Haskell"]
> to_list list3
[10,20,30]
> to_list list4
[1.25,0.65,8.123,9.434]

> :t to_list
to_list :: List a -> [a]

> takel 0 Nil
Nil
> takel 10 Nil
Nil
> takel 0 list4
Nil
> takel 1 list4
Cons 1.25 Nil
> takel 2 list4
Cons 1.25 (Cons 0.65 Nil)
> takel 3 list4
Cons 1.25 (Cons 0.65 (Cons 8.123 Nil))
> takel 4 list4
Cons 1.25 (Cons 0.65 (Cons 8.123 (Cons 9.434 Nil)))
> takel 5 list4
Cons 1.25 (Cons 0.65 (Cons 8.123 (Cons 9.434 Nil)))
> takel 6 list4
Cons 1.25 (Cons 0.65 (Cons 8.123 (Cons 9.434 Nil)))
> takel 26 list4
Cons 1.25 (Cons 0.65 (Cons 8.123 (Cons 9.434 Nil)))

{-
    Infinite List
-}

> let ones = Cons 1 ones
>
> takel 1 ones
Cons 1 Nil
>
> takel 3 ones
Cons 1 (Cons 1 (Cons 1 Nil))
>
> takel 5 ones
Cons 1 (Cons 1 (Cons 1 (Cons 1 (Cons 1 Nil))))

> let from n = Cons n (from (n+1))
> takel 3 (from 0)
Cons 0 (Cons 1 (Cons 2 Nil))
> takel 3 (from 3)
Cons 3 (Cons 4 (Cons 5 Nil))
> takel 10 (from 8)
Cons 8 (Cons 9 (Cons 10 (Cons 11 (Cons 12 (Cons 13 (Cons 14 (Cons 15 (Cons 16 (Cons 17 Nil)))))))))


> let from_step start step = Cons start (from_step (start+step) step)
> takel 3 (from_step 1 3)
Cons 1 (Cons 4 (Cons 7 Nil))
>
> takel 6 (from_step 2 4)
Cons 2 (Cons 6 (Cons 10 (Cons 14 (Cons 18 (Cons 22 Nil)))))

> takel 8 (from_step 0 1)
Cons 0 (Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 (Cons 6 (Cons 7 Nil)))))))

> nth (from_step 0 1) 0
0
> nth (from_step 0 1) 1
1
> nth (from_step 0 1) 2
2
> nth (from_step 0 1) 6
6
> nth (from_step 0 1) 22
22
> nth (from_step 0 1) 60
60
>
>
> :t nth
nth :: (Eq t, Num t) => List t1 -> t -> t1
>


> mapl (\x -> 3*x + 5) list0
Nil
> mapl (\x -> 3*x + 5) list3
Cons 35 (Cons 65 (Cons 95 Nil))
> mapl (\x -> 3*x + 5) list4
Cons 8.75 (Cons 6.95 (Cons 29.369 (Cons 33.302 Nil)))
>
> :t mapl
mapl :: (t -> a) -> List t -> List a


>
> list4
Cons 1.25 (Cons 0.65 (Cons 8.123 (Cons 9.434 Nil)))
>
> filterl (\x -> x > 3.5) list4
Cons 8.123 (Cons 9.434 Nil)
>
> filterl (\x -> x > 8) list4
Cons 8.123 (Cons 9.434 Nil)
>
> :t filterl
filterl :: (a -> Bool) -> List a -> List a

    Reference:

    Author: nobody

    Created: 2018-05-07 Mon 10:13

    Emacs 25.3.1 (Org mode 8.2.10)

    Validate