2.2 Datatypes

2.2.1 Defining algebraic datatypes

syntax
(data type-clause data-clause ...
maybe-deriving)

type-clause = type-id
| (type-constructor-id param-id ...+) maybe-fixity-ann
| {param-id type-constructor-id param-id} maybe-fixity-ann

data-clause = value-id
| (data-constructor-id arg-type ...+) maybe-fixity-ann
| {arg-type data-constructor-id arg-type} maybe-fixity-ann

maybe-fixity-ann = #:fixity fixity
|

fixity = left
| right

maybe-deriving = #:deriving [class-id ...]
|

Defines a new algebraic datatype. The defined type is distinct from all other types, whether or not they have the same shape or name.

If type-clause is a bare type-id, then type-id is defined and bound directly to the freshly defined type. Alternatively, type-constructor-id may be provided, which binds type-constructor-id to a type constructor that accepts the same number of arguments as param-ids are provided and constructs the freshly defined type when fully saturated.

The fresh type is only inhabited by the values defined and produced by the specified data-clauses. Specifically, each value-id is bound to a unique value of the newly defined type. Similarly, each data-constructor-id is bound to a function that accepts arguments with types arg-types and constructs a value of the newly defined type that contains the provided values.

Examples:

> (data Foo
    (Foo1 Integer Bool)
    (Foo2 String)
    Foo3
    #:deriving [Show])
> (#:type Foo1)
: {Integer -> Bool -> Foo}
> (Foo1 42 True)
: Foo
(Foo1 42 True)
> (#:type Foo2)
: {String -> Foo}
> (Foo2 "hello")
: Foo
(Foo2 "hello")
> Foo3
: Foo
Foo3

Additionally, the bound value-ids and data-constructor-ids serve as patterns that match against different values of the defined type. The pattern associated with each data-constuctor-id accepts patterns that match against the contained values, so pattern-matching allows extracting values stored “inside” data constructors.

Example:

> (case (Foo1 42 True)
    [(Foo1 n _) n]
    [(Foo2 _)   2]
    [Foo3       3])
: Integer
42

If #:deriving is provided, a typeclass instance on the defined type is derived for each of the typeclasses bound to each class-id using its deriving transformer. Specifically, for each class-id, a derive-instance form of the shape (derive-instance class-id type-id) is generated.

Like def, data supports operator fixity annotations. Each fixity specified controls the fixity used by the associated type-constructor-id or value-constructor-id when used as an infix operator.

Examples:

> (data (Tree a)
    {(Tree a) :&: (Tree a)} #:fixity right
    (Leaf a))
> (instance (forall [a] (Show a) => (Show (Tree a)))
    [show (λ* [[{a :&: b}] {"{" ++ (show a) ++ " :&: " ++ (show b) ++ "}"}]
              [[(Leaf a)] {"(Leaf " ++ (show a) ++ ")"}])])
> {(Leaf 1) :&: (Leaf 2) :&: (Leaf 3)}
: (Tree Integer)
{(Leaf 1) :&: {(Leaf 2) :&: (Leaf 3)}}

2.2.2 Defining type aliases

syntax
(type type-clause maybe-fixity-ann type-expr)

type-clause = name-id
| (name-id param-id ...+)

maybe-fixity-ann = #:fixity fixity
|

fixity = left
| right

Defines a type alias named name-id. Uses of name-id are equivalent to uses of the type specified in type-expr. If type-clause is a bare name-id, then name-id is bound directly to the type alias.

Examples:

> (type Num Double)
> (def n : Num 1.5)
> (#:type n)
: Double

If param-ids are specified, then uses of the type alias must supply as many arguments as there are param-ids. The arguments are supplied like those to a type constructor—i.e. (name-id type-argument ...)—and the resulting type is type-expr with each param-id substituted with the corresponding type-argument.

Examples:

> (type (Predicate a) {a -> Bool})
> (def zero? : (Predicate Integer) (== 0))
> (#:type zero?)
: {Integer -> Bool}
> (zero? 0)
: Bool
True
> ((: zero? (Predicate Integer)) 0)
: Bool
True

Though the application of a type alias is syntactically similar to the application of a type constructor, type aliases are effectively type-level macros, and they may not be partially applied. All uses of a type alias must be fully saturated.

Example:

> (: zero? Predicate)
eval:382.23: Predicate: expected 1 argument(s) to type alias
at: Predicate
in: Predicate

2.2.3 Numbers

syntax
Integer

The type of arbitrary-precision integers. Just as with numbers in #lang racket, integers will be represented as fixnums, machine integers, where possible. Values that exceed this range will automatically be promoted to arbitrary-precision “bignums”.

value
+ : {Integer -> Integer -> Integer}
value
- : {Integer -> Integer -> Integer}
value
* : {Integer -> Integer -> Integer}

These functions provide simple, arbitrary-precision, integral arithmetic.

value
> : {Integer -> Integer -> Bool}
value
< : {Integer -> Integer -> Bool}
value
>= : {Integer -> Integer -> Bool}
value
<= : {Integer -> Integer -> Bool}

Comparison operators on integers.

syntax
Double

The type of double-precision IEEE 754 floating-point numbers, known as flonums in #lang racket.

value
d+ : {Double -> Double -> Double}
value
d- : {Double -> Double -> Double}
value
d* : {Double -> Double -> Double}
value
d/ : {Double -> Double -> Double}

These functions provide simple, floating-point arithmentic on Doubles.

2.2.4 Strings

syntax
String

The type of strings, which can be constructed using string literals.

value
string-length : {String -> Integer}

Returns the length of a string, in characters.

Examples:

> (string-length "hello")
: Integer
5
> (string-length "Λάμβδα")
: Integer
6

value
string-split : {String -> String -> (List String)}

Splits a string on all instances of a separator string.

Examples:

> (string-split "," "1,2,3,4,5")
: (List String)
{"1" :: "2" :: "3" :: "4" :: "5" :: Nil}
> (string-split "," ",2,,4,")
: (List String)
{"" :: "2" :: "" :: "4" :: "" :: Nil}
> (string-split "," ",,,,")
: (List String)
{"" :: "" :: "" :: "" :: "" :: Nil}

value
string->bytes/utf-8 : {String -> Bytes}

Encodes a string using UTF-8.

Example:

> (string->bytes/utf-8 "αβγδ")
: Bytes
#"\316\261\316\262\316\263\316\264"

2.2.5 Bytes

syntax
Bytes

The type of byte strings, a fixed-length array of bytes. Byte strings can be constructed with byte string literals.

value
bytes-length : {Bytes -> Bytes}

Returns the length of a byte string.

Examples:

> (bytes-length #"abcd")
: Integer
4
> (bytes-length (string->bytes/utf-8 "αβγδ"))
: Integer
8

value
bytes->string/utf-8 : {Bytes -> (Maybe String)}

Attempts to decode a string using UTF-8.

Examples:

> (bytes->string/utf-8 #"\316\261\316\262\316\263\316\264")
: (Maybe String)
(Just "αβγδ")
> (bytes->string/utf-8 #"\303(")
: (Maybe String)
Nothing

2.2.6 Functions

syntax
(-> a b)

A type constructor of arity 2 that represents functions, where a is the type of value the function accepts as an argument, and b is the type of the result. Functions of higher arities are represented via currying.

value
id : (forall [a] {a -> a})

The identity function. Returns its argument unchanged.

value
const : (forall [a b] {a -> b -> a})

Accepts two arguments and returns the first, ignoring the second.

Examples:

> (const "hello" "goodbye")
: String
"hello"
> (const Unit (error! "never gets here"))
: Unit
Unit

value
|.| : (forall [a b c] {{b -> c} -> {a -> b} -> {a -> c}})

Function composition. Given two functions f and g, then ({f . g} x) is equivalent to (f (g x)).

Examples:

> (def add1AndDouble {(* 2) . (+ 1)})
> (add1AndDouble 3)
: Integer
8

value
$ : (forall [a b] {{a -> b} -> a -> b})

Function application as a binary operator. Not especially useful, since {f $ x} is equivalent to (f x), but sometimes convenient when used higher-order.

value
& : (forall [a b] {a -> {a -> b} -> b})

Reverse function application. This function is a flipped version of $ that accepts the argument first and the function second.

value
flip : (forall [a b c] {{a -> b -> c} -> b -> a -> c})

Produces a function with the same behavior as another function, but with its first two arguments flipped.

Example:

> (flip :: Nil 3)
: (List Integer)
{3 :: Nil}

2.2.7 Quantification and Constrained Types

syntax
(forall [var-id ...+] type)
(forall [var-id ...+] constraint ...+ => type)
syntax
(∀ [var-id ...+] type)
(∀ [var-id ...+] constraint ...+ => type)

Universal quantification over types. Within type, each var-id is bound to a fresh, universally quantified type.

The second form is a shorthand that provides a nicer syntax for types constructed with => nested immediately within forall: (forall [var-id ...] constraint ... => type) is precisely equivalent to (forall [var-id ...] (=> [constraint ...] type)).

syntax
(=> [constraint ...+] type)

Builds a type that includes typeclass constraints. The resulting type is equivalent to type, with the requirement that each constraint must hold.

2.2.8 Unit

datatype
(data Unit
Unit)

The unit type. Values of type Unit only have one possible value (ignoring bottom), Unit. A value of type Unit carries no information, so it is similar to #<void> in #lang racket or the void return “type” in many C-like languages.

2.2.9 Booleans

datatype
(data Bool
True
False)

The boolean type, representing two binary states.

value
not : {Bool -> Bool}

Inverts the boolean it is applied to; that is, produces False when given True and produces True when given False.

value
if : (forall [a] {Bool -> a -> a -> a})

Performs case analysis on a boolean value. If the supplied boolean is True, returns its second argument; otherwise, returns its third argument.

Since Hackett is lazy, if is an ordinary function, not a macro or special form, and it can be used higher-order if desired.

Examples:

> (if True "first" "second")
: String
"first"
> (if False "first" "second")
: String
"second"

value
\|\| : {Bool -> Bool -> Bool}

Returns True if its first argument is True; otherwise, returns its second argument. Notably, the second argument will not be evaluated at all if the first argument is True, but the first argument will always be forced when the result is forced.

Examples:

> {True || True}
: Bool
True
> {False || True}
: Bool
True
> {True || False}
: Bool
True
> {False || False}
: Bool
False
> {True || (error! "never gets here")}
: Bool
True

value
&& : {Bool -> Bool -> Bool}

Returns False if its first argument is False; otherwise, returns its second argument. Notably, the second argument will not be evaluated at all if the first argument is False, but the first argument will always be forced when the result is forced.

Examples:

> {True && True}
: Bool
True
> {False && True}
: Bool
False
> {True && False}
: Bool
False
> {False && False}
: Bool
False
> {False && (error! "never gets here")}
: Bool
False

2.2.10 The Identity Type

(require hackett/data/identity)

package: hackett-lib

datatype
(data (Identity a)
(Identity a))

A simple wrapper type with a variety of typeclass instances that defer to the value inside whenever possible. Most useful for its Functor, Applicative, and Monad instances, which simply apply functions to the value inside the Identity wrapper, making it serve as a “no-op” wrapper of sorts.

> (Identity 5)
: (Identity Integer)
(Identity 5)
> (map (+ 1) (Identity 5))
: (Identity Integer)
(Identity 6)
> {(Identity (+ 1)) <*> (Identity 5)}
: (Identity Integer)
(Identity 6)
> {(Identity "hello, ") ++ (Identity "world")}
: (Identity String)
(Identity "hello, world")

procedure
(run-identity x) → a
x : (Identity a)

Unwraps and returns the value inside an Identity wrapper.

> (run-identity (Identity 5))
: Integer
5

2.2.11 Tuples

datatype
(data (Tuple a b)
(Tuple a b))

The tuple type, which contains a pair of possibly heterogenous values.

value
fst : (forall [a b] {(Tuple a b) -> a})

Extracts the first element of a tuple.

Example:

> (fst (Tuple 42 "hello"))
: Integer
42

value
snd : (forall [a b] {(Tuple a b) -> b})

Extracts the second element of a tuple.

Example:

> (snd (Tuple 42 "hello"))
: String
"hello"

2.2.12 Optionals

datatype
(data (Maybe a)
(Just a)
Nothing)

A type that encodes the notion of an optional or nullable value. A value of type (Maybe a) implies that it might contain a value of type a, but it also might contain nothing at all. This type is usually used to represent operations that can fail (where Nothing represents failure) or values that are not required to be present.

Examples:

> (map (+ 1) (Just 5))
: (Maybe Integer)
(Just 6)
> (map (+ 1) Nothing)
: (Maybe Integer)
Nothing

procedure
(maybe v f x) → b
  v : b
  f : {a -> b}
  x : (Maybe a)

The catamorphism for Maybe. Produces v when x is Nothing and produces (f y) when x is (Just y).

Examples:

> (maybe 0 (+ 1) (Just 5))
: Integer
6
> (maybe 0 (+ 1) Nothing)
: Integer
0

procedure
(from-maybe v x) → a
v : a
x : (Maybe a)

Extracts the value inside x, producing a default value v when x is Nothing. Equivalent to (maybe v id).

Examples:

> (from-maybe 0 (Just 5))
: Integer
5
> (from-maybe 0 Nothing)
: Integer
0

datatype
(data (Either a b)
(Left a)
(Right b))

A type that encodes the notion of a successful result or an error. The Functor, Applicative, and Monad instances for (Either a) are “right-biased”, so they will short-circuit on values wrapped in Left and will perform mapping or sequencing on values wrapped in Right.

This type is generally used in a similar way to Maybe, but it allows the sort of failure to be explicitly tagged, usually returning a error message or failure reason on the Left side.

Examples:

> (map (+ 1) (: (Right 5) (Either String Integer)))
: (Either String Integer)
(Right 6)
> (map (+ 1) (: (Left "an error happened") (Either String Integer)))
: (Either String Integer)
(Left "an error happened")

procedure
(either f g x) → c
  f : {a -> c}
  g : {b -> c}
  x : (Either a b)

The catamorphism for Either. Produces (f y) when x is (Left y) and produces (g z) when x is (Right z).

Examples:

> (either (+ 1) (* 2) (Left 5))
: Integer
6
> (either (+ 1) (* 2) (Right 5))
: Integer
10

procedure
(is-left e) → Bool
e : (Either a b)

This predicate is True when e is of the form (Left x) for some x, and is False when e is (Right x).

Examples:

> (is-left (Left "nifty"))
: Bool
True
> (is-left (Right "tubular"))
: Bool
False

procedure
(is-right e) → Bool
e : (Either a b)

This predicate is True when e is of the form (Right x) for some x, and is False when e is (Left x).

Examples:

> (is-right (Left "nifty"))
: Bool
False
> (is-right (Right "tubular"))
: Bool
True

procedure
(lefts es) → (List a)
es : (List (Either a b))

Extract all values of the form (Left x) from es.

Example:

> (lefts {(Left 1) :: (Right "haskell") :: (Right "racket") :: (Left -32) :: Nil})
: (List Integer)
{1 :: -32 :: Nil}

procedure
(rights es) → (List b)
es : (List (Either a b))

Extract all values of the form (Right x) from es.

Example:

> (rights {(Left 1) :: (Right "haskell") :: (Right "racket") :: (Left -32) :: Nil})
: (List String)
{"haskell" :: "racket" :: Nil}

procedure
(partition-eithers es) → (Tuple (List a) (List b))
es : (List (Either a b))

Extract every (Left x) to the first element of the pair and each (Right x) to the second. (partition-eithers es) is equivalent to (Tuple (lefts es) (rights es))

Example:

> (partition-eithers {(Left 1) :: (Right "haskell") :: (Right "racket") :: (Left -32) :: Nil})
: (Tuple (List Integer) (List String))
(Tuple {1 :: -32 :: Nil} {"haskell" :: "racket" :: Nil})

2.2.13 Lists

datatype
(data (List a)
(:: a (List a))
Nil)

The list type, which describes lazy linked lists. Since a list is lazy, it may be infinite, as long as the entire list is never demanded. The :: constructor is pronounced “cons”, and it is generally intended to be used infix.

syntax
(List element ...)

Produces a list containing each element in order.

Example:

> (List 1 2 6 12 60)
: (List Integer)
{1 :: 2 :: 6 :: 12 :: 60 :: Nil}

List can also be used as a pattern:

Example:

> (case {1 :: 4 :: 9 :: Nil}
[(List _ x _) (Just x)]
[_ Nothing])
: (Maybe Integer)
(Just 4)

value
head : (forall [a] {(List a) -> (Maybe a)})

Returns Just the first element of a list, or Nothing if the list is Nil.

Examples:

> (head {1 :: 2 :: 3 :: Nil})
: (Maybe Integer)
(Just 1)
> (head (: Nil (List Integer)))
: (Maybe Integer)
Nothing

value
tail : (forall [a] {(List a) -> (Maybe (List a))})

Returns Just a list without its first element, or Nothing if the list is Nil.

Examples:

> (tail {1 :: 2 :: 3 :: Nil})
: (Maybe (List Integer))
(Just {2 :: 3 :: Nil})
> (tail (: Nil (List Integer)))
: (Maybe (List Integer))
Nothing

value
head! : (forall [a] {(List a) -> a})

A partial version of head that returns the first element of a list. If the list is empty, it raises an error.

Examples:

> (head! {1 :: 2 :: 3 :: Nil})
: Integer
1
> (head! (: Nil (List Integer)))
head!: empty list

value
tail! : (forall [a] {(List a) -> (List a)})

A partial version of tail that returns a list without its first element. If the list is empty, it raises an error.

Examples:

> (tail! {1 :: 2 :: 3 :: Nil})
: (List Integer)
{2 :: 3 :: Nil}
> (tail! (: Nil (List Integer)))
tail!: empty list

procedure
(take n xs) → (List a)
n : Integer
xs : (List a)

Produces a list with the first n elements of xs. If xs contains fewer than n elements, xs is returned unmodified.

Examples:

> (take 2 {1 :: 2 :: 3 :: Nil})
: (List Integer)
{1 :: 2 :: Nil}
> (take 2 {1 :: Nil})
: (List Integer)
{1 :: Nil}

procedure
(drop n xs) → (List a)
n : Integer
xs : (List a)

Produces a list like xs without its first n elements. If xs contains fewer then n elements, the result is Nil.

Examples:

> (drop 2 {1 :: 2 :: 3 :: Nil})
: (List Integer)
{3 :: Nil}
> (drop 2 {1 :: Nil})
: (List Integer)
Nil

procedure
(filter f xs) → (List a)
f : {a -> Bool}
xs : (List a)

Produces a list that contains each element, x, for which x is an element of xs and (f x) is True.

Example:

> (filter (λ [x] {x > 5}) {3 :: 7 :: 2 :: 9 :: 12 :: 4 :: Nil})
: (List Integer)
{7 :: 9 :: 12 :: Nil}

procedure
(foldr f acc xs) → b
  f : {a -> b -> b}
  acc : b
  xs : (List a)

Reduces xs to a single value using a right-associative binary operator, f, using acc as a “seed” element. Uses of foldr can be thought of as a series of nested, right-associative applications of f, so if xs contains elements named x0, x1, x2 etc., up to xn, then (foldr f acc xs) is equivalent to the following expression:

{x0 f {x1 f {x2 f .... {xn f acc} ....}}}

Examples:

> (foldr + 0 {1 :: 2 :: 3 :: 4 :: 5 :: Nil})
: Integer
15
> (foldr * 1 {1 :: 2 :: 3 :: 4 :: 5 :: Nil})
: Integer
120
> (foldr - 0 {1 :: 2 :: 3 :: 4 :: 5 :: Nil})
: Integer
3
> (foldr :: Nil {1 :: 2 :: 3 :: 4 :: 5 :: Nil})
: (List Integer)
{1 :: 2 :: 3 :: 4 :: 5 :: Nil}

procedure
(foldl f acc xs) → b
  f : {b -> a -> b}
  acc : b
  xs : (List a)

Reduces xs to a single value using a left-associative binary operator, f, using acc as a “seed” element. Uses of foldr can be thought of as a series of nested, left-associative applications of f, so if xs contains elements named x0, x1, x2 etc., up to xn, then (foldr f acc xs) is equivalent to the following expression:

{.... {{{acc f x0} f x1} f x2} .... xn}

Examples:

> (foldl + 0 {1 :: 2 :: 3 :: 4 :: 5 :: Nil})
: Integer
15
> (foldl * 1 {1 :: 2 :: 3 :: 4 :: 5 :: Nil})
: Integer
120
> (foldl - 0 {1 :: 2 :: 3 :: 4 :: 5 :: Nil})
: Integer
-15

procedure
(sum xs) → Integer
xs : (List Integer)

Adds the elements of xs together and returns the sum. Equivalent to (foldl + 0).

Examples:

> (sum {1 :: 2 :: 3 :: Nil})
: Integer
6
> (sum Nil)
: Integer
0

← prev up next →

2.1	Core Syntactic Forms
2.2	Datatypes
2.3	Typeclasses
2.4	I/ O
2.5	Monad Transformers
2.6	Controlling Evaluation

2.2.1	Defining algebraic datatypes
2.2.2	Defining type aliases
2.2.3	Numbers
2.2.4	Strings
2.2.5	Bytes
2.2.6	Functions
2.2.7	Quantification and Constrained Types
2.2.8	Unit
2.2.9	Booleans
2.2.10	The Identity Type
2.2.11	Tuples
2.2.12	Optionals
2.2.13	Lists