2.3 Typeclasses

2.3.1 Defining typeclasses and typeclass instances

A typeclass defines a set of typeclass methods, each named method-id, which are operations that must be implemented by all members of the class. Implementations of typeclass methods must match the provided method-type, with the var-ids replaced by the types the instance is being defined for.

For each method-id, a default method may be provided as default-method-impl-expr, which will be used if any instance opts to not specify an explicit implementation for that method. Each default method implementation must be polymorphic enough to be a valid implementation for any instance of the class. Default methods are generally used when a typeclass method may be defined in terms of other typeclass methods, but the implementor can be given a choice of which methods to implement, or they can provide a more efficient implementation for commonly-used methods.

Each fundep-spec, if provided, declares a functional dependency between parameters of the class, where each determinant-id and dependent-id must be included in the class’s var-ids. A functional dependency introduces a constraint between instances of the class: each combination of the parameters specified by the determinant-ids must uniquely determine the parameters specified by the dependent-ids. For example, given the following class declaration:

(class (C a b c) #:fundeps [[a -> c]])

…then each instance of C with the same type for a must also have the same type for c. For example, these instances would be permitted together:

(instance (C Integer Unit String))

(instance (C Integer Bool String))

…but these instances would not:

(instance (C Integer Unit String))

(instance (C Integer Bool Double))

Restriction of this sort is useful mostly because the knowledge that a class will be used this way allows the typechecker to perform better type inference. Without a functional dependency, use of a typeclass-constrained function requires all of its parameters to be known, but with a functional dependency, the typechecker can solve a typeclass constraint when only a subset of the parameters are known.

If deriving-transformer-expr is provided, it is evaluated in the transformer environment to obtain a deriving transformer for the defined class. A deriving transformer must be a syntax transformer, which will be used to expand uses of derive-instance or data #:deriving clauses that reference the class.

2.3.2 Printing for debugging

value show : {a -> String}

Examples:

> (show 42)

: String "42"

> (show "hello")

: String "\"hello\""

> (show (Just 11))

: String "(Just 11)"

> (show {1 :: 2 :: 3 :: Nil})

: String "{1 :: 2 :: 3 :: Nil}"

2.3.3 Equality

An implementation for at least one of == or /= must be provided. If one is omitted, a default implementation will be provided in terms of the other.

value == : {a -> a -> Bool}

Examples:

> {10 == 10}

: Bool True

> {10 == 11}

: Bool False

> {{1 :: 2 :: Nil} == {1 :: 2 :: Nil}}

: Bool True

> {{1 :: 2 :: Nil} == {1 :: Nil}}

: Bool False

> {{1 :: 2 :: Nil} == {1 :: 3 :: Nil}}

: Bool False

value /= : {a -> a -> Bool}

Examples:

> {10 /= 10}

: Bool False

> {10 /= 11}

: Bool True

> {{1 :: 2 :: Nil} /= {1 :: 2 :: Nil}}

: Bool False

> {{1 :: 2 :: Nil} /= {1 :: Nil}}

: Bool True

> {{1 :: 2 :: Nil} /= {1 :: 3 :: Nil}}

: Bool True

2.3.4 Semigroups and monoids

value ++ : {a -> a -> a}

An associative operation. That is, ++ must obey the following law:

{{a ++ b} ++ c} = {a ++ {b ++ c}}

Examples:

> {"hello" ++ ", " ++ "world!"}

: String "hello, world!"

> {{1 :: 2 :: Nil} ++ {3 :: 4 :: Nil}}

: (List Integer) {1 :: 2 :: 3 :: 4 :: Nil}

value mempty : a

An identity element for ++. That is, mempty must obey the following laws:

{a ++ mempty} = a

{mempty ++ a} = a

Examples:

> (: mempty String)

: String ""

> (: mempty (List Integer))

: (List Integer) Nil

2.3.5 Functors

• The map function can be thought of as applying a function to each “element” of some “container”. This metaphor applies to many members of the Functor typeclass, such as List and Maybe, but does not apply well to all of them.

• More generally, map can be viewed as a “lifting” operation, which “lifts” a function of type {a -> b} to a function of type {(f a) -> (f b)} for some type f. This is a very general notion, and the meaning of such an operation is highly dependent on the particular choice of f.

All map implementations must obey the following laws:

(map id) = id

(map {f . g}) = {(map f) . (map g)}

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

Examples:

> (map (+ 1) {1 :: 2 :: Nil})

: (List Integer) {2 :: 3 :: Nil}

> (map (+ 1) (Just 10))

: (Maybe Integer) (Just 11)

> (map (+ 1) Nothing)

: (Maybe Integer) Nothing

2.3.6 Applicative functors

Applicative functors must satisfy the following laws:

{(pure id) <*> v} = v

{(pure .) <*> u <*> v <*> w} = {u <*> (v <*> w)}

{(pure f) <*> (pure x)} = (pure (f x))

{u <*> (pure y)} = {(pure (& y) <*> u)}

As a consequence of these laws, the Functor instance for f will satisfy:

(map f x) = {(pure f) <*> x}

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

Lifts a value.

Examples:

> (: (pure 11) (Maybe Integer))

: (Maybe Integer) (Just 11)

> (: (pure 11) (List Integer))

: (List Integer) {11 :: Nil}

value <*> : (forall [a b] {(f {a -> b}) -> (f a) -> (f b)})

Applies a function in a context. While map/<$> “lifts” a pure function to a function that operates on a functor, <*> applies a function that is already inside the context of a functor.

Examples:

> {(Just not) <*> (Just True)}

: (Maybe Bool) (Just False)

> {(Just not) <*> (Just False)}

: (Maybe Bool) (Just True)

> {(Just not) <*> Nothing}

: (Maybe Bool) Nothing

> {(: Nothing (Maybe {Bool -> Bool})) <*> (Just True)}

: (Maybe Bool) Nothing

Due to currying, this is especially useful in combination with <$> to apply a multi-argument function to multiple arguments within the context of some functor. For example, Maybe implements a sort of short-circuiting, where any Nothing will cause the entire computation to produce Nothing.

Examples:

> {+ <$> (Just 1) <*> (Just 2)}

: (Maybe Integer) (Just 3)

> {+ <$> Nothing <*> (Just 2)}

: (Maybe Integer) Nothing

> {+ <$> (Just 1) <*> Nothing}

: (Maybe Integer) Nothing

This works because {f <$> x} is guaranteed to be equivalent to {(pure f) <*> x} by the applicative laws, and since functions are curried, each use of <*> applies a single argument to the (potentially partially-applied) function.

2.3.7 Monads

Monads must satisfy the following laws:

{join . pure} = id

{join . (map pure)} = id

{join . join} = {join . (map join)}

The =<< operation is pronounced “bind”, and it is equivalent in power to join. While join is closer to the essence of what a monad is, =<< (or its flipped version, >>=) is more frequently used in ordinary programming. Either may be implemented, and a default implementation will be provided for the other, or an implementation may be provided for both if a more efficient implementation can be provided.

It is often more useful to use do than to use join or =<< directly.

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

Examples:

> (join (Just (Just 3)))

: (Maybe Integer) (Just 3)

> (join (Just (: Nothing (Maybe Integer))))

: (Maybe Integer) Nothing

> (join (: Nothing (Maybe (Maybe Integer))))

: (Maybe Integer) Nothing

> (join {{1 :: Nil} :: {2 :: 3 :: Nil} :: Nil})

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

value =<< : (forall [a b] {{a -> (m b)} -> (m a) -> (m b)})

Applies a function that produces a monadic value to a monadic value. The expression {f =<< x} is equivalent to (join {f <$> x}) (and an explicit implementation of both methods must maintain that law). It is worth comparing and contrasting the types of map/<$>, <*>, and =<<, all of which are similar but slightly different.

Examples:

> {head =<< (tail {1 :: 2 :: Nil})}

: (Maybe Integer) (Just 2)

> {head =<< (tail {1 :: Nil})}

: (Maybe Integer) Nothing

> {head =<< (tail (: Nil (List Integer)))}

: (Maybe Integer) Nothing

The do form is desugared using the following rules:

1. Any use of do with a single subform expands to the subform—(do expr) is equivalent to expr.

2. Each monadic-do-clause introduces a use of >>=, with the result potentially bound to a binding-id. That is, (do [x <- m] more ...+) expands to {ma >>= (λ [x] (do more ...))}, and (do m more ...+) expands to {ma >>= (λ [_] (do more ...))}.

3. Each pure-do-clause produces a local binding form without any uses of >>=, which is useful to create local bindings that are not monadic. (do (let binding-pair ...) more ...+) expands to (let (binding-pair ...) (do more ...)), and (do (letrec binding-pair ...) more ...+) expands to (letrec (binding-pair ...) (do more ...)).

Using do is often much more readable than writing the uses of >>= out by hand, especially when it is helpful to give the result of each action a name.