Creating A Binary Search Tree In Racket

Firstly, what is a binary tree?

A binary tree is a simple data structure where every node points to two more nodes, culminating in some type of final data type (usually null or nil).

1
2 3
4 5 6 7

A badly unbalanced binary tree might look more like this:

1
2 null
3 null
4 5 null
null null null 6 7

Both of these examples are not really sorted, and thus are not very useful as binary search trees. They look sorted in this format, and there is an order to them, but it’s not what I’ll be talking about when I’m trying to get to grips with the data structure in this post. A properly-sorted balanced binary tree would look like this:

4
2 6
1 3 5 7

This is much more useful, as it means that we can find our way around the tree by checking the value held by the current node against the target value. For instance, in the case of 5, we check to see if it’s larger than (4). It is, so we go right to the node with the value (6). 5 is smaller than 6 so we go left, and we’re there!

In a sorted list, we would need to make 5 checks to find our number, while for the BST we only need to make 3 (2 to traverse the tree, one to make sure we’ve ended on the correct value).

In an unsorted or unbalanced tree this would take a lot longer, and if the value didn’t exist in an unsorted tree the operation would take O(n) time to return #f. In a balanced, sorted binary search tree it takes O(log n) time to search for the value, even if the value doesn’t exist.

So, trees are most useful when they’re already sorted and balanced – or ideally automatically self-sorting and balancing.

Binary trees are closely related to a clever data structure called a skip list. The concept behind a skip list (crudely) is that a list is created:

(list 1 2 3 4 5 6 7 8 9)

Followed by a second list with only every other number, to speed up traversal times:

(list 1 3 5 7 9)

If we reach a number in the skip list which is larger than the target number, we know that we’ve moved one place past the target number. If the number matches, we’ve found the number. At a stroke, we’ve halved the search time for this list!

If you build your skip list to its intended height…

(list 1)
(list 1 5)
(list 1 5 9)
(list 1 3 5 7 9)
(list 1 2 3 4 5 6 7 8 9)

Looks a lot like a balanced binary tree!

So how do we make a binary tree in Racket?
(struct node (x left right)
#:transparent)

Ta-da.

Obviously there’s more to a binary tree than this, but that’s the basics of it. Once you have a node with a place for values, a left node and a right node, you’ve basically got a binary tree.

You can also extend the trees by hand:

(define tree (node 1 (node 2 null null) (node 3 null null)))

This is pretty rubbish though. If we treated linked lists like this in Racket, we’d have to make everything using (cons x (cons y null)), when what people actually do in the real world is write (list x y).

For this next part, I first created a leaf struct. Leaves should typically be very populous, so I wanted to identify them to save a large number of function calls.

(define-struct/contract leaf ([x (not/c null?)])
#:transparent)

Just the value, and it’s not allowed to be null.

Next, we create a function which takes a list and spits out a sorted, unbalanced tree.

;Modified quicksort to create ordered (but not balanced) binary search tree
(define (unsorted-list->binary-tree xs)
    (if (null? xs)
        null
        (if (null? (cdr xs))
            (leaf (car xs))
            (let* ([hd (car xs)]
                   [tail (cdr xs)]
                   [left (filter (lambda (x) (< x hd)) tail)]
                   [right (filter (lambda (x) (>= x hd)) tail)])
              (node hd (unsorted-list->binary-tree left) (unsorted-list->binary-tree right))))))

A simple modified racket quicksort function, similar to the quicksort I’ve discussed here before.

Sample input/output:

> (unsorted-list->binary-tree (list 1 2 3 4 5 6))
(node 1 '() (node 2 '() (node 3 '() (node 4 '() (node 5 '() (leaf 6))))))
>(unsorted-list->binary-tree (list 4 5 7 12 1 2))
(node 4 (node 1 '() (leaf 2)) (node 5 '() (node 7 '() (leaf 12))))

Meanwhile, turning a sorted list into a balanced tree is just as easy:

(define (sorted-list->balanced-tree xs)
    (if (null? xs)
        null
        (if (null? (cdr xs))
            (leaf (car xs))
            (let* ([n (floor (/ (length xs) 2))]
                   [mid (list-ref xs n)]
                   [left (take xs n)]
                   [right (drop xs (+ n 1))])
             (node mid (sorted-list->balanced-tree left) (sorted-list->balanced-tree right))))))

We don’t know what the median of a list is until it’s sorted, meaning I can’t balance a list that isn’t sorted without seeking out a different algorithm or data structure. What we could do is use a slightly different data structure, the Red-Black tree, but I’m still getting to grips with how and why exactly that structure works, so I’d rather not get into that now.

In other words, we might as well take an already-sorted list, then balance it.

If we don’t want to just feed lists into our tree, we make our tree-making function variadic. A variadic function is a function able to take a variable number of arguments.

In Racket, it’s simple:

;To create a binary tree from a variadic argument
(define binary-tree
  (lambda xs
    (letrec ([f (lambda (xs)
            (if (null? xs)
            null
            (let* ([hd (car xs)]
                   [tail (cdr xs)]
                   [left (filter (lambda (x) (< x hd)) tail)]
                   [right (filter (lambda (x) (>= x hd)) tail)])
             (if (null? tail)
                 (leaf hd)
                 (node hd (f left) (f right))))))])
    (f xs))))

If you’re wondering why I’ve bothered with the local recursive function (f xs) here, it’s because the variadic argument is a list as soon as it is passed to the function. Thus, if we tried recursing on it our function would get confused and think there was only one argument and stop recursing – unless we put a cond statement in to differentiate between lists and other types of input and…yes. This could get counter-productive.

This function works in the exact same way as the one we saw earlier, only it takes different numbers of arguments rather than different lengths of lists.

Finally, here is how I create a balanced tree with variadic arguments and of different types, and also a kth-select algorithm for any ordered tree in Racket:

;Requires a sign (e.g. <, >, <=, string<?) as the first argument to sort the rest of the arguments
(define balanced-tree
  (lambda xs
    (letrec ([f (lambda (xs)
                    (if (null? xs)
                        null
                        (let* ([n (floor (/ (length xs) 2))]
                               [mid (list-ref xs n)]
                               [left (take xs n)]
                               [right (drop xs (+ n 1))])
                          (if (null? (cdr xs))
                              (leaf mid)
                              (node mid (f left) (f right))))))])
        (f (sort (cdr xs) (car xs))))))
;count-tree-members - useful for kth selection algorithm
(define (count-tree-members ts)
  (cond
    [(null? ts) 0]
    [(leaf? ts) 1]
    [(node? ts)
     (+ 1 (count-tree-members (node-left ts)) (count-tree-members (node-right ts)))]))
;selection algorithm on tree
(define  (exn:fail "Error! Value k is too large or small for the search tree." (current-continuation-marks)))
(define (kth-select ts k)
 (letrec ([f (lambda (ts k)
              (cond
               [(null? ts) (raise )]
               [(leaf? ts) (if (= k 1) (leaf-x ts) (raise ))]
               [(node? ts) (let ([left (add1 (count-tree-members (node-left ts)))])
                             (cond
                               [(= k left) (node-x ts)]
                               [(> k left) (f (node-right ts) (- k left))]
                               [(< k left) (f (node-left ts) k)]))]))])
   (f ts k)))

In the mean-time, I’ve been fiddling around with small improvements to the Nearest Neighbour algorithm for the Travelling Salesman Problem (for fun, I’m not a crank I promise!), and continuing to work on my game in Java.

Here is the worst video this is it it is the worst one there is nothing worse than this.

Tagged , , , ,

Learning From Project Euler

If you’re just starting out with programming, like me, and haven’t yet checked out Project Euler and GitHub, please do. They’re not hard to get into, and I’ve found them really useful!

Project Euler is a particularly powerful impetus for you to improve on your programming skills. Like Codecademy, you start out simple and work your way up through challenges – unlike Codecademy, the challenge is actually worthwhile.

Github, meanwhile, is really useful for storing the code you’re working on and encouraging commentary/interaction with your fellow programmers. It’s also an introduction to version control, which is a useful thing to understand.

I’d urge you to listen to the people at Project Euler and avoid committing Problem answers to Github, as it kind of takes away from the challenge.

Project Euler

In the in-between, a problem with Project Euler forced me to re-design the function I built here, and I’m pretty happy with the results.

My original prime-finding function was taking well over a minute, so I had no choice but to refactor.

It’s a great demonstration of how Project Euler forces you out of your comfort zone – in my case, into Racket vectors. Even though they’re essentially the same as arrays in most other languages, something in me balked at using vectors in Racket. Something about their mutability struck me as not-right in a language so defined by its immutability.

Here’s the first draft of what I wrote, working with vectors to create a static sieve of eratosthenes of length (n):

(define (primes-to x)
  (letrec ([f (lambda (count vs n)
                (cond
                  [(= n 0) (begin (vector-set! vs 0 #f) (f (+ count 1) vs (+ n 1)))]
                  [(= n 1) (begin (vector-set! vs 1 #f) (f (+ count 1) vs (+ n 1)))]
                  [#t
                   (if (= n x)
                       vs
                       (if (< count x)
                           (if (= n count)
                               (f (+ count n) vs n)
                               (begin (vector-set! vs count #f)  (f (+ count n) vs n)))
                           (f (+ n 1) vs (+ n 1))))])

                )])
    (f 0 (make-vector x #t) 0)))

Since you can access vector members using vector-ref, and this program currently runs all the way to (= n x) – which means that we check almost every item on the list – there’s a lot of optimisation which could be done, and done profitably.

The important thing is (if (= n count), which takes away progressively larger chunks of things to check as the formula grows – I believe this puts it in O(n log n) space, or close to it. With this formula, I can check two million digits in ~6 seconds and I could cut that down substantially with some quick tweaks.

Eventually, I’ll hit a wall with the sieve of eratosthenes, and be forced to use the sieve of atkin – which I do not understand and actually dread facing. When I do have to face it, though, it will magically transform into a fun and interesting challenge. That’s the magic of Project Euler!

Last day, Capricorn-15s

Tagged , , ,

Merge Sort In Racket

I talked briefly about merge sort only yesterday, in my post about quicksort.

I also mentioned Lisp, which in the form of “Common Lisp” is a really nice practical language I really intend to learn properly one day. The more I learn about it, the more startled I am at how far ahead of its time it was – or more accurately, at how primitive popular ‘modern’ programming languages such as C, Java and C++ can be. Note that primitive doesn’t mean easy to grasp – if anything, the lower levels of abstraction possible with OOP and procedural languages mean that it’s harder to build the same kinds of things and more difficult to understand what’s going on once you have assembled a simulacrum of the abstraction you intended.

The things people build in these languages constantly astound me, and they have the added bonus that they’re often backed by powerful enough compilers that they’ll run much faster than their FP brethren. I’ve kind of got away from the topic though.

Merge Sort

So yes. Merge sort. Off we go.

I had a naive view that merge sort was quicksort’s less glamorous older brother, until watching the videos on the preview of my Coursera course in algorithm design, I realised that algorithm design and speed were incredibly complex issues subject to a whole host of factors.

I also realised, on trying to implement a quick and ugly merge sort in Racket, that it was harder to do than I had anticipated.

Merge sort pretty much forces you to create at least two different functions:

  • A zipping-up function, which merges ordered arrays, lists or vectors into bigger ordered listy things
  • An unzipping function, which splits the initial lists until they are small enough that ordering them is a trivial operation

Generally, either the zipping-up function or the unzipping function can also take care of ordering the tiny little lists.

For the tiny little lists, we either order them at length 2 by a simple conditional check, reversing the list if they’re “out of order”, at length 7 by doing an insertion sort (I’ve chosen this length because it’s the same length Java apparently use in the default Java sort function (source: Wikipedia) or at length 1 by simply having the zipping-up function handle them.

Length 1 is the easiest for me, so I go with that. I’d probably go with the length 7 option if I was actually building a sort function of my own for god-knows-what reason.

Let’s build our zippy function then – it’s going to be really simple. As before, comments are marked out with a semi-colon.

(define (merge-lists xs ys)
  (cond
    [(null? xs) ys]
;if xs is empty, return ys [(null? ys) xs]
;if ys is empty, return xs [(< (car xs) (car ys))
;if the head of list "xs" is bigger than head of list "ys" (cons (car xs) (merge-lists (cdr xs) ys))]
;cons head xs to (recurse) [#t ;I use true as an else cond here - possibly bad style? (cons (car ys) (merge-lists xs (cdr ys)))]))
;cons head ys to (recurse)

Sure, it only sorts ordered lists – but we’re gonna make sure these are ordered in the sort function.

(define (merge-sort xs)
  (cond
    [(or (null? xs) (null? (cdr xs))) xs]
    [(null? (cddr xs))
     (merge-lists (list (car xs)) (cdr xs))]
    [#t
     (let ([x (ceiling (/ (length xs) 2))])
       (merge-lists (merge-sort (take xs x))
                    (merge-sort (drop xs x))))]))

Wow, we’re done. That was SO easy. I love Racket.

All we do is check if the list is empty (null?) or has a length of 1 (if its tail is null? it must have a length of 1). If either of these is the case, we return the list.

The next bit uses (cddr), which checks if the tail of the tail is null. Similarly, (cdddr) would return the tail of the tail of the tail of the list, or (cadr) would return the head of the tail of the list – it’s simply a matter of combining (car) – head – and (cdr) – tail – in the proportions you desire. If this returns true, we merge-lists on a list of the head of list and tial of list.

But why do we specifically turn (car xs) into a list, and keep (cdr xs) as-is?

Well, that’s due to how linked lists work.

A pair in Racket, and other “tuples” in other languages, are constructed by (cons)ing values together. So (cons 1 2) results in a pair ‘(1 2). A linked list can be constructed by (cons)ing another value to this pair (e.g. (cons 1 (cons 2 3))).

However, a list is only officially a list in Racket if it ends in a null value, for many reasons – we’ve seen some of them here! When we find where the null value is, we know to end the recursive function for sure. So (cons 1 (cons 2 3)) – not a list. (cons 1 (cons 2 null)) – a list.

This affects us here because the head of our list cannot end in null – it is by definition a single value. Although the tail looks like a single value, ‘(x), it’s actually a list ‘(cons x null). So the head goes in a brand new list, while the tail remains as it is.

Finally, we define a local variable equal to half the list’s length (rounded up with the (ceiling) function) and we call (merge-list) on the first half and second half of our list, divided up using the (take) and (drop) functions from the Racket library. They do more-or-less what you’d expect – take the list up to position x, or drop the list up to position x. We keep merging and merging our merge-sort function until we finally end up with a 2-length list, at which point we order and merge them – and merge this with the other list that has been merged – and so on, all the way back until the function returns.

It’s nice and fast, we separate our concerns prettily, and it’s not even as complex as quicksort – merge sort is awesome.

As always, if you’ve seen something egregious in this post, please correct me. I make these posts primarily to learn, so anything you can let me know is gratefully accepted!

Tagged , , , ,

In Which I Decide That Ruby Is A Silly Place

I have nothing against Ruby’s image, despite the hipster-bashing that its name tends to invoke.

I think that the “Rails coding ninja” archetype the start-up world has conjured up is obnoxious, but I also think it’s strictly a product of the tech start-up world. Outside that limited circle, I doubt that anyone who uses Rails is any different from the people who were using PHP fifteen-odd years ago.

However, I cannot stand the language itself.

Ruby seems to offer roughly the same package as PHP (easy enough to code things up even for non-computer-science types like me, particularly well-suited to web development, slow, something of a mish-mash from a language-design perspective), just improved. Its niche, as far as I can tell, is the same. It’s avoided the mistakes PHP made, it’s a little slower, and it has the ability to do some clever cross-paradigm things (functional programming is a different paradigm because Ruby is object-oriented-turtles all the way down). It saves developer time, I guess, used right.

Meh. It doesn’t excite me, and I don’t learn anything new from it. I’m sure once I’m experienced enough with programming to be jaded I will find it utterly thrilling – but right now, all I see is a heap of syntactic sugar on top of a big ol’ mess of blah.

Let’s not go to Ruby, it is a silly place. Here is some more messing around with Lisp’s grandchild, Racket instead, along with explanations.

Quicksort

Quicksort is a decently fast sorting algorithm, as the name would imply. Here’s a simple way to implement a rough version in Racket, with explanations of what I’m doing as I go.

Comments are marked out with “;”, in case anyone reading doesn’t do Racket.

(define (quicksort xs)
    (if (null? xs)
    xs ;if the list we pass to quicksort is empty, return the list.
    (let* ;let* allows you to define multiple local bindings
        ([hd (car xs)] ;variable "hd" = the head of our list.
         [tail (cdr xs)] ;tail = list tail
         [smaller (filter (lambda (x) (< x hd)) tail)]
         [bigger (filter (lambda (x) (>= x hd)) tail)])
      (append (quicksort smaller) (list hd) (quicksort bigger))))

This is pretty concise, but it’s not really that simple of course. I’ve used the simplest way of writing things without really examining why it works or how it will work in practice.

The “smaller” and “bigger” bindings are made by passing our anonymous function (the bit with the keyword “lambda”) to the library function “filter”. That’s a bit of a cop-out, although filter is fairly simple it is a pretty cool and useful function to know how to write. Let’s have a look at my understanding of how it works:

(define (filter-local fn xs) ;defined locally to avoid shadowing
    (letrec ([f (lambda (xs acc) ;introducing an accumulator
        (if (null? xs)
            (reverse acc) ;give back the consed list at end (in right order)
            (if (fn (car xs)) ;if our function is true for head of list
                (f (cdr xs) (cons (car xs) acc));recurse and cons head to accumulator
                (f (cdr xs) acc))))]);else recurse and do nothing
    (f xs null))) ;starting the recursive function

This is probably not how it’s done exactly, but it gives you the general idea of what we’re doing with it – grabbing a list of numbers smaller than the head of our list, and a list of numbers bigger than or equal to the head of our list. This illustrates that this seemingly simple function actually is doing more work than it looks like, filtering the same list twice for every call. We could definitely make this more efficient, if we needed to, with a more specific single local function:

(letrec ([f (lambda (x ys sml big)
    (if (null? ys)
        (append (quicksort sml) (list x) (quicksort big))
        (if (> x (car ys))
            (f x (cdr ys) (cons (car ys) sml) big)
            (f x (cdr ys) sml (cons (car ys) big)))))])
    (f hd tail null null))

Feel free to check this function, it may be a little off as I’ve just written it in WordPress now. The idea, however, is that we do less work with each call to quicksort. This is not traditionally that important in algorithms (the Big O notation is usually more relevant, especially as if we’re not using the sort on large lists we’ll probably choose, say, an insertion-sort method instead) but it could probably knock at least some time off its run-time.

The way it works is by recursively calling quicksort on the lists of smaller and larger numbers, gradually sifting the big list blocks so that eventually we’re sorting (1) (2) and (3) rather than (213) (5) and (6559).

Now I run quicksort on a boring random list of 10000 numbers.

It’s super-fast! Awesome.

Just for kicks, I’ll run it again on the ordered list and -huh?

On ordered lists, this quicksort algorithm is slooooow. If we start with a pre-ordered list and use head/car as our “pivot”, quicksort runs at its worst-case performance, O(n^2). Usually, worst-case performance is very rare, but since ordered lists are pretty common we’ve just upped the chance that we’ll get a worst-case performance. Now, we could simply check to see if a list is ordered before we run the algorithm (boo!) or we could refactor the algorithm (yay!).

We can choose the middle-value by dividing the length of the list by two and using list-ref to choose the appropriate element – that’s the simplest way.

Further optimisations are a little more complicated (honestly, not much more complicated) and can be seen here: http://en.wikipedia.org/wiki/Quicksort

I’ve also written an implementation of merge sort[1] in Racket to make sure I understand that. It’s possible I’m a little over-excited about my upcoming Coursera course on algorithm design and analysis, and it’s definitely the case that I need to go write in some less pretty languages in the near future.

As always, if you’ve seen something egregious in this post, please correct me. I make these posts primarily to learn, so anything you can let me know is gratefully accepted!

[1] You can see how I created my merge sort here if you’re interested.

Tagged , ,

Standard ML: Pattern Matching And Datatypes

SML is another functional language, but its syntax is a lot more familiar than Racket’s to the average newbie programmer. Values are assigned using the “=” sign, addition works the way you’d expect it to –

(i + 1)

not

(+ i 1)

– and there is a comforting similarity to English/mathematical phrasing (“let val x = 2 in x + 3 end”). That said, I found the syntax and semantics of Standard ML far harder to pick up than I did Racket’s.

We learned using Emacs and a Read-Eval-Print-Loop. So; I can now fumble my way through a REPL, create and delete files, switch buffers, copy and paste in Emacs with some small amount of speed. I suppose that’s another little life skill which might come in handy at some point.

To look at what I learned from Standard ML, I chose to use datatypes and pattern matching. These stood out most strongly on the course as essential parts of the SML language’s ‘feel’.

As ever, I’m just showing this code because it puts pressure on me to keep improving, not as a demonstration of what you should do. If you’re just getting interested in SML, don’t use my code as an example!

datatype Count = Num of int
		  | Fizz
		  | Buzz
		  | FizzBuzz
		  | NoCount

This is how we start off, defining a datatype “Count”.

We need to define “Count” because we’re going to be returning a list from our FizzBuzz function, and in SML every list element must be the same. We could have tried turning everything into one long string, or a list of lots of short strings, but that would create problems later.

All this means is that something called “Num 1″, “Num 2″, “Fizz”, “Num 4″, “Buzz” … and “Fizzbuzz” are all of the same type of thing, counts, just like the numbers 1 2 3 4 5…15 are all ints.

In theory in Standard ML you could have a “One True Datatype” which encompassed absolutely everything. It’s at that point that it’s really unlikely that SML was ever the language you should have been using in the first place.

fun fizzbuzz (x:int,y:int) =
    let fun fb(x,acc) =
	    if x<=0
	    then acc
	    else
		if x mod 15 = 0
		then fb(x-1,FizzBuzz::acc)
		else
		    if x mod 3 = 0
		    then fb(x-1,Fizz::acc)
		    else
			if x mod 5 = 0
			then fb(x-1,Buzz::acc)
			else fb(x-1,Num (x+y)::acc)
    in fb(x,[])
    end

This is the fizzbuzz-making function.

It takes two ints, an int for length (x) and an int to determine our starting point (y, where “0” will start us off at “1”), and then creates a sequence from FizzBuzz in accordance with those two ints.

“::” in SML is the same as “cons” in the Lisp family, and “[]” is effectively the same as “null” or “empty”. Confusingly, “null” in SML is a boolean operator equivalent to “null?” in Racket.

The logic of it’s pretty simple. We create a temporary tail-recursive function with an accumulator, and kick it off (without using “y” as an argument — “y” is going to remain constant throughout the process so that’d be pointless).

If we hit one of our targets (multiple of 3, multiple of 5, multiple of 15), we cons a “Count” datatype of the appropriate sort to our accumulator. If we don’t, we simply cons a “Count” datatype of “Num i” to our accumulator list, with i equal to x + y.

Once x has counted down to 0, we return the accumulator list, nicely sorted from lowest to highest:

fizzbuzz(20,4);
val it =
  [Num 5,Num 6,Fizz,Num 8,Buzz,Fizz,Num 11,Num 12,Fizz,Buzz,Num 15,Fizz,...]
  : Count list

Simple.

Now before we translate it back using nested pattern matching, we quickly create some exceptions.

exception NoListEntered
exception ImpossibleListEntered

Well, that was thrilling.

On to the function I wrote:

The arguments this time are a list of Counts “xs”, and a starting point “y” (which should match the starting point of Counts, or you will probably get an error – there are ways of improving this function).

It was at this point that I realised that the function was pretty damn stupid in this form, as we could get the same results with a function which simply, well, counted for the length of a list from a given starting point. Creating a “proper” reverse fizzbuzz would be more complicated than this.

I decided to go ahead with the function in this form for the reason that these posts are not supposed to be solving problems — they’re demonstrations that I understand certain concepts in a language.

In that respect, this function does what I want it to. It type-checks, it returns the correct result, it uses pattern-matching and it uses datatypes. It really doesn’t have to do those things, and it’s possibly the most silly way of solving this “problem”, but it does anyway.

dealwithit.jpeg

fun reverseFizzbuzz (xs:Count list, y:int) =
    let fun fb(xs, acc, lastNum, lastCount) =
	    if null xs
            then
		case lastCount of
		    NoCount => raise NoListEntered
		  | _ => rev acc
	    else
		let val x = hd xs
		in
		    case x of
			Num i    => fb(tl xs, i::acc, i, Num i)
		     | Fizz      =>
		       (case lastCount of
			    Num i => fb(tl xs, (i + 1)::acc, i, Fizz)
			  | Buzz => fb(tl xs, (lastNum + 2)::acc, lastNum, Fizz)
			  | NoCount =>
			    if y mod 3 = 0
			    then fb(tl xs, y::acc, y, Fizz)
			    else raise ImpossibleListEntered
			  | _     => raise ImpossibleListEntered
		       )
		     (*end of Fizz case*)
		     | Buzz      =>
		       (case lastCount of
			    Num i => fb(tl xs, (i + 1)::acc, i, Buzz)
			  | Fizz => fb(tl xs, (lastNum + 2)::acc, lastNum, Buzz)
			  | NoCount =>
			    if y mod 5 = 0
			    then fb(tl xs, y::acc, y, Buzz)
			    else raise ImpossibleListEntered
			  | _     => raise ImpossibleListEntered
		       )
		     (*end of Buzz case*)
		     | FizzBuzz  => 
		       (case lastCount of
			    Num i   => fb(tl xs, (i + 1)::acc, i, Buzz)
			  | NoCount =>
			    if y mod 15 = 0
			    then fb(tl xs, y::acc, y, FizzBuzz)
			    else raise ImpossibleListEntered
			  | _       => raise ImpossibleListEntered
		       )
		(*end of FizzBuzz case*)
		     | _ => raise ImpossibleListEntered
		end
    in fb(xs, [], y, NoCount)
    end

All pattern matching does is check what type we’re dealing with (for instance “What was passed to the function “fb” as the argument “lastCount”?”) and then act on that information. This is why we introduced “NoCount” as a datatype up top, so we can introduce a NONE value without breaking type rules.

Pattern matching would be a great way to deal with the real reverse fizzbuzz function, but I’ll get to that another day.

Welp, there’s SML. I know what pattern-matching is, and can implement it in a (very) silly fashion, and I know how to use datatypes. Also, as long as this post remains up, it’ll push me to do better — seriously, it’s like a dull ache in the back of my mind.

I’m going to find a way of showing something about Ruby next — and then I’ll be done with these for a little while, focussing on building a small frontend-only site for my girlfriend.

Hopefully I won’t come back to SML for some time yet

Tagged , , , , ,

Racket: FizzBuzz, Thunks And Streams

It’s all very well talking about what I’ve learned, but keeping up with it and providing proof is another issue entirely.

So, I’m going to provide variations on what I’ve done with FizzBuzz, a simple programming test to see if you understand the basics of a language – to see if you can be taught the rest from there, really.

The Rules Of FizzBuzz:
1. You start counting.
2. If a number is a multiple of 3, it must be replaced by the word "Fizz".
3. If a number is a multiple of 5, it must be replaced by the word "Buzz".
4. If a number is a multiple of both, it must be replaced by the word "FizzBuzz".

Like I said, simple.

I’m hoping to write up quick but unique implementations in Racket, Ruby, and SML that highlight a little of what I’ve learned from each language.

I’m starting with Racket, a programming language developed from Scheme, which in turn developed from Lisp. All together you’ve got a bit of a mafia movie going.

Racket was by far my favourite language studied on the course, which is probably why I’m starting with it. It’s often seen as a teaching language, but you can definitely do some pretty practical stuff with some easily-available libraries – I’ve been playing around with its JSON abilities during my lunch breaks at work, and it seems very natural (especially as I’ve not done any work with web APIs before).

The basic syntax is:

(define a-symbol a-thing)

This develops pretty quickly and naturally into recursive functions:

(define (multiply-recurse-silly x y)
  (letrec ([f (lambda (y acc)
            (if (<= y 0)
             acc
            (f (- y 1) (+ x acc))))])
    (f y 0)))

This is a silly and impractical use for recursion, using repeated addition to multiply two numbers together. To explain what’s going on here, if you don’t speak Racket:

The main function is defined as “multiply-recurse-silly” and given two arguments “x” and “y”.

We need a recursive function, so we “let” a new symbol, “f” be a new, local function. This function won’t need to change “x”, but it will need to count the number of times it’s added “x” to itself (the multiplication), and we’ll give it an accumulator called “acc” to help it keep track of what “x” is so far.

Once “y” has hit 0 (or below, through some error or inappropriate input), the function returns what the accumulator has saved up.

Otherwise, the function calls itself with the value of “y” – 1 (so “y” is like a countdown timer going towards zero) and “x” added to itself.

Finally, none of this will work unless we call our new “f” function in the first place, so we call it with the last line and then close all the brackets up.

Not too complicated. There’s some things I don’t like about this function looking back on it though:

1.
It’s bad that it isn’t an error for y to be less than 0. This is clearly a function to multiply only positive numbers together, so returning “0” when we try to multiply by a negative number is a big mistake.

What I should have done is either (a) added a new conditional branch so that if y is less than 0 the multiplication works (and works properly) for negative numbers or (b) added a new conditional branch so that if y is less than 0 we raise an error.

2.
For this function we don’t really need a local recursive function. I wanted practice using local functions because I haven’t been using them while designing my game in Java, but this was completely unnecessary. The entire function could have fit on one line, if I’d simply written it to call itself.

Moving quickly on from that:

(define (fizz-buzz start finish)
  (letrec ([f (lambda (strt acc)
                (cond [(> strt finish) (reverse acc)]
                      [(and (= (modulo strt 3) 0) (= (modulo strt 5) 0)
                       (f (+ strt 1) (cons "FizzBuzz" acc)))]
                      [(= (modulo strt 3) 0) (f (+ strt 1) (cons "Fizz" acc))]
                      [(= (modulo strt 5) 0) (f (+ strt 1) (cons "Buzz" acc))]
                      [(integer? strt) (f (+ strt 1) (cons strt acc))]
                      [#t (f 1 acc)]))])
    (f start null)))

My first FizzBuzz function in Racket. It seems to work OK.

Just a simple recursive function, only this time I am using cond, which in practice works like a switch statement, instead of if. “cons”, not to be confused (ha) with “cond”, simply means that we are adding something to a list. At the very end, we see a “#t” condition – this means that for any value other than “#f”, if the conditions before it haven’t executed, the condition at the end will execute. This is because Racket interprets any value other than false (#f) as true (#t).

This means that if an incorrect value is passed by the user as the start value we assume they just meant “start from the bottom!” and go from there.

Again, this is probably not something I would include in a program meant to be used seriously.

Because of the way we are joining the list together, we need to reverse it at the end to make sure it comes out the right way round for human eyes.

This function is able to count from a start number to a finish number, and gives back a Racket list depending on those numbers, in accordance with the FizzBuzz rules.

So:

(fizz-buzz 1 15)

Gives:

'(1 2 "Fizz" 4 "Buzz" "Fizz" 7 8 "Fizz" "Buzz" 11 "Fizz" 13 14 "FizzBuzz")

All working as expected.

Of course, if we put the inputs in the wrong way round, it gives us:

'()

A null or empty list.

Going with the bodge-job aesthetic I’ve employed so far, I decided I wanted it to be able to handle both ways. Simple but unsatisfying to implement:

(define (fizz-buzz-up-or-down x y)
  (letrec ([f (lambda (countdown goal acc)
                (cond [((< countdown goal) acc]
                      [(and (= (modulo countdown 3) 0) (= (modulo countdown 5) 0)
                       (f (- countdown 1) goal (cons "FizzBuzz" acc)))]
                      [(= (modulo countdown 3) 0) (f (- countdown 1) goal (cons "Fizz" acc))]
                      [(= (modulo countdown 5) 0) (f (- countdown 1) goal (cons "Buzz" acc))]
                      [(integer? countdown) (f (- countdown 1) goal (cons countdown acc))]
                      [#t (raise "Inappropriate input!")]))])
    (if (> x y)
        (f x y null)
        (f y x null))))

Giving us:

(fizz-buzz 15 1)
'(1 2 "Fizz" 4 "Buzz" "Fizz" 7 8 "Fizz" "Buzz" 11 "Fizz" 13 14 "FizzBuzz")

Just to confuse everything, this time I’ve changed the function so that the accumulator doesn’t need to be reversed, and the new way of doing things means that I have to raise an error if there’s an inappropriate input – I can’t just guess what the countdown would start at.

On the other hand, with the new up-or-down-ness this function will raise an error for an inappropriate input before I even get to that stage, rendering the error-raising and checking to see if the number’s an integer entirely moot, but it’s nice to be prepared (maybe).

The last thing I did in this file was create the ability to input custom fizzes and buzzes into the function:

(define (fizz-buzz-plus pairs x y)
  (letrec ([f (lambda (xs countdown goal acc)
                (cond [(< countdown goal) acc]
                      [(letrec ([g (lambda (ys ac)
                                     (cond [(null? ys)
                                            (if (null? ac)
                                                (f pairs (- countdown 1) goal (cons countdown acc))
                                                (f pairs (- countdown 1) goal (cons (reverse ac) acc)))]
                                           [(= (modulo countdown (cdar ys)) 0) (g (cdr ys) (cons (caar ys) ac))]
                                           [#t (g (cdr ys) ac)]))])
                         (g xs null))]))])
    (if (> x y)
        (f pairs x y null)
        (f pairs y x null))))

We’ve got an inner loop and an outer loop here.

(fizz-buzz-plus (list (cons "Snark" 7) (cons "Flunge" 4) (cons "Grontch" 9)) 1 25)

This time we pass in a list of pairs and get back:

'(1 2 3 ("Flunge") 5 6 ("Snark") ("Flunge") ("Grontch") 10
11 ("Flunge") 13 ("Snark") 15 ("Flunge") 17 ("Grontch") 19 ("Flunge")
("Snark") 22 23 ("Flunge") 25)

More-or-less what we expected.

(fizz-buzz-plus (list (cons "Snark" 3) (cons "Flunge" 6) (cons "Grontch" 9)) 1 25)
'(1  2  ("Snark")
  4  5  ("Snark" "Flunge")
  7  8  ("Snark" "Grontch")
  10  11  ("Snark" "Flunge")
  13  14  ("Snark")
  16  17  ("Snark" "Flunge" "Grontch")
  19  20  ("Snark")  22  23  ("Snark" "Flunge") 25)

I can’t remember why I chose to cons them together rather than string-append them. That’s this line:

[(= (modulo countdown (cdar ys)) 0) (g (cdr ys) (cons (caar ys) ac))]

It worked for my purposes. I suppose it makes it easier to parse the list as well, when we’re looking back over it.

Yeah, that was probably my reasoning. Let’s go with that.

Now to what I really learned: thunks and streams.

A “Thunk” is a function without arguments which we create only so that we can delay it ever being called, hopefully forever. Thunks are therefore prone to existentialist angst, but they are very useful in many ways.

I remember what they do by thinking of them as an onomatopoeia for a program slamming up against one (THUNK) or alternatively as a “then-function” – a function to do later. Then-func – Th-unc – Thunk. It’s a stretch but it helped me remember it.

Probably the most useful place for a Thunk (at least, at my current level of programming knowledge) is a Stream. A Stream is a Thunked pair, of which pair the latter part is a call to the Stream usually but not always with a different argument. This enables us to create infinite patterns, which we can read at a later date. Naturally this is very useful, and naturally I will only use it to mess around (for now at least).

Here is a simple stream I wrote while on the course. It shows alternately dan.jpg then dog.jpg, but only when called:

(define dan-then-dog (lambda () (cons "dan.jpg" (lambda () (cons "dog.jpg" dan-then-dog)))))

And here is how we read any given stream for a certain number of steps (starting from step 1):

(define (stream-for-n-steps s n)
   (if (<= n 0)
       null
       (cons (car (s)) (stream-for-n-steps (cdr (s)) (- n 1)))))

So, this is how we adapt our simple FizzBuzz function from earlier (I changed modulo to remainder, but it’s otherwise a very similar idea):

(define fizz-buzz-stream
  (letrec ([f (lambda(x)
                (cons
                 (if (and (= (remainder x 3) 0) (= (remainder x 5) 0))
                     "FizzBuzz"
                     (if (= (remainder x 3) 0)
                         "Fizz"
                         (if (= (remainder x 5) 0)
                             "Buzz"
                             x)))
                 (lambda () (f (+ x 1)))))])
                (lambda () (f 1))))

Finally, as an extension of the fizz-buzz-plus function defined earlier, here is a stream for prime numbers.

(define prime-numbers-stream
  (letrec ([f (lambda(x xs ys)
                (if (< x 3)
                    (cons x
                          (lambda () (f (+ x 1) ys ys)))
                    (if (null? xs)
                        (cons x
                              (lambda () (f (+ x 1) (cons x ys) (cons x ys))))
                        (if (= (remainder x (car xs)) 0)
                            (f (+ x 1) ys ys)
                            (f x (cdr xs) ys)))))])
    (lambda () (f 1 (list 2) (list 2)))))

This is really what FizzBuzz is all about. Once you’ve assigned enough multipliers to miscellaneous noises, you end up with only the prime numbers left. If you played FizzBuzz in Primary school, like me, you might have just realised it was a sneaky way of teaching you to think about the patterns involved in multiplication.

Someone once said that prime numbers are what’s left when all the patterns are taken away. I prefer to think of them as the seeds of their own patterns. Each prime fulfils its own unique function, creating a pattern that tessellates perfectly with every other prime, stretching out into infinity.

My method of reading this infinite stream is a lot less elegant and looks like this:

(define (read-prime-stream x)
  (begin (if (equal? x "quit")
             (display "Prime Number Generator Exited.")
             (display (stream-for-n-steps prime-numbers-stream x)))
         (display "\r")
         (if (equal? x "quit")
             (display "\r")
             (read-prime-stream (read)))))

(display "Type \"quit\" (including quotes) to exit. \r")
(read-prime-stream (read))

I learned a lot by writing all of this, though, and it’s really helped solidify some of the concepts of the course in my mind.

Did I get anything wrong? Was I inaccurate somewhere? Should I have expanded on something? Let me know in the comments.

Tagged , , ,

A First Experience With Open Courses

I’ve finally finished what was, for me, a fairly gruelling ten week slog.

Using Coursera, a platform offering free University-level courses to anyone who’s interested, I tried Introduction To Programming Languages as a first course. I met the requirements (just, sort of, not really), and figured “eh, it’s an introduction. How hard could it be?”

Very hard.

I made the mistake of thinking that this was going to be an introduction to the three programming languages on the course. It was actually an introduction to programming languages in general, and concepts in programming language design. I found even the first homework difficult, and struggled through much of the course. It was frustrating, and ate up almost all my free time for the entire ten weeks the course ran (and although I’ve completed the final exam, I still need to complete some peer assessments).

The lesson from this is that open courses are not an easy option, and it is probably not something that most people will be able to do in their spare time without major sacrifices. The courses can be extremely challenging at an extremely high level. It’s not simple stuff. For me, this difficulty was exactly what rendered the courses such a rewarding experience, and really re-affirmed my assumption that what I was learning was really worthwhile rather than just coding busy-work.

On that note, the lectures were top quality. Concepts were taught in a way that seemed very natural, code provided to explain ideas was very clear and useful, and the entire staff (from University of Washington) were extremely dedicated. My thanks to them. Moreover, the concepts built and fed into each other in a very subtle, unassuming way that made ideas that would have frazzled my brain at the start of the course fairly clear by the end. Professor Dan Grossman regularly interacted with and helped students in the forums, and following on from that, the community was incredible. The interaction between people who’d been programming in C for 16+ years, Haskell evangelists and complete novices (like me) was invariably friendly and invariably helpful. It was a great experience.

Just thinking about how much I learned on this course staggers me a little now. Before the course, I had no idea what thunks, streams, or mixins even were, and (as it turns out) I only had a shaky grasp of interfaces, subclassing, and data structures. It would take me twenty minutes to work out what a simple recursive function did, and twenty more to implement my own. I’m now fairly comfortable with functional programming (more comfortable than I am with OOP, in fact), I can edit SML and Ruby with confidence, and I can write programs in Racket. My understanding of Java and its seemingly arbitrary rules and regulations has improved no end, although the syntax looks a lot uglier and more verbose than it used to (and it always looked quite verbose).

In the end I think I got a grade of around 80 (scores aren’t finalised until peer assessments finish), and I would be upset with anything below 70 given the huge amount of effort I put into this course. That’s another thing about these courses – theoretically, the grade doesn’t matter, but once you’ve invested some time into them it becomes just as important as if you’d paid for the course.

I’d recommend this course to absolutely anyone interested in programming should it come up again, and I personally enjoyed my experience with Coursera immensely. I should probably note that there were a few bugs in the autograder, but that these were always found extremely quickly and dealt with almost instantly.

Thanks, Dan. Thdanks.

Tagged , , , ,

Game Update: ThuggRPG

Working title is ThuggRPG. I’ve finally got a level of sorts up and running. It doesn’t look like much but I have big plans for this.

ThuggRPG

Now it’s just a matter of literally everything.

Went for the Alcest, stayed for the Katatonia.

Tagged , ,

Things I Am Doing

I sometimes go quiet for fairly long stretches. Sorry about that.

If you’re interested, these are the kinds of things I tend to be doing during these long stretches. Or in this case the kind of thing I am doing right now.

Learning HTML & CSS (& Javascript)

Thanks to Codecademy, this is so easy it’s ridiculous. It eases you into the learning process as gently as a scared newborn piglet attempting to suckle from a hedgehog.

Learning Java

This is harder. The ultimate aim of this is to…

Design And Complete A Vast Non-Linear 2D RPG/Strategy Hybrid

Should take a little while.

Edit The Novel I Wrote During NaNoWriMo

Looking to focus on this during this year’s NaNoWriMo.

Getting My Poetry Published In Magazines

I have written some poems I’m happy with, so in a way I feel like I’ve ‘completed poetry’. I feel like I should push myself further here, so I’m going to.

Inventing Puns

Why was the Catholic protestor arrested?

He was being in-a-pope-riot.

Proclaiming That Science Is Badass

It really is, especially at the moment.

Life Stuff

Finding people to take my room, trying to keep up with cool games, working for a living, analysing metal until I take all the fun out of it for myself and others, basically doing enough things that take up enough time that I’ll only rarely be able to update here.

Hopefully when I do it’ll be somewhat entertaining.

…this one doesn’t count.

Some 70s War Comics

I picked these war stories up in a small store that sold a few different kinds of oddities. These booklets were really cheap so I bought a very small handful of them.

I found them fairly interesting, both as comic books and as historical artifacts. Though not, actually, historical artifacts from the wars they portray. These are from the mid-’70s, and as such are more pop-culture-historical than propaganda/history-historical.

The stories are sometimes relatively complex in their morals though — relative, that is to say, to the modern action film, where a half-German dude would almost certainly be the villain, rather than a conflicted hero torn between duty and personal crisis.

Here are some of what I consider to be the most fascinating pages of the books.

If anyone’s not happy with me uploading these here for reasons of copyright, I can take them down again. However, I have uploaded these as a useful resource & for commentary, and will not make any money from them being here, so there is a pretty strong Fair Use case.

If you’d like to use the images, I’d appreciate a link back or a credit! I won’t get too upset if you don’t though.

Sergeant Shouts Orders From D-Day Boat As Shells Land

D-Day Landings.

The D-Day landings. Not sure about the face there. Can faces peel half away from the skull and scream at you? If so, why hasn’t there been an album about that yet?

Two Soldiers Flee A Collapsing Pylon | Marines Stand Together With Weapons

Now who needs more pylons.

This is the inside front cover of Hell’s Gates and the title page.

I like that you could just buy 192 pages of pictures of things exploding back then and no-one would look at you askance. Although I suppose Michael Bay Esq. scratches the same itch today.

English Soldiers Shoot A German Soldier

A shiny penny to anyone who can tell me which one is the hero in this image.

I’m not sure whether I’m bothered by the fact they just shoot the German soldier who had refrained from shooting them or not.

I guess not.

More to the point, why did he give them the chance? Why didn’t he shoot the guy with the trusty service revolver as soon as he reached for it? Why was he not even pointing the gun at them at any point despite clearly seeing them and having time to shout at them to stop?

I think these questions will likely remain unanswered.

The Origin Of The Marines

And now, what some guy thinks the marine-navy rivalry started as.

This comic purports to tell the origin of the rivalry between marines and navy. It’s supposed to explain why Cain, the Unfairly Treated Private Who Ends Up A War Hero of this little escapade, is victimised for being called Cain.

I don’t know why I was expecting it to be something to do with Cain from the Bible, but I was. I also assumed some Rime Of The Ancient Mariner would be thrown in there. I think I attended too many English Literature classes to see things properly.

Man Firing Machine Gun

He actually has a fair bit to lose, or we wouldn’t really care about him as readers. His life is the first thing that springs to mind but that might be being facetious.

This comic has the most sophisticated artwork, certainly in terms of cover art, out of all the comics I picked up.

On the inside, too, there was a marked increase in quality over some of the earlier examples. More detail, more realistic facial expressions, motion and emotion captured better.

Unfortunately…

British Soldiers Talk About Japanese Soldiers

“The yellow flood…” – acceptable in January 1942 in Britain, probably. Acceptable in mid-1970s Britain? Really?

I can’t read the actual story without flinching a bit. I understand that it makes sense in context, but the narrative is still one of Allied good, “Japs”, “yellow swarm” bad, and it’s not particularly edifying.

It only gets worse from there, too, I just couldn’t really bring myself to fill my blog with anti-Japanese tirades from the seventies. It’s not really what I want people to find on my personal blog.

The following is from “CUT OFF!”, yet another little booklet.

British squaddie blows up a tank, shouts "Sock-O!"

Sock-O!

As far as I want to know, this was what the entire war was about.

Plucky squaddies blowing shit up and shouting things like “Sock-O!” and “Bally good show!”.

Good clean fun, and everyone’s back in time for tiffin cake at great-aunt Marjorie’s.

German Machine Gun Crew Shot From Behind

Just a machine gunner, crumping.

This was the only book out of the ones I bought that I genuinely enjoyed for reasons other than (a) interest in retro curios and (b) a mind about as complex as a hammer.

With a xenophobic authority figure and a genuinely suspenseful, tight plot, plus a slightly complicated lead character who you could actually empathise with at times, and who dealt with (gasp) emotional issues, this was the only comic that engaged me, and which I would read again.

The others are fascinating examples of cheap comic book art of the time, and I will keep them as long as possible, but the story in Runaway Glory is actually quite well-written. It reminds me of some of the Golden Age superhero comic books in how tightly, simply, and coherently it is plotted.

Now I have written in depth about heavy metal, games, comic books and my favourite search engine. Ahem. I have cool interests too. That involve people. Death matches count as human interaction, right?

I might have used Bolt Thrower before, but damn if it ain’t appropriate here!

Tagged , , , ,
%d bloggers like this: