Datatypes and Recursion

Slides

Quizzes

cse116-para-ind -> C cse116-adt-ind -> D cse116-case-ind -> B cse116-case2-ind -> D cse116-rectype-ind -> E cse116-tree-ind -> C cse116-leaves-ind -> D cse116-tail-ind -> NO

Representing complex data

  • base/primitive types: int, float, bool, etc

  • ways to build up types: functions, tuples, lists

Algebraic Data Types: a technique to build data types from these

Note

Tuples can do the job, but there are two problems:

  • verbose and unreadable

  • no type checking (unsafe)

type Date = (Int, Int, Int)
type Time = (Int, Int, Int)

deadDate :: Date
deadDate = (2, 4, 2019)

deadTime :: Time
deadTime = (11, 59, 59)

-- example: extend
extension :: Date -> Date
extension = ...

-- however, you can do
extension deadTime -- which should error!

Solution: construct datatypes

data Date = Date Int Int Int
data Time = Time Int Int Int
-- constructor ^  ^ param types

deadDate :: Date
deadDate = Date 2 4 2019

deadTime :: Time
deadTime = Time 11 59 59

Building Data Types

  1. Product types (each-of): a value of T contains a value of T1 and a value of T2

  2. Sum types (one-of): A value of T contains a value of T1 or a value of T2

  3. Recursive types: A value of T contains subvalues of type T

Product Types

You can name the constructor params:

data Date = Date {
    month :: Int,
    day :: Int,
    year :: Int
}

deadDate = Date 2 4 2019
deadMonth = month deadDate
-- field name is func that accesses date

Sum Types

e.g. a type for Paragraph that is one of the three options

data Paragraph =
      Text String
    | Heading Int String
    | List Bool [String]

Recursive Types

See recursive-types

Constructing Datatypes

data T =
      C1 T11 .. T1k
C2 T21 .. T2l
..
Cn Tn1 .. Tnm

T is the datatype

C1 .. Cn are the constructors

A value of type T is

  • either C1 v1 .. vk with vi :: T1i

  • or C2 v1 .. vl with vi :: T2i

  • or …

  • or Cn v1 .. vm with vi :: Tni

Writing Functions

e.g. how to write a function to convert nanoMD to HTML?

Pattern Matching

match on the constructor

html :: Paragraph -> String
html (Text str) = ...
html (Heading lvl str) = ...
html (List ord items) = ...

But, there are dangers:

-- example: missing a type
html :: Paragraph -> String
html (Text str) = ...
html (List ord items) = ...

html (Heading 1 "Introduction") -- runtime error!

You can also pattern match inside the program:

html :: Paragraph -> String
html p =
    case p of
        Text str -> ...
        Heading lvl str -> ...
        List ord items -> ...

Case

case e of
    pattern1 -> e1
    pattern2 -> e2
    ...
    patternN -> eN

has type T if:

  • each e1..eN has type T

  • e has some type D

  • each pattern1..patternN is a valid pattern for D

Recursive Types

Let’s define natural numbers.

data Nat = Zero       -- base constructor
           | Succ Nat -- inductive constructor

Zero      -- 0
Succ Zero -- 1

A Nat value is a box named Zero or a box labeled Succ with another Nat in it

Using as Parameter

toInt :: Nat -> Int
toInt Zero     = 0           -- base case
toInt (Succ n) = 1 + toInt n -- inductive case

Using as Result

fromInt :: Int -> Nat
fromInt n
    | n <= 0    = Zero
    | otherwise = Succ (fromInt (n - 1))

-- and operations
add :: Nat -> Nat -> Nat
add Zero     m = m
add (Succ n) m = Succ (add n m)

sub :: Nat -> Nat -> Nat
sub n        Zero     = n
sub Zero     _        = Zero
sub (Succ n) (Succ m) = sub n m

Lists

Lists aren’t built in!

data List = Nil
    | Cons Int List

[1, 2, 3] == Cons 1 (Cons 2 (Cons 3 Nil))

Ex. appending two lists

append :: List -> List -> List
append [] ys     = ys
append (x:xs) ys = x:(append xs ys)

append2 :: List -> List -> List
append2 xs []     = xs
append2 xs (y:ys) = append xs:y ys

Trees

Think of lists as unary trees with elements stored in the nodes. What about binary trees?

data Tree = Leaf | Node Int Tree Tree  -- leaves don't store data!

t1234 = Node 1
            (Node 2 (Node 3 Leaf Leaf) Leaf)
            (Node 4 Leaf Leaf)

1 - 2 - 3 - ()
  |   |   \ ()
  |   \ ()
  \ 4 - ()
      \ ()

Functions on Trees

depth :: Tree -> Int
depth Leaf = 0
depth (Node _ l r) = 1 + max (depth l) (depth r)

Ex: Calculator

Let’s implement an arithmetic calculator to eval things like 4.0 + 2.0, 3 - 9, (4.0 + 2.9) * (1.0 + 2.2)

data Expr = Val Float
            | Add Expr Expr
            | Sub Expr Expr
            | Mul Expr Expr

-- evaluate!
eval :: Expr -> Float
eval (Num f)     = f
eval (Add e1 e2) = eval e1 + eval e2
eval (Sub e1 e2) = eval e1 - eval e2
eval (Mul e1 e2) = eval e1 * eval e2

Tail Recursion

Whatever the recursive call returns will be what the expression returns. No computations are allowed on recursively returned values.

-- tail recursive factorial!
facTR :: Int -> Int
facTR n = loop 1 n
    where
        loop :: Int -> Int -> Int
        loop acc n
            | n <= 1    = acc
            | otherwise = loop (acc * n) (n - 1)

--      <facTR 4>
--     <<loop 1 4>>
--    <<<loop 4 3>>>
--   <<<<loop 12 2>>>>
--  <<<<<loop 24 1>>>>>
-- <<<<<<24>>>>>>