Monthly Archives: April 2013

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 , , ,
%d bloggers like this: