Following on from my previous posts about functors, applicative functors and applying applicative it would only be natural for me to post a follow up on the topic of Monads. Monads take shape very similarly to applicative functors so for this post to make sense, I suggest you read the previous articles so that you have a chance to follow along.
What is a Monad?
At a code level, a Monad is a type that is an instance of the Monad type class. At a concept level a Monad allows you to provide a function that is context-unaware to operate over values that are wrapped in a context. Immediately, you’d think that this is weaker functionality that what was defined for applicative functors - and you’d be right in thinking so, but Monads do provide a very natural way to write code against our types. Here is the type definition for a Monad.
Moving through all of the defined functions, you first see return. return is the same as pure which we defined when making an applicative functor. return’s role in this type is to lift a value into a context. The next function you see is >>= which is pronounced “bind”. This is the major difference right here. >>= is what takes a value wrapped in a context m a and takes a function with a parameter of a returning a wrapped b as m b, with the function returning a b in a context m b. The remaining two operations are rarely delved into as their default implementations suffice majority of scenarios.
Laws
There are some laws that need to be abided by when implementing Monads. Left Identity suggests that
x >>= f is the same thing as f x
Right Identity suggests that
m >>= return is the same as m
Associativity suggests that
(m >>= f) >>= g is the same as m >>= (\x -> f x >>= g)
Such that it shouldn’t matter how these calls are nested together.
Custom context
Applying this knowledge to our rather useless example “CustomContext” discussed here, we can make this type a monad with the following definition.
Ok, so - as prophesied return is doing the same thing as pure did for us - it’s just lifting a plain value into our context. >>= or “bind” on the other hand is taking the value out of its context and applying a function to it. We can check out our bind implementation in action with the following simple examples.
Our value is having a function applied to it. Values are getting de-contexted, worked-on than re-contexted. Pretty straight forward. To show you how >>= can work for us, I’ve created a function that will accumulate even numbers as they are received into it. If an odd number is encountered, the accumulated total get wiped back to zero until conditions are met to have another two consecutive calls with even numbers. Here’s how the function looks.
Using guards, we filter out odd numbers sending the result back to zero otherwise we continue to accumulate. Note how the inputs are just plain integers but the output is an integer wrapped in one of our CustomContext types. With the use of >>= the following calls are possible.
First of all, we’re freely using wrapped and un-wrapped contexts thanks to that bind operator. More interestingly (and demonstrative to our purposes here), the last example appears to be in error, but it’s really not. Think about it this way.
So you can see here that the next sub-sequent call to accumEven would finish with a 0 (zero) value as the 13 would be carried onto the next call and would be tested for evenness. Even if this isn’t the best example, it still demonstrates how bind is sending information between the calls.
do Notation
Another nicety when working with Monads is do notation. do notation allows you to clean up a lot of the boilerplate that builds up around the functionality you write when working with monadic values. Here’s a very simple function that builds a CustomContext from two other CustomContexts by adding them.
You can see how things start to get a bit gnarly once you chain more calls together. Using do notation, this gets cleaned up pretty well. The above can be re-written like so.
That’s so much easier to read! There’s do notation at work for you, anyway. Well, that’s all there is for Monads right now. As soon as I try something useful with them, I’ll post a follow-up article of Monads in Application.
In most of your day to day applications, numbers that fit within 8, 16, 32 and 64 bits are enough. Sometimes you may need to stretch out into your floating point processor to include some more precision and start looking at 80 bit numbers. Today’s post, I want to start on a library in assembly language that works on even bigger numbers. There are going to be some caveats or conditions that we’ll establish up front, but they will be big numbers! The design considerations for this library will be as follows:
Unsigned integers
Fixed size
With this information, we can now start to build our library.
The big number data type
Well, it’s not really that special at all. We just need to define an array of quad-words to the length that we want. So, an example would look like this.
bignum_size EQU10; bignums will be 640bits in sizenum_aresqbignum_size; make our bignum variable
That’s all pretty simple. A number is just an array of a pre-defined length. With a length to 10, at 64 bits per array index we’ve got ourselves a 640 bit number. Quite large. In fact, we’re talking numbers up to 4.562441e+192. Now that’s impressive.
Lets operate!
We’ve got a very impressive data type that we can declare where ever we want, but how do we use it? We need to define all of the management, arithmetic, logic and printing ourselves. First of all though, we’ll want to be able to zero out our number, which is just continually writing zeros over our memory buffer (much like a memset).
; --------------------------------------------; bignum_zero ; initialize a bignum to zero ; ; input ; rdi - address of the number ; --------------------------------------------_bignum_zero:pushrax; save any registers pushrcx; that we'll mow over pushrdixorrax,rax; the value we want to set to movecx,bignum_size; the number of quads to write repstosq; clear out our number poprdi; restore any registers that poprcx; we saved popraxret
Excellent. We can initialize our big number now to zero so that we have a starting point. Next, we’ll want to be able to debug any problems that we may have while building this library, so its going to be of great benefit to be able to see what the value is of our number. The following code leans on some assembly I had written in a previous article which displays the value in RAX. Here’s how we’ll print our big number to screen.
; --------------------------------------------; bignum_print ; prints a bignum to the console ; ; input ; rsi - address of the number ; --------------------------------------------_bignum_print:pushrax; save off any values pushrbxpushrcxmovrcx,bignum_size; we'll print all blocksnext_block:movrbx,rcx; setup our base pointer decrbx; to point to the block corresponding shlrbx,3; to our counter rcxmovrax,[rsi+rbx]; get the value in rax call_print_rax; print it decrcx; move onto the next block jnznext_block; keep printing poprcx; restore any saved registers poprbxpopraxret
Most obvious thing to note here is that we’re moving through the bignumber back-to-front so that it’s presented on screen in a human manner. We can test what we have so far is working by writing a small piece of test code.
; zero out our numbermovrdi,num_acall_bignum_zero; print it to screenmovrsi,num_acall_bignum_print
Which, rather uninterestingly will just spit out a massive list of zeros.
So, lets do something a little more interesting. The smallest pieces of arithmetic that I think we can implement for these numbers is increment and decrement.
Increment
This is straight forward. Add 1 to the lowest part of the number. If that part of the number just “clocked”, or reset to zero - we must carry our value onto a higher block.
; --------------------------------------------; bignum_inc ; increments a big number by 1 ; ; input ; rdi - address of the number ; --------------------------------------------_bignum_inc:pushrcx; save off any registers pushrbxpushraxmovrcx,bignum_size; worst case, we'll have to; go through all blocksxorrbx,rbx; reset our base to be zero _bignum_inc_carry:movrax,qword[rdi+rbx]; get this block into rax incrax; increment itmovqword[rdi+rbx],rax; store it back cmprax,0; check if we "clocked" jne_bignum_inc_done; if we didn't, we're finished addrbx,8; move the base onto the next block decrcx; 1 less block to process jnz_bignum_inc_carry; continue until we're finished _bignum_inc_done:poprax; restore any of the saved values poprbxpoprcxret
Alright, we’ve got incrementation going on here. The most interesting case for us to test is when a block is sitting on the carry boundary or sitting at 0xffffffffffffffff. After we increment that, we should see that clear out to zero and the next block to get a 1.
movrdi,num_acall_bignum_zeromovqword[rdi],0xffffffffffffffff; setup out number on the boundarymovrsi,num_acall_bignum_print; print it outmovrdi,num_a; push it over the boundary withcall_bignum_inc; an increment movrsi,num_a; print out the new numbercall_bignum_print
Those massive trails of zeros are getting annoying. We can clean them up later by making our print routine a little smarter. But you can see that we’ve successfully incremented over a boundary so that our next higher block gets a one.
Decrement
This is pretty much as straight forward as incrementing, on this time we’re not going to carry to a higher quad-word, we’re going to borrow from it if we do cross a boundary. Here’s the code for a decrement.
; --------------------------------------------; bignum_dec ; decrements a big number by 1 ; ; input ; rdi - address of the number ; --------------------------------------------_bignum_dec:pushrcx; save off any registers pushrbxpushraxmovrcx,bignum_size; worst case, we'll need; to go through all blocksxorrbx,rbx; clear out the base _bignum_dec_borrow:movrax,qword[rdi+rbx]; get the current quad decrax; decrement it movqword[rdi+rbx],rax; store it back in the number cmprax,0xffffffffffffffff; check if we went across a boundary jne_bignum_dec_done; if not, get out now addrbx,8; move onto the next block decrcx; not done yet? jnz_bignum_dec_borrow; keep processing borrows _bignum_dec_done:poprax; restore the saved registers poprbxpoprcxret
This really is the increment routine just with the numeric direction reversed. Making sure that we are on the right track, we can test out the decrement across a boundary again.
movrdi,num_a; setup our number right call_bignum_zero; on the boundarymovqword[rdi],0xffffffffffffffffmovrsi,num_a; print its current statecall_bignum_printmovrdi,num_a; increment over the boundarycall_bignum_incmovrsi,num_a; print its statecall_bignum_printmovrdi,num_a; decrement it over the boundarycall_bignum_decmovrsi,num_a; print its statecall_bignum_print
Again, it’s pretty hideous with the trailing zeros, but you can see this in action now. Back and forth, across boundaries - no sweat.
Conclusion
Well, this is just the tip of the iceberg for this particular library. I’d hope to demonstrate logical testing, addition, subtraction, multiplication and division as well shortly. The best part about these routines is that if you wanted to operate on 6400 bit numbers, all you have to do is change the constant bignum_size that I’d set earlier to 100.
Associativity is a property of a function which has an output equivalent no matter what order the function is applied. Addition and product are examples of mathematical functions that are associative as opposed to subtraction and division which are not. Today’s post will focus on associative functions and their definitions through Monoids in Haskell.
Associative functions
In the introduction to this post, I spoke about associative functions and gave a few examples. Here are those examples again, but demonstrated mathematically.
These examples are pretty straight forward in their reading. You can see clearly that the product and addition operators are associative, subtraction and division not. String concatenation (or array concatenation) is also associative such that:
You can find more information specifically about the type up on the Haskell Wiki. From the definition above, we can see that there are 3 functions to be defined.
mempty
mempty is the identity value for the monoid. It acts more like a constant rather than a function.
mappend
mappend is the binary function that can be used between two of these typed Monoids.
mconcat
mconcat folds the mappend function between the elements of an array of Monoids.
Monoid Laws
Above, I have gone through the basic principals of associative functions which by-and-large cover off on the laws that a Monoid must abide by. There are some explicit ways of writing this concept, there are as follows.
mempty `mappend` x = x
x `mappend` mempty = x
(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)
That’s Monoids for you. Take a look as some example implementations on the Wiki and around the web.
In a previous post, I had pretty much got the textbook definition down for an Applicative Functor and shown some of its pre-existing uses. Today’s post, I want to walk through some code that I’ve written that implements Applicative.
Put it in context!
Right on! It’s all about context. When making instances of the Functor typeclass, it’s all about defining fmap appropriately to “operate” on the data that sits in a context. What’s a context then? The books and articles that I’ve read use pre-existing types as examples. A list for instance is a context, Either is a context, Maybe is a context. All of these things wrap data. So, let’s make our own context to put something in.
dataCustomContexta=CustomContextaderiving(Show)
There’s our context, CustomContext. It just wraps around something .. anything. We can apply a functor instance to this with the following.
fmap allows a function to get inside the context and operate on the inner data - alright, I’ve said this already. Proof that all of this is working is as follows.
λ> let x = CustomContext 10
λ> x
CustomContext 10
λ> fmap (+5) x
CustomContext 15
We wrapped 10 in a context. We applied the function (+5) to the value inside our context. We got back a 15 wrapped in a context. Moving into Applicative territory now, it’s not only the value that we operate on that has the context this time - it’s also the function that we apply. We use the pure function to lift a value inside a context and we use <*> to apply a function to a value (both being inside their respective contexts). Here’s how we’ll define Applicative for our type.
The implementation of pure is straight forward, we’re just going to pop the value in a CustomContext context. The sequential application function <*> is implemented very much how fmap was implemented, in fact it’s the same. The difference comes in with how the parameters are supplied. We’re taking the function out of the context, we take the value out of the context - we apply the function and wrap the result in the context. Here it is in action.
This post is just a small write up on the differences between these three keywords and their uses within Haskell.
type
Using the type keyword is the same as just referring to the actual type that you’ve declared. In other words, type just lets you make a synonym for the original type.
-- a deck is an array of cardstypeDeck=[Card]-- an array of crows would be a murdertypeMurder=[Crow]
Using these, we’ll be able to refer to a Card list as a Deck. They can be used interchangeably as they’ll directly cast. All this really does for us, is gives a pre-existing type a more meaningful name to our code.
newtype
Using the newtype keyword, we make a thin wrapper around an existing type. Something that will be treated differently at compile time, but will be directly translatable (and not subject to conversion) at runtime.
-- declare the data typenewtypeWord=Word{getWord::String}derives(Show,Eq)-- using the data typelethelloWord=Word"Hello"letbyeWord=Word"Bye"letgreetingWord=Word"Hello"
newtype only allows you one constructor and one field. It’s important that its used when you’re creating data entries that have these constraints on them. These attributes make newtype a great candidate for when you just want to add a typeclass instance to an existing type.
data
The data keyword allows you to build much more complex types. With the data keyword, you can have as many constructors and fields as you like.
-- create a person data typedataPerson=PersonStringStringIntderiving(Show)letjohn=(Person"John""Smith"35)-- create a more complex employee typedataEmployee=EmployeeIntPersonderiving(Show)letjohn=(Employee6(Person"John""Smith"35))
Of course, it would make more sense to use “record syntax” when defining these datatypes above.
-- define a persondataPerson=Person{firstName::String,lastName::String,age::Int}deriving(Show)-- define an employeedataEmployee=Employee{employeeId::Int,person::Person}deriving(Show)-- define "john"letjohn=Employee{employeeId=6,person=(Person{firstName="John",lastName="Smith",age=35})}
Wrapping up
Use type to give your types more meaningful names
Use newtype if you just want to take an existing type and add a typeclass instance to it