Type introduction illustrated
for casual haskellers

to get over the Foldable

Takenobu T.
Rev. 0.01.2
WIP

“What is this description ?!”foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

NOTE
- This document shows one of the mental model.
- Please see also references.
- This is written for Haskell, especially ghc7.10/8.0 and later.

Contents
1. Introduction- Values, Types, Type classes- Polymorphic types- Type constructors- Polymorphic and type constructors
2. more, Types and Type classes- Function types- Type class operations
3. What is this?

Appendix I – Various types- Bool, Char, Int, Float- Maybe, List, Either, Tuple
Appendix II – Various type classes- Eq, Ord
- Num
- Foldable- Functor, Applicative, Monad- Monoid- Traversable
Appendix III – Advanced topics
References

1. Introduction

1. Introduction

Values, Types, Type classes

Values‘a’False

1.0

12

‘h’
1.5

‘5’

True
700

3.14

References : [B2] Ch.2, [B3] Ch.2

Types“Bool” type“Int” type
1

False
True

2

“Float” type

“Char” type

1.0

‘a’

1.5

700

3.14...

...

‘h’‘5’...

A type is a collection of values which have common property.

References : [B2] Ch.2, [B3] Ch.2, [B1] Ch.2, [D2], [B5] Ch.8, [H1] Ch.4

Type classes“Num” type class
BoolInt
1

False
True

Float

2

1.0

1.5

700

3.14...

...

Char‘a’...

‘h’‘5’...

A type class is a collection of types which have common operations.

References : [B1] Ch.2, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6, [H1] Ch.4

1. Introduction

Polymorphic types

Proper types

BoolPropertypes

Int
1FalseTrueFloat

2

1.0

1.5

700

3.14...

...

Char‘a’‘h’‘z’...

References : [B1] Ch.2, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

Polymorphic types
aPolymorphic
types

Parametric polymorphism...

BoolPropertypes

Int
1False
True

Float

2

1.0

1.57003.14...

...

Char‘a’‘h’‘z’...

References : [B1] Ch.7, [B3] Ch.3, [B4] Ch.6, [D1] Week 2, [H1] Ch.4

Polymorphic types restricted with type classes
Num a => aPolymorphic
types

limited with the type class
...

Bool

Propertypes

Int
1

False
TrueFloat2

1.0

1.5

700

3.14...

...

Char‘a’...

‘h’‘z’...

Num type class
References : [B1] Ch.2, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6, [D1] Week 4

Polymorphic types
aPolymorphic
types

polymorphic
typeswith type class

Propertypes

Num a => aInt

References : [B1] Ch.2, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6, [D1] Week 2, 4

1. Introduction

Type constructors

Type constructors

nullary type constructor

Int

References : [B1] Ch.7

Type constructors

unary type constructor

Maybe Int

“Maybe” type constructor takes one type argument (unary).

References : [B1] Ch.7

Type constructors

nullaryunaryInt

Maybe Int

Either Int Char(,,) Int Int Float

Float

IO IntState Int Char:Int -> Bool[] Int(,) Int Char:binary[ Int ]
Syntactic sugar(Int, Char)
Syntactic sugar

::

3-ary

...

References : [B1] Ch.7, [H1] Ch.4

1. Introduction

Polymorphic types and type constructors

Polymorphic types and type constructors

aPolymorphictypes?

IntMaybe Int

Type constructors
References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

Polymorphic types and type constructors

aPolymorphictypes

t aMaybe aInt

Maybe Int

Type constructors
References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

Polymorphic types and type constructors
t a...

Maybe aPolymorphic
types[] aTree a

IO a...

References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

Polymorphic types and type constructors
Maybe aPolymorphictypes...

Maybe Int

Propertypes

Maybe Char

Maybe Float

Maybe Bool...

References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

Polymorphic types and type constructors
anullaryunarybinary

3-aryt at a bt a b c

