Tag Archives: pattern matching

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

Advertisements
Tagged , , , , ,
%d bloggers like this: