May 7, 2016

Beginner's Thought on PureScript Type Classes

tldr; A Monoid is a container that supports an append operation, that is you can add new elements to the container. It also supports the idea of an "empty container" that you can add new elements to. Monoids can be thought of as accumulators of values - a general purpose structure that a function can store values in without knowing the internal details of the Monoid.

An instance of a Monoid type class must implement the mempty and append functions. The requirement to implement append is because the Monoid's superclass is Semigroup, which requires an implementation of append.

These are mempty and append's type signatures...

import Prelude
import Data.Monoid

:type mempty
forall m. (Monoid m) => m

:type append
forall a. (Semigroup a) => a -> a -> a

Two simple examples of Monoid types are String and Array.

So the mempty function returns the empty value for a particular Monoid type. In the case of Strings, it would be "". For Array, it would be []. We can see that from the following...

> append mempty "abc"
"abc"

> append mempty ["a", "b", "c"]
["a", "b", "c"]

So what does mempty return? It all depends on the context in which it's run. It doesn't make sense to run mempty outside of the context of a Monoid type, because what it returns all depends on the type. If you're dealing with Strings, it returns "". If you're dealing with Arrays, it returns [].

Knowing this, it's possible to create new types that are Monoids.

A type class seems to be a rule for how a data structure works. For instance you look at this type class...

class Stream list element where
  uncons :: list -> Maybe { head :: element, tail :: list }

This type class says there exists a structure called a "Stream" that is composed of something we want to consider "list-like", and an element of that list. And that if there is an instance of this type class that matches, then we know there is a function named uncons on that instance that we can run using the list argument.

A type class can accepts arguments - so in that way a type class is function-like. If you create an instance of a type class, then you pass arguments into the type class to create an instance. Those arguments can be types, or type constructors. We're not talking about values right now - we're talking about the things that hold the values.

So now we have this type class instance, which is a rule about types, or maybe you could say an expectation of types. If there is a show instance for a type, then we know there must exist a function 'show' that takes that type and returns a String. If there is a "Hashable" instance instance of a type, we know there is a function called "hash" that will take that data type and return a HashCode. We also know that in the future we can create new Hashable instance for new types in our applications.

So a type class is creating functionality based on a certain pattern - For instance we know that if we have two types that can be shown, then we can make a function for all those types that will take two types and show both of them. So we could create a function like this...

doubleShow :: forall a b. (Show a, Show b) => a -> b -> String
doubleShow a b = (show a) ++ " -- " ++ (show b)

But that's making the assumption that doubleShow will always function the same regardless of type - this doesn't allow a particular set of types to override the functionality. With type classes, we could do something like this for the base functionality...

class DoubleShow t1 t2 where
  doubleShow :: t1 -> t2 -> String

instance showDouble :: (Show a, Show b) => DoubleShow a b where
   doubleShow a b = (show a) ++ " -- " ++ (show b)

Which would accomplish the same as we did before. But if we wanted showDouble to function differently based on a specific type, we could create specific instances for each type combination we were interested in..

instance showDoubleStrings :: DoubleShow String String where
  doubleShow a b = a ++ " -- " ++ b

instance showDoubleNumbers :: DoubleShow Int Int where
  doubleShow a b = show a ++ ":Int -- " ++ show b ++ ":Int"

Now if we run doubleShow on strings and integers, we'll get the appropriate functionality based on the types...

> doubleShow 1 2
"1:Int -- 2:Int"

> doubleShow "a" "b"
"a -- b"

Obviously this is a contrived example, but hopefully it illustrates the benefit of type classes.

As a beginner, I look at something like this and think, "How do I create a stream?"

class Stream list element where
  uncons :: list -> Maybe { head :: element, tail :: list }

instance streamArray :: Stream (Array a) a where
  uncons = Data.Array.uncons

instance streamString :: Stream String Char where
  uncons = Data.String.uncons

But you don't create a Stream. There is no instance of Stream. Stream is a something we define externally and impose on existing types. It's a way of saying, this is how I want these types to work. This is the functionality I want to happen when these types come together.

Knowing this, we can create functions that have type class constraints, and know that the types that go into the function will behave the way we want them to by specifying that the types that go in must adhere to the structure the type class imposes on them.

foldStream :: forall l e m. (Stream l e, Monoid m) => (e -> m) -> l -> m
foldStream f list =
  case uncons list of
    Nothing -> mempty
    Just cons -> f cons.head <> foldStream f cons.tail

So now we can fold over various types of streams with the assurance that the data types follow the rules we want.

foldStream (\(n :: Int) -> [n]) [1,2,3,4]

This idea of defining functionality externally... What if the definitions of this external functionality already existed - meaning those rules are already known. For instance, what if we want our types to be added and multiplied in a well defined way - so that any program that knows our types can be added, can use them just like they would any other type, that is...

let t1 = MyType ...
let t2 = MyType ...
let added = t1 + t2

This is what type classes let us do. Because addition and multiplication operations are defined by the Semiring typeclass, we can make our type adhere to to that type class...

https://pursuit.purescript.org/packages/purescript-prelude/0.1.4/docs/Prelude#t:Semiring

class Functor f where
    map :: forall a b. (a -> b) -> f a -> f b

For there to be an instance of Functor for type Maybe...

instance functorMaybe :: Functor Maybe where
  map f (Just a) = Just (f a)
  map f Nothing  = Nothing

A functor takes a function from (a -> b), say, Int to Int. It also takes a value of type f a, say, 'f Int', or "Array Int", or "Maybe Int". 'f' is the type constructor. So in the case of the 'map' function implemented in prelude, we have the type...

forall a b f. (Functor f) => (a -> b) -> f a -> f b

This means that the "map" function will take any type constructor "f" as long as that type constructor has an instance of Functor. If you look in the docs, we can see there are Functor instances for Maybe and Array.

Apply and Applicative

class (Functor f) <= Apply f where
  apply :: forall a b. f (a -> b) -> f a -> f b

class (Apply f) <= Applicative f where
  pure :: forall a. a -> f a

"pure" can be thought of as lifting functions of zero arguments.

> let add = (\a b -> a + b)
> lift2 add (Just 5) (Just 10)
Just (15)
> lift2 add [5] [10]
[15]

What does "lift" do? When we lift a function, we run a function using types that the function was never intended to work with. For instance, if we made a function that creates a heading, by putting dashes below the text...

createHeading :: String -> String
createHeading h = h ++ "\n" ++ underline
  where
  underline = foldl (\acc char -> acc ++ "-") "" (Data.String.toCharArray h)

It takes a string, and returns a string. But what if wanted to use this function with a different type? Why not pass in a "User" or "Business" type, both with a "name" field if we wanted to show the username or business name as a heading? With lift we can do that...