Polymorphictypes...
Propertypes

...

...

IntMaybe Int

Either Int CharFloat[] Int(,) Int CharInt -> BoolIO IntState Int Char:::...
(,,) Int Int Float:

References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6...

2. more, Types and Type classes

2. more, Types and Type classes

Function types

Function typeInt

fun :: Int -> BoolBool

fun

The “->” represents the function type.

References : [B2] Ch.2, [B1] Ch.5, [B3] Ch.7, [B5] Ch.9, [H1] Ch.4

Function type with multiple arguments
equivalent tof :: Int -> (Float -> Bool)Int

fun :: Int -> Float -> Bool
Bool
funFloatInt
fun :: Int -> Float -> Char -> Bool
Float

Bool
fun

Char

References : [B2] Ch.2, [B1] Ch.5, [B3] Ch.7

Function type with same typeInt

fun :: Int -> Int -> Int
fun

References : [B2] Ch.2, [B1] Ch.5, [B3] Ch.7

Function type with function as argument

Int -> IntInt -> Int

fun :: (Int -> Int) -> Int -> Bool

BoolfunInt

References : [B2] Ch.2, [B1] Ch.5, [B3] Ch.7

Function type with function as resultInt

fun :: Int -> (Int -> Int)fun

Int -> IntInt -> Int

References : [B2] Ch.2, [B1] Ch.5, [B3] Ch.7

Function type with polymorphic function

afun :: a -> Bool

Bool

funPolymorphic
types

Parametric polymorphism...

Propertypes

Intfun :: Int -> Bool
funBoolChar

fun :: Char -> Bool

Bool

fun

References : [B2] Ch.2, [B1] Ch.5, [B3] Ch.7

Function type for polymorphic function with type classafun :: Num a => a -> Bool

Bool

fun
Polymorphictypes

limited with the type class...

Propertypes

Intfun :: Int -> Boolfun...

Bool

Char

fun :: Char -> Bool

Bool

fun

References : [B2] Ch.2, [B1] Ch.5, [B3] Ch.7

2. more, Types and Type classes

Type class operations

A type class has the class operations

Class a => aclass operations(class methods / common operations)?

References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

A type class has the class operations

Eq a => aEq a => a -> a -> Bool

Bool

==

Eq class has “==“ (equality) operation.

References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

A type class has the class operations

aEq a => a -> a -> Bool

Bool

==
Polymorphictypes

Ad-hoc polymorphism (overloading)...

Propertypes
Int

Int -> Int -> Bool
==

Bool

Char

Char -> Char -> Bool

Bool

==

Each type, that belongs to the type class, must be support the overloaded operations.
References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

Declaration of a type class and instancesclass Eq a where(==) :: a -> a -> BoolaEq a => a -> a -> Bool

Bool==Polymorphictypes...

Propertypes
IntInt -> Int -> Bool

Bool

CharChar -> Char -> Bool====

instance Eq Int where(==) = eqInt

instance Eq Char where(==) = ...

Bool

References : [B1] Ch.2, 7, [B2] Ch.2, [B3] Ch.3, [B4] Ch.6

3. What is this?

What is this ?!

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bfoldr = ...

？

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

What is this ?!
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bb

Foldable t => t afoldra -> b -> babb

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

What is this ?!
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bb

Foldable t => t afoldra -> b -> babb

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

What is this ?!
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bb

Foldable t => t afoldra -> b -> babb

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

What is this ?!
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bb

Foldable t => t afoldra -> b -> babb

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

What is this ?!
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bb

Foldable t => t afoldra -> b -> babb

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

What is this ?!
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bb

Foldable t => t afoldra -> b -> babb

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

What is this ?!
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bb

Foldable t => t afoldra -> b -> babb

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

Example of polymorphism on foldrb

Foldable t => t afoldra -> b -> b

Polymorphictypes

...

bb[a]

Tree afoldra -> b -> bfoldra -> b -> b

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

Example of polymorphism on foldrb[a]foldra -> b -> bPolymorphictypes

Propertypes...

IntInt[Char][Int]
foldr

foldr
exampleChar -> Char -> IntInt -> Int -> Int

foldr (+) 0 [1, 2, 3]
foldr (*) 1 [1, 2, 3]
foldr max 0 [1, 2, 3]:

References : [B1] Ch.12, 5, 7, [B2] Ch.6, 2, [B3] Ch.7, 3, [B4] Ch.4, 6

Appendix I – Various types

Bool, Char, Int, Float types

BoolChar‘a’False
True‘h’‘z’...

Int1

Float

2

1.0

1.57003.14...

...

References : [B2] Ch.2, [B3] Ch.2, [B1] Ch.2, [H1] Ch.6, [S1]

Maybe typeMaybe aPolymorphictypes...

Maybe Bool

Propertypes

Nothing

Just True
Just False

Maybe Int

Maybe Float

Maybe Char

Nothing

Nothing

Nothing

Just 1.0
Just 1.5

Just ‘a’Just 3.14...

Just ‘z’...

Just 1
Just 2Just 700...

Just ‘h’

References : [B1] Ch.7, [S1]

List type
Syntactic sugar[a][] a

Polymorphictypes...

[ Bool ][ Int ]

[ Float ][ Char ]

[]

[]

[]

[]

Propertypes[True][True, False]...

[1][1, 2][700, ..]
...

[1.0]
[1.5, 20.0][3.14]
...

[‘a’]

[‘h’]

[‘a’, ‘b’, ‘c’]...

References : [B1] Ch.1, [B2] Ch.4, [B3] Ch.3, [H1] Ch.6, [S1]

Either type
Either a b

Polymorphictypes...

Either Bool Int

Propertypes

Left True
Left False
Right 7...

Either Char Int
Left ‘a’
Right 2Right 700...

Either Int Float
Left 1
Right 1.5
Right 3.14...

Either Float Char
Left 1.0
Left 20.0
Right ‘z’...

References : [B1] Ch.7, [S1]

Tuple (pair) type
Syntactic sugar(a, b)(,) a bPolymorphictypes...

(Bool, Int)

Propertypes(True, 1)(False, 7)(True, 10)...

(Char, Int)

(Int, Float)(‘a’, 2)

(1, 1.0)(‘b’, 5)(‘z’, 700)...

(5, 1.5)(100, 3.14)...

(Float, Char)(1.0, ‘A’)
(20.0, ‘b’)
(3.14, ‘z’)...

References : [B1] Ch.1, [B2] Ch.2, [B3] Ch.3, [H1] Ch.6, [S1]Appendix II – Various type classes

Eq class‘s characteristic operationsEq a => a

Bool

==/=

The Eq class has equality operations.

References : [B1] Ch.1, [B2] Ch.2, [B3] Ch.3, [H1] Ch.6, [S1]

Ord class‘s characteristic operations
Ord a => aBool<<=>>=The Ord class has comparison operations.

References : [B1] Ch.1, [B2] Ch.2, [B3] Ch.3, [H1] Ch.6, [S1]Num class‘s characteristic operations
Num a => a+-*abs

The Num class has arithmetic operations.

References : [B1] Ch.1, [B2] Ch.2, [B3] Ch.3, [H1] Ch.6, [S1]

Foldable class‘s characteristic operationsb

Foldable t => t afoldra -> b -> b

References : [B1] Ch.12, [B2] Ch.6, [B3] Ch.7, [D3], [S1]

Functor class‘s characteristic operations

exampleFunctor f => f a

Functor f => f b[] bMaybe bTree bIO b:

fmap :: Functor f => (a -> b) -> f a -> f b

fmapa -> b

References : [B1] Ch.7, [D3], [H1] Ch.6, [S1]Applicative class‘s characteristic operations
apure

Applicative f => f a

Applicative f => f b<*>

Applicative f => f (a -> b)

References : [B1] Ch.11, [D3], [S1]

Monad class‘s characteristic operationsareturn

Monad m => m a

Monad m => m b>>=

Monad m => a -> m b

References : [B1] Ch.12, [B2] Ch.10, [D3], [H1] Ch.6, [S1]

Monoid class‘s characteristic operations

Monoid a => amappendmemptyReferences : [B1] Ch.12, [D3], [S1]

Related topics: monoid laws
Monoid a => amappendbinary operation

Monoid a => amemptymappendunit law

Monoid a => amappendmappendmappendmappendassociative lawsameProgrammers should satisfy the monoid laws.
References : [B1] Ch.12, [D3], [S1]

Traversable class‘s characteristic operations

Traversable t => t a

Traversable t => f (t b)traversea -> f b

References : [D3], [S1]Appendix III – Advanced topics

Universally quantified types
aforall a . aimplicitly quantified with
universal quantification (∀a .)Polymorphic
types

...

Bool

Propertypes

Int
1

False
True

Float

2

1.0

1.5

700

3.14...

...

Char‘a’‘h’‘z’...

References : [B5] Ch.23, [H1] Ch.4, [H2] “GHC Language Features”Kinds and type constructors

nullaryunarykind

binary3-ary...

kindkind

Maybe :: * -> *Either :: * -> * -> *(,,) :: * -> * -> * -> *Int :: *Maybe Int :: *Either Int Char :: *(,,) Int Int Float :: *Int

Maybe Int

Either Int CharFloat

IO IntState Int CharInt -> Bool[] Int(,) Int Charkind(,,) Int Int Float

References : [B1] Ch.7, [B5] Ch.29, [H1] Ch.4

Type systems
TAPL [5] Ch.23

corresponding to System F

TAPL [5] Ch.29

corresponding to System FωaPolymorphictypest a(Quantifiedtypes)

Maybe aInt

Maybe IntTAPL [5] Ch.30

corresponding to λωType constructors(Type operators)
References : [B5] Ch.23, 29, 30

ReferencesReferences
Books
[B1]

Learn You a Haskell for Great Good! (LYAH)
http://learnyouahaskell.com/[B2] Thinking Functionally with Haskell(IFPH 3rd edition)
http://www.cs.ox.ac.uk/publications/books/functional/[B3] Programming in Haskell
http://www.cs.nott.ac.uk/~pszgmh/book.html[B4] Real World Haskell (RWH)
http://book.realworldhaskell.org/[B5] Types and Programming Languages(TAPL)
https://mitpress.mit.edu/books/types-and-programming-languages

Documents[D1]

CIS 194: Introduction to Haskell
http://www.seas.upenn.edu/~cis194/lectures.html[D2] Type Systems
http://dev.stephendiehl.com/fun/004_type_systems.html[D3] Typeclassopedia
http://www.cs.tufts.edu/comp/150FP/archive/brent-yorgey/tc.pdf
https://wiki.haskell.org/Typeclassopedia

References
Search[S1]

Hooglehttps://www.haskell.org/hoogle

Specifications[H1] Haskell 2010 Language Reporthttps://www.haskell.org/definition/haskell2010.pdf[H2] The Glorious Glasgow Haskell Compilation System (GHC user’s guide)
https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/index.html
https://downloads.haskell.org/~ghc/latest/docs/users_guide.pdf

References
Furthermore readings[A1]

What I Wish I Knew When Learning Haskell
http://dev.stephendiehl.com/hask/[A2] How to learn Haskell
https://github.com/bitemyapp/learnhaskell[A3] Documentation
https://www.haskell.org/documentation[A4] A Haskell Implementation Reading List
http://www.stephendiehl.com/posts/essential_compilers.html[A5] The GHC reading list
https://ghc.haskell.org/trac/ghc/wiki/ReadingList