ch11.adoc

11 Algebraic datatypes

11.4 Data constructors and values

For data types

link:ch11_11.4_0.hs[role=include]

1. Doggies is type constructor

2. kind of Doggies is * -> *

3. kind of Doggies String is *

4. type of Husky 10 is Num a ⇒ Doggies a

5. type of Husky (10 :: Integer) is Doggies Integer

6. type of Mastiff "Scooby Doo" is Doggies String

7. DogueDeBordeaux is both type and data constructor

8. type of DogueDeBordeaux is doge → DogueDeBordeaux doge

9. type of DogueDeBordeaux "doggie!" is DogueDeBordeaux String

11.5 What’s a type and what’s data?

link:ch11_11.5_0.hs[role=include]

1. type of myCar is Vehicle

2. define functions

   link:ch11_11.5_1.hs[role=include]

3. define function (error on non Car)

   link:ch11_11.5_2.hs[role=include]

4. Plane Airline for getManu error is Non-exhaustive patterns in function getManu. You can add all catching pattern, but it would have to end up in error anyway, as there is no Manufacturer for non-Car value.

5. add size for Plane, can be done similary as Price with Double instead of Integer

   link:ch11_11.5_3.hs[role=include]

11.7 What makes these datatypes algebraic?

Intermission: Exercises

1. cardinality 1 data PugType = PugData

2. cardinality 3

   data Airline =
         PapuAir
       | CatapultsR'Us
       | TakeYourChancesUnited

3. Int16 has cardinality 65535

4. Int is instance of Bounded, therefore cardinality can be determined. Integer does not have bounds

5. Int8 has 256 values, which corresponds to 2 ^ 8 = 256

Simple datatypes with nullary data constructors

data Example = MakeExample deriving Show

1. MakeExample has type Example. :t Example gives error Not in scope: data constructor ‘Example’

2. :i Example shows that it is instance of Show typeclass

3. :t MakeExample gives Int → Example

newtype

type synonym does not work

link:ch11_11.7_0.hs[role=include]

GHC pragma GeneralizedNewtypeDeriving works for tooMany (Goats 45) even without declaring an instance. Reusing Int instance.

link:ch11_11.7_1.hs[role=include]

Intermission: Exercises

1. without newtype

   link:ch11_11.7_2.hs[role=include]

   with newtype

   link:ch11_11.7_3.hs[role=include]

2. TooMany instance for (Int, Int), sum the values

   link:ch11_11.7_4.hs[role=include]

3. TooMany instance for (Num a, TooMany a) ⇒ (a, a)

   Note	TooMany a as class constraint means we know what to do with toomany x. If we use (n + n') > 42 as the implementation, then we get error as there is no Ord for TooMany.

   link:ch11_11.7_5.hs[role=include]

Warning

All of the following breaks. Ambiguous type or could not deduce class constraint.

link:ch11_11.7_6.hs[role=include]

11.8 Sum types

Intermission: Exercises

1. cardinality is 4. Bool is 2 and sum type adds

   data BigSmall =
         Big Bool
       | Small Bool
       deriving (Eq, Show)

2. cardinality is 258. Int8 is 256, Bool is 2, sum type adds. let myNumba = Numba (-128) breaks, details in https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/syntax-extns.html NegativeLiterals. Number out of Int8 range gives error Literal 1000 is out of the Int8 range -128..127 for 1000 :: Int8

   import Data.Int
   
   data NumberOrBool =
         Numba Int8
       | BoolyBool Bool
       deriving (Eq, Show)

11.9 Product types

Intermission: Jammin Exercises

link:ch11_11.9_0.hs[role=include]

11.10 Normal form

link:ch11_11.10_2.hs[role=include]

BookType gone

link:ch11_11.10_3.hs[role=include]

Exercises

this code

link:ch11_11.10_0.hs[role=include]

Garden in normal form

link:ch11_11.10_1.hs[role=include]

11.11 Constructing and deconstructing values

link:ch11_11.11_0.hs[role=include]

11.12 Function type is exponential

Exponentiation in what order?

link:ch11_11.12_0.hs[role=include]

Intermission: Exercises

1. 4 + 4 = 8

   data Quad =
         One
       | Two
       | Three
       | Four
       deriving (Eq, Show)
   eQuad :: Either Quad Quad
   eQuad = ???

2. 4 * 4 = 16

   prodQuad :: (Quad, Quad)

3. 4 ^ 4 = 256

   funcQuad :: Quad -> Quad

4. 2 * 2 * 2 = 16

   prodTBool :: (Bool, Bool, Bool)

5. (2 ^ 2) ^ 2 = 16

   gTwo :: Bool -> Bool -> Bool

6. (4 ^ 4) ^ 2 = 65536

   fTwo :: Bool -> Quad -> Quad

11.15 Binary Tree

Write map for BinaryTree

link:ch11_11.15_0.hs[role=include]

Convert binary trees to lists

Simple solution

link:ch11_11.15_1.hs[role=include]

Eventually cooler and better solution

link:ch11_11.15_1_0.hs[role=include]

Write foldr for BinaryTree

The big shift was to realize that the folding function needs to take 3 arguments, not the usual 2 as seen in folds so far.

link:ch11_11.15_2.hs[role=include]

The book gives this signature foldTree :: (a → b → b) → b → BinaryTree a → b though :/, let’s do as the book says.

link:ch11_11.15_2_0.hs[role=include]

Warning

But this way you cannot recreate the original tree!!!

Rewrite map for BinaryTree

3 parameter fold first

link:ch11_11.15_3.hs[role=include]

2 parameter fold - BROKEN

Warning

as mentioned above, this fold ruines the structure

link:ch11_11.15_3_0.hs[role=include]

11.16 Chapter Exercises

Multiple choice

1. a) Weekday is a type with five data constructors

   data Weekday =
         Monday
       | Tuesday
       | Wednesday
       | Thursday
       | Friday

2. c) type of f Friday = "Miller Time" is f :: Weekday → String

3. b) Types defined with the data keyword must begin with a capital letter

4. c) The function g xs = xs !! (length xs - 1) delivers the final element of xs

Ciphers

Vigenère cipher

link:ch11_11.16_0.hs[role=include]

As-patterns

1. isSubsequenceOf

   link:ch11_11.16_1.hs[role=include]

2. capitalizeWords

   link:ch11_11.16_2.hs[role=include]

Language exercises

Caution

This one was more tricky - review?

link:ch11_11.16_3.hs[role=include]

Phone exercise

Warning

don’t know!

link:ch11_11.16_4.hs[role=include]

Hutton’s Razor

link:ch11_11.16_5.hs[role=include]