h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

That's the kind of thing I was aiming for, I just kind of didn't get there...

Mmm, thanks to an unusual bout of clear thought, I now have a program which accepts a list of numbers representing the user number - for example [5,5,6,6,9] and attempts to add them all together to make 42. It doesn't succeed of course, but at least it's a start. The problem I'm now having is with such delights as being able to treat multiple sequential digits as part of the same number, and in choosing which operation to apply next, and in changing the way the system evaluates because at the moment it produces a list of operations such as

[Add 5, Add 5, Add 6, Add 6, Add 9, Nothing]

which evaluates as

((((5 + 5) + 6) + 6) + 9)

And as you can see, although this tendency for early evaluation doesn't cause problems when there's just addition, it's going to make multiplication and division extremely odd indeed. Especially since I just found another bug... ugh. Back to the drawing board on the data structure I think.

The way I dealt with multiple digits was my 'add_digit' operator. Bearing in mind that I use RPN, so that '1*(2+3)' is represented as '1 2 3 + *', it's easy for me to work out if the add_digit operator is legal at any point in the calculation.
'1+23' is '1 2 3 add_digit +', and
'123+4' is 1 2 add_digit 3 add_digit 4 +'
so the add_digit operator is legal either after two digits, or after a digit preceded by another add_digit operator.

The calculation of the result of an add_digit operator is simply 10*first_operand + second operand.

With only a head-addresable list as a data structure, I suppose I'd use a similar method to my RPN one, but the other way round
(12+3 would be '+ 3 add_digit 2 1')

* nods and thinks for a while *

The largest problem with Haskell is that lists may only contain one type, so I can't have a list like this

[5,5,+]

Because 5 is an Int, and + is a function of type Num a => a -> a -> a - clearly not the same at all! The solution to that of course is to define a new datatype:

data Operation = Val Int | Add | Subtract | Multiply | Divide

Thus allowing lists like

[Val 5, Val 5, Add]

to be constructed, having type [Operation] and meaning

5 5 +

in RPN.

Although

+ 5 5

Would be easier to evaluate, because although it's possible to recurse over a list from the end to the front, it's easier to do it the other way around as the internal representation of a list in Haskell is something like this:

a list [5,5] is effectively the same as (55:[])) internally, where [] is the empty list and : is the cons operator which takes a element and attaches it to the front of a list.

So deconstructing lists is easiest from the front, as you can pattern-match in function parameters

myFunction (x:xs), given a list, will split its parameter up into x, the head of the list, and xs, the list of all the other items in the list. Although there are other ways to get them - the head function returns the head of a list, and the tail function returns the rest of it. last and init do the same kind of thing, but return the last element and the beginning of the list respectively. I believe they're implemented in terms of head, tail and reverse...

I'm going to go and construct something that can work on lists like I just wrote about.

Gargh! Smiley conversion functions! That should read

( 5 : ( 5 : [] ) )

I defined an enumerated type in C of

typedef enum ops { zero, one, two, three, four, five, six, seven, eight, nine, add_digit, add, sub, mul, divide, power, negate, bang, root, arctan, invalid_op
} operators ;

The enumerated type *is* represented internally as some kind of int, so in practice, one actually equals 1, and though I *do* make use of that in my code :-
if (op>=zero && op<=nine) stack[stackptr++] = (int) op ;
else...

I don't technically *have* to - I could write explicit code for each digit :-
if (op==zero) stack[stackptr++]=0 ;
else if (op==one) stack[stackptr++]=1 ;
etc...

That's pretty much similar to what I'm doing - except that Haskell doesn't have enums, so I do have to write explicit conversion functions. Happily that's quite easy due to the way Haskell's datatypes work - because I use constructor functions with parameters, I can say Val Int instead of One, Two, Three etc. and thus I only need to handle one possible instance of Val Int - and that function just 'unwraps' the Int and returns it.

Except I'm actually using Floats to avoid any unpleasantness with division operations.

What I still need to do is a stack-based interpereter for RPN, it's the only way to do it that's even vaguely sane, and it is possible to model stacks in Haskell quite well... or at least, I've seen stack machines that use very little actual code to operate yet have a fairly comprehensive instruction set, written in Haskell. Something to look at later tonight.

Right, I now have a fully-working stack-based interpereter for RPN expressions represented as lists of operations, which handles Add, Subtract, Multiply, Divide, Factorial and AddDigit operations.

All I need to do next is write some code to generate some expressions to throw at it, and to check if they're forty-two or not! And I've got some ideas, but I need to have lunch and then go to three lectures, so I can't work on them right now