Thursday 1 October 2015

Wise words on encapulation

From nklein software...
Encapsulation is about protecting the person who has to read your code. It’s not about protecting your code.
That is to say, if you have some complicated data structure and you diligently hedge it about with getter and setter functions, the benefit there is to those who will read and write code that uses that data structure. Which includes you of course. By using the access functions it is clear in the code what you are actually doing.  Your functions give meaning to the operations.

The reason often cited for using encapsulation functions - that it lets you change the implementation at a later date without needing to change the interface - is nugatory - that situation hardly ever arises.

This is a good point, well said.

Thursday 6 August 2015

Returning from a function

I remember the first time I saw someone violate the return conventions in a function.

This was in submission to Personal Computer World magazine.  They used to run a column where people could write in with their own utility routines.

Someone submitted a routine that returned the current contents of the program counter - that is to say where in the code you are currently executing.

The routine looked like this:

; v.1
WHEREAMI  POP  HL
          PUSH HL
          RET

Perfectly simple; you pop the return address into the HL pair then push it back on the stack and then return as normal.  You might use it like this:

...
76C9      CALL  WHEREAMI
76CC      ; on return, HL contains 76CC
...

The author submitted comprehensive documentation about the routine, aiming at some arcane humour in setting a new record for comment-to-code line count ratio.

However the record was promptly snatched away by the editor of the column, who pointed out that the routine can be rewritten thus:

; v.2
WHEREAMI  POP  HL
          JP   (HL)

You can hear the original author saying damn.  Or can you?  There is more than just a simple optimisation that separates v.2 from v.1 - in fact a different way of thinking is at work.  I would have written v.1.  I know about the JP (HL) instruction but until I saw this I would never have thought of v.2.

I pondered for a long time before I was convinced that v.2 would really work.  It looks like one of those dodgy bodges that looks good but falls over when you apply it to the real world.  Surely what happens when the routine that calls WHEREAMI returns to whereever it came from?  No that would work.

It's just so... disturbing... to see someone ending a function with a jump rather than a return, much as it would be to see someone leave a meeting by leaping out of the window rather than walking through the door.

In v.1 we temporarily allow ourselves to peek at the stack, and make a strict point of putting it all back where it was before we proceed.  It is not our business to mess with the stack.  It is not our business to tell the processor where to go next.  That is all taken care of automatically by CALL and RET and we do poke around there unless we want to lose a finger in the machinery.

In v.2 the attitute is different.  We take responsibility for the flow of control, we grab the return address and use it ourselves - this is a significantly different way to think about code.

Tuesday 4 August 2015

A Quick Visit to the Database

To tie together these threads let's actually issue that query to the database from Haskell...

Link to the modules for database access via ODBC (one I prepared earlier):

> :m +Database.HDBC
> :m +Database.HDBC.ODBC

Create a connection using the credentials set up in the ODBC settings:

> conn <- connectODBC "DSN=Lethbridge;UID=POLLY;PWD=S0wn4kb8J6f"

Get a record set back by sending the query via the connection:

> records <- quickQuery conn "select dept, sum(salary) from employees group by dept;" []

And what do we get back?

> records
[[SqlByteString "Ed",SqlInt32 175],[SqlByteString "MS",SqlInt32 320],[SqlByteString "Yale",SqlInt32 160]]

Close the session...

> commit conn
> disconnect conn

Monday 3 August 2015

A Random Thought

I recently listened to the podcast on Artificial Intelligence from the Programming Throwdown boys and I was struck by the thought that the phrase "No fruit flies like a banana" exactly fits the opening theme of Brahms' Second Piano Concerto.


List Comprehensions And Beyond

From Simon Peyton-Jones web site I find a link to a paper discussing extensions to list comprehensions to make them more like SQL select statements.

To make use of these we need to do two things: firstly warn the GHCi that I will be using the language extensions:

:set -XTransformListComp

And then import some extra functionality it will need:

:module +GHC.Exts

As an example we have a table of people with the Name (String), Dept (String) and Salary (Int).
To see the contents of this table on the database we issue a basic SQL select command:

select
*
from
employees

And the results are

Name Dept Salary
----------------------------
Simon MS 80
Erik  MS 100
Phil Ed 40
Gordon Ed 45
Paul Yale 60
Polly MS 45
Sue Ed 90
Jill Yale 100
Jackie MS 95

And how we would replicate this in Haskell code?

Start by setting out a couple of type synonyms to make the database fields clearer:

type Name = String
type Dept = String
type Salary = Int

And here is our database table as a Haskell list of tuples:

employees :: [(Name, Dept, Salary)]
employees = [("Simon", "MS", 80)
            ,("Erik", "MS", 100)
            ,("Phil", "Ed", 40)
            ,("Gordon", "Ed", 45)
            ,("Paul", "Yale", 60)
            ,("Polly", "MS", 45)
            ,("Sue", "Ed", 90)
            ,("Jill", "Yale", 100)
            ,("Jackie", "MS", 95)]

In Haskell the query to select all the records comes out as a simple list comprehension:

selectAll = [ (name, dept, salary) |
              (name, dept, salary) <- employees ]

The result is so:

*Main> selectAll
[("Simon","MS",80),("Erik","MS",100),("Phil","Ed",40),("Gordon","Ed",45),("Paul","Yale",60),("Polly","MS",45),("Sue","Ed",90),("Jill","Yale",100),("Jackie","MS",95)]

So far so normal.  For our first enhancement we want to be able to specify an order for the output records.  For example let us see the records in order of increasing salary.  This is simple enough with an "order by" clause in SQL:

select
name, salary
from
employees
order by salary

name salary
Phil 40
Gordon 45
Polly 45
Paul 60
Simon       80
Sue 90
Jackie 95
Jill 100
Erik 100

To do the same in a list comprehension we add an extra use for the keyword then, which
here lets us introduce the function sortWith into the expression:

selectWithOrder = [ (name, salary) |
                    (name, dept, salary) <- employees,
                    then sortWith by salary ]

The sortWith function sorts a list of elements using the user supplied function to project something out of each element

*Main> :t sortWith
sortWith :: Ord b => (a -> b) -> [a] -> [a]

So here we are sorting by the salary field of the record:

*Main> selectWithOrder
[("Phil",40),("Gordon",45),("Polly",45),("Paul",60),
("Simon",80),("Sue",90),("Jackie",95),("Erik",100),
("Jill",100)]

But nobody wants to see who is getting the lowest salary.  In SQL we add the keyword desc to see the results sorted into descending order:

select
name, salary
from
employees
order by salary desc

name  salary
Erik 100
Jill 100
Jackie 95
Sue 90
Simon 80
Paul 60
Polly 45
Gordon 45
Phil 40

To do the same in our list comprehension we use the newtype Down like this:

selectWithReverseOrder = 
    [ (name, salary) |
      (name, dept, salary) <- employees,
      then sortWith by Down salary ]

Down has the ingenious function of inverting the sort order:

newtype Down a = Down a deriving (Eq, Show, Read)

instance Ord a => Ord (Down a) where
    compare (Down x) (Down y) = y `compare` x

So if you compare Down x with Down y you get the reverse of what you'd get if you compare x with y.  So our comprehension now comes up with the top salary first:

*Main> selectWithReverseOrder
[("Erik",100),("Jill",100),("Jackie",95),("Sue",90),
("Simon",80),("Paul",60),("Gordon",45),("Polly",45),("Phil",40)]

We can also create selections with group functions such as sum: for example we need to list the departments and their total salary spends. In SQL we group by a field and apply functions such as sum():

select
dept, sum(salary) as [total salary]
from
employees
group by
dept

Which looks like this:

dept total salary
Ed 175
MS 320
Yale 160

The corresponding list comprehension is this:

selectByGroup = [ (the dept, sum salary) |
                  (name, dept, salary) <- employees,
                  then group by dept using groupWith ]

*Main> selectByGroup
[("Ed",175),("MS",320),("Yale",160)]

There are several new things happening here.

Here we have a group by clause added to the list comprehension.  This does something dodgy to the fields: what we are returning is not individual dept and salary fields but lists of fields, so we add the the function and the sum function to reduce these back to a single record.

The function the is a new one: it checks first that all the elements of the list are identical and then returns just that duplicated element.  (It bears no resemblance to the Common Lisp operator of the same name, I checked)

*Main> :t the
the :: Eq a => [a] -> a

The function groupWith uses the function that you supply, with type (a -> b), to projects out an element (the one of type b) from each list element in your list - - it uses the b-type item to sort the input list and then to form groups by equality on these projected elements.

*Main> :t groupWith
groupWith :: Ord b => (a -> b) -> [a] -> [[a]]

But I just want to see the top one... the department with the largest spend...

In SQL I can opt to see the top so many of the results, like this:

select top 1
dept, sum(salary) as [total salary]
from
employees
group by
dept
order by sum(salary) desc

Which comes out as:

dept total salary
MS 320

In our newly empowered list comprehensions we can use the then keyword this time to bring in the standard function take, to take just the first record from the result set:

selectMaxGroup = [ (the dept, sum salary) |
                   (name, dept, salary) <- employees,
                   then group by dept using groupWith,
                   then sortWith by Down salary,
                   then take 1 ]

*Main> selectMaxGroup
[("MS",320)]

Thursday 16 July 2015

Progress Report

If you map out the power of your computer year by year from a base line at say 1985


And then subtract out the fraction of this power that your computer expends on background tasks that you didn't ask for, don't understand and can do nothing about


Then you get a pretty good model of how much you can actually get done


So it is not my imagination, the nineties really were the Golden Age.

Wednesday 15 July 2015

Problem of Nines, alternative method

Well, there is a quick way I find on Stack Overflow to convert an integer to the binary string equivalent - import Text.Printf and then use the printf function with "%b" as a descriptor.  If this doesn't work then you might need a newer version of Haskell.  Anyway, read this to convert to an integer and then multiply by 9 - so the list of numbers that are all made of digits 0 and 9 can be defined so:

Prelude> import Text.Printf
Prelude Text.Printf> let nines = [ 9 * read (printf "%b" n) | n <- [1..] ]

Test this:

Prelude Text.Printf> take 10 nines
[9,90,99,900,909,990,999,9000,9009,9090]

So the question asked for the first of these numbers that is a multiple of 23:

Prelude Text.Printf> head [ n | n <- nines, n `mod` 23 == 0 ]
990909

I like the other way better partly because I'm not sure how this function printf works.  Doesn't it have to take a variable number of parameters to match the placeholders in the string?  How does that work against the type checker?  Some reading to do


Tuesday 14 July 2015

Problem of Nines

Here is a pretty problem from Programming Praxis that has popped up on Planet Scheme... what is the lowest number that is a multiple of 23 that is made of only the digits 0 and 9?

One way to find it would be to scan through all the numbers made of 0s and 9s.  This looks tricky until you see the numbers:

9
90
99
900
909
990
999
...


Aha, you say, these are just like binary numbers:

1
10
11
100
101
110
111

Except take each one and multiply by 9 and Bob's your uncle you have all the numbers made of 0s and 9s.  Scan through and pick the first one that is a multiple of 23.  I'll try that approach later when I've figured out how you convert a number to a binary digit sequence.  Must be a simple way.

However the alternative path to the solution is to produce the list of multiples of 23 and pick the first one that is made only of 0s and 9s.

Now the multiples of 23 are easy - it's just [23,46..]:

Prelude> take 10 [23,46..]
[23,46,69,92,115,138,161,184,207,230]

And the condition that the number is made of 0s and 9s? - well, given a number n we say read n to convert to a string, which is just a list of characters: we can then use the function all to apply the test to this list that all the characters are either 9 or 0, that is to say all are an element of the list "90"  - we use the function elem for this:

Prelude> all (`elem` "09") "9080"
False
Prelude> all (`elem` "09") "9090"
True

So we set up a list of all numbers n drawn from the multiples [23,46..] subject to the condition that all the characters of the string representation of n are in the list "90" - in other words

[ n | n <- [23,46..], all (`elem` "90") (show n) ]

Of course this is an infinite list, but we just ask for the first element, i.e. the head, as follows:

Prelude> head [ n | n <- [23,46..], all (`elem` "90") (show n) ]
990909

So the answer is 990909.  In fact let's see the first 10 solutions:

Prelude> take 10 [ n | n <- [23,46..], all (\c -> c=='0' || c=='9') (show n) ]
[990909,9099099,9909090,90000909,90990990,99090900,99909999,99999009Interrupted.

An infinite list is like the Tao, it seems empty, but draw upon it and it is never exhausted - - although in this case I gave up waiting after the eighth answer...

Monday 29 June 2015

The Fifth Problem (4)

Right, so now I can built the solution.  First get all those combinations of  the operations:

let ops = take 6561 (iterate cyclops "________")

Then map mergeops onto all of those to make a list of strings like "1_2_3+4_5_6-7_8_9" etc:

let rawStrings = map (mergeops "123456789") ops

Then use that little filter to remove the underline characters from the strings:

let neatStrings = map (filter (\c -> c /= '_')) rawStrings

Then just extract the ones where the string evaluates to 100:

let hundreds = filter (\s -> eval s == 100) neatStrings

At this point you might be thinking, blimey, Haskell is fast.  Actually of course due to the magic of lazy evaluation Haskell hasn't done anything yet.  Now we actually ask to see the results and the cogs have to turn:

*Main Data.Char> hundreds
["123-45-67+89","12-3-4+5-6+7+89",
"12+3+4+5-6-7+89","123+4-5+67-89",
"1+2+3-4+5+6+78+9","12+3-4+5+67+8+9",
"1+23-4+56+7+8+9","1+2+34-5+67-8+9",
"1+23-4+5+6+78-9","123+45-67+8-9",
"123-4-5-6-7+8-9"]

Now I see how that goes I could make a tidy logical version ("Plan to throw one away")

Looking at the solution posted by the blogger I see he has gone for a neat recursive way to deduce the answers.  Er or I mean neat in concept: I can't work out what the actual code does.  I must admit on this one it never crossed my mind not to use the brute force approach.  Logically I should now try to code up Santiago's solution in Haskell.  Hmm.

The Fifth Problem (3)

And then to evaluate the final string.  Work down the string keeping a running accumulator: each time you hit a digit, multiply your accumulator by 10 and add the value of the digit: but if you hit a plus or a minus, add or subtract the value of the remainder of the string.  So we get this:-

The main function...

val :: String -> Int
val s = valx 0 s

This works by calling its auxiliary function...

valx n [] = n
valx n (c:cs) =
    case c of
      '+' -> n + valx 0 cs
      '-' -> n - valx 0 cs
      _ -> valx ((n * 10) + (ord c - ord '0')) cs

And so...

*Main Data.Char> val "1+2+34-5+67-8+9"
-18

Wrong answer.

The reason is that doing it recursively implicitlty brackets from the end of the string, so we are working out 1+(2+(34-(5+(67-(8+9))))) but really we want to work out (((((1+2)+34)-5)+67)-8)+9

OK so I want an auxiliary function that takes an accumulator for the whole expression, and as I go along a smaller accumulator for the value of the number I'm working through.  And a number -1 or +1 for the last sign character I encountered.

At the start, the accumulators are zero and the sign is +1.

Each time I hit either a + or a - character I either add or subtract the value of my current number to or from the accumulator.  Also I set the sign for the next number, and set the little accumulator back to
zero.

When I hit a digit I use it to increase the value of the current number.

So I get this:

eval :: String -> Int
eval s = evalx 0 0 1 s

evalx :: Int -> Int -> Int -> String -> Int

evalx acc cur sgn "" = 
    acc + (sgn * cur)

evalx acc cur sgn (c:cs) =
    case c of
      '+' -> evalx (acc + (sgn * cur)) 0 1 cs
      '-' -> evalx (acc + (sgn * cur)) 0 (-1) cs
      _ -> evalx acc ((cur * 10) + (ord(c) - ord('0'))) sgn cs


*Main Data.Char> eval "1+2+34-5+67-8+9"
100

This one does work.

The Fifth Problem (2)

So now I will want to merge the list of operations into the list of numbers.  I did a merge function already recently, it went like this:-

mergeops :: String -> String -> String
mergeops ns [] = ns
mergeops [] os = os
mergeops (n:ns) (o:os) = n : o : mergeops ns os

For example two digits then plus then two digits then minus then two digits...

*Main Data.Char> mergeops "123456789" "__+__-__"
"1_2_3+4_5_6-7_8_9"

Ah yes I will want to filter out the "nothing" operation characters, say like this:-

*Main Data.Char> filter (\c -> c /= '_') it
"123+456-789"

The bit in the brackets is a lambda, the function taking c and returning a boolean true if c is not equal to the underline character.

And it is the Haskell shell's way of giving you the result of the previous expression you just evaluated.

The Fifth Problem (1)

The Fifth Problem is to write a program that will output all the possibilities of putting the operations + or - or nothing between the numbers 1, 2 ... 9 (in that order) so that the result is 100.

For example, 1+2+34-5+67-8+9 = 100

Therefore I will want to cycle through all the possibilities for the eight operations (one between each pair of the nine numbers) - - each of which is one of plus + minus - and nothing _.

The function - er - cyclops (hee hee) will take a list of operations each expressed as a character +, - or _ in a string: is the first one is _ it changes to +, if it is + it changes it to -, and if it is - then it changes it back to _ but carried the change forward by cycling the remainder of the string.

cyclops :: String -> String
cyclops [] = []
cyclops ('_':cs) = '+':cs
cyclops ('+':cs) = '-':cs

cyclops ('-':cs) = '_' : cyclops cs

So starting from eight nothings:-

*Main Data.Char> cyclops "________"
"+_______"
*Main Data.Char> cyclops it
"-_______"
*Main Data.Char> cyclops it
"_+______"

Function iterate will repeat as long as we want:-

*Main Data.Char> take 20 (iterate cyclops "________")
["________",
"+_______",
"-_______",
"_+______",
"++______",
"-+______",
"_-______",
"+-______",
"--______",
"__+_____",
"+_+_____",
"-_+_____",
"_++_____",
"+++_____",
"-++_____",
"_-+_____",
"+-+_____",
"--+_____",
"__-_____",
"+_-_____"]

Looking about right.

There will be 3 ** 8 different possibilities = 6561 altogether.

Monday 22 June 2015

Task Number Four Concluded

Yes I did do something wrong.  The base case of the recursion is the list of permutations of the empty list, which is not empty, because there is a permutation, that is to say the empty list itself.  So what I should have done is this:-

permutations :: (Eq a) => [a] -> [[a]]
permutations [] = [[]]
permutations xs = [ h:t | h <- xs, t <- permutations (xs `except` h) ]

*Main> permutations "HORSE"
["HORSE","HORES","HOSRE","HOSER","HOERS","HOESR",
"HROSE","HROES","HRSOE","HRSEO","HREOS","HRESO",
"HSORE","HSOER","HSROE","HSREO","HSEOR","HSERO",
"HEORS","HEOSR","HEROS","HERSO","HESOR","HESRO",
"OHRSE","OHRES","OHSRE","OHSER","OHERS","OHESR",
"ORHSE","ORHES","ORSHE","ORSEH","OREHS","ORESH",
"OSHRE","OSHER","OSRHE","OSREH","OSEHR","OSERH",
"OEHRS","OEHSR","OERHS","OERSH","OESHR","OESRH",
"RHOSE","RHOES","RHSOE","RHSEO","RHEOS","RHESO",
"ROHSE","ROHES","ROSHE","ROSEH","ROEHS","ROESH",
"RSHOE","RSHEO","RSOHE","RSOEH","RSEHO","RSEOH",
"REHOS","REHSO","REOHS","REOSH","RESHO","RESOH",
"SHORE","SHOER","SHROE","SHREO","SHEOR","SHERO",
"SOHRE","SOHER","SORHE","SOREH","SOEHR","SOERH",
"SRHOE","SRHEO","SROHE","SROEH","SREHO","SREOH",
"SEHOR","SEHRO","SEOHR","SEORH","SERHO","SEROH",
"EHORS","EHOSR","EHROS","EHRSO","EHSOR","EHSRO",
"EOHRS","EOHSR","EORHS","EORSH","EOSHR","EOSRH",
"ERHOS","ERHSO","EROHS","EROSH","ERSHO","ERSOH",
"ESHOR","ESHRO","ESOHR","ESORH","ESRHO","ESROH"]
*Main> length (permutations "HORSE")
120
*Main> 5 * 4 * 3 * 2 * 1
120
*Main> 

That's more like it.

Slipped the factorial in there just for fun: 120 permutations.

Now given a list of integers I want the value of the concatenation of their string representations: build this up...

*Main> let ns = [50, 2, 1, 9]

Convert each integer in the list into the string form, with function show:-

*Main> map show ns
["50","2","1","9"]

Now concatenate the whole list by folding the binary concatenation operator ++ into the list with "" as the base case:-

*Main> foldr (++) "" (map show ns)
"50129"

Now read this to get the integer value:

*Main> read (foldr (++) "" (map show ns))
    No instance for (Read a0) arising from a use of `read'

Aha, need to help read by specifying the destination type:

*Main> read (foldl (++) "" (map show ns)) :: Int
50219

So wrap this in a nice function:-

value :: [Int] -> Int
value ns = read (foldl (++) "" (map show ns)) :: Int

Right.  So I can now generate all the permutations and assign a single value to each one.  Finally I need the maximum value from the list.  Aha, there is already a function maximum that does this.

*Main> maximum (map value (permutations [50, 2, 1, 9]))
95021

QED (Quite Easily Done)

I haven't been keeping track but that definitely was more than an hour.

On reviewing the solution posted by the original blogger I see he went down the track of comparing strings, and spotted that the problem is made hard by the fact that the numbers can be represented by strings of different lengths.

I like this Haskell solution because you read that last line of code and it pretty much tells you what it does.

Task Number Four Continued

Well what I am feeling my way towards is a Cartesian join between the list of heads of the list ns and the permutation of the tails, where the tail is the numbers in the list except the head one.

So this is where we go for a list comprehension:-

permutations :: [Int] -> [[Int]]
permutations ns = [ h:t | h <- ns, t <- permutations (ns except h) ]

That is too honey not to be right.  There are two generators: the first one cycles through the list of elements and the second one calls the function to get the permutations of the elements of the list except the element that the first generator has just pulled out itself.  This is legitimate as the generators are evaluated left-to-right.  This works in logic so it should work in  Haskell.

However I first need that except operator:-

except :: [Int] -> Int -> [Int]
except ns x = [ n <- ns, n /= x]

*Main> [50, 2, 1, 9] `except` 2
[50,1,9]

No hang on, that would eliminate more than I want:

*Main> [3, 1 , 4, 1, 5, 9] `except` 1
[3,4,5,9]

Just one 1 should go, not all of them.   Ok let's try spelling it out:

except :: [Int] -> Int -> [Int]
except [] x = []
except (n:ns) x =
    if n == x
    then ns
    else n : (ns `except` x)

*Main> [3, 1, 4, 1, 5, 9] `except` 1
[3,4,1,5,9]
*Main> [3, 1, 4, 1, 5, 9] `except` 3
[1,4,1,5,9]
*Main> [3, 1, 4, 1, 5, 9] `except` 9
[3,1,4,1,5]
*Main> [3, 1, 4, 1, 5, 9] `except` 8
[3,1,4,1,5,9]

I'm sure there are already library functions that do all this.

That's the one.  So.  Hang on let's generalise except to take any type where you can do an equality comparison:

except :: (Eq a) => [a] -> a -> [a]
except [] x = []
except (n:ns) x =
    if n == x
    then ns
    else n : (ns `except` x)

Now my permutations function:

permutations :: (Eq a) => [a] -> [[a]]
permutations [] = []
permutations xs = [ h:t | h <- xs, t <- permutations (xs `except` h) ]

The generalised version should work on strings:-

*Main> permutations "HORSE"
[]

No hang on it's not returning anything.

*Main> permutations [3,1,4,1,5,9]
[]

Hm.  Must have done something wrong.

Task Number Four

The next problem is this.  Given a list of numbers, you can concatenate them in various orders to make a larger number.  The problem is to work out the order for a given list of numbers that will give you the largest combined number.

My first thought was that this is easy - just sort the numbers into largest first and then join them together.  This would work for say 31 41 59 - - join them in sorted order 59 41 31 and you get 594131 which is the largest possibility.

However this won't work even for the example on the page - 50, 2, 1, 9.  Put them in increasing order and you get 50921 but the largest result possible is 95021.

So is there a way to work out the largest by allowing for the fact that the numbers are different lengths?  I'm sure there is but I haven't got time to try to work that our now.  The clock is supposed to be ticking...

Therefore perhaps the way to do this is to just blindly work out the whole list of permutations of the number list and then get the maximum.

OK so if I have a list of numbers, how do I list all permutations?

Pardon me if I switch language here...

So firstly if I want all permutations I want to start with each of the numbers in turn so I want to be able to rotate my list:

rotate :: [Int] -> [Int]
rotate [] = []
rotate (x:xs) = xs ++ [x]

Now for example:-

*Main> rotate [50, 2, 1, 9]
[2,1,9,50]

So to get a list of all possible rotations of one list:-

rotations :: [Int] -> [[Int]]
rotations ns = take (length ns) (iterate rotate ns)

The function iterate produces a potentially infinite list of repeated calls of the same function: take allows us to get only as much of this infinite list as we need, which here is the number of elements
in the list so each one comes to the front once.

And for this example:-

*Main> rotations [50, 2, 1, 9]
[[50,2,1,9],[2,1,9,50],[1,9,50,2],[9,50,2,1]]

So er yes I want to rotate through the first number of the list and then combine each number with successive permutations of the remainder of the list.  Thinking recursively you see.

So perhaps I want the heads of the list and the tails of the list as separate lists:-

heads :: [Int] -> [Int]
tails :: [Int] -> [[Int]]

heads ns = ns 
tails ns = map tail (rotations ns)

*Main> heads [50, 2, 1, 9]
[50,2,1,9]
*Main> tails [50, 2, 1, 9]
[[2,1,9],[1,9,50],[9,50,2],[50,2,1]]

Tuesday 16 June 2015

All the Classics

The third warm-up test is to create the first 100 members of the Fibonacci series.

OK, so let's consider the series two elements at a time as a and b: we can initialise neatly so:

>>> a, b = 0, 1

And accumulate the series in a list called fibo which we initialise empty:

>>> fibo = []

Then loop 100 times appending each element to our list and then moving on to the next with another neat parallel assignment:

>>> for ix in range(0, 100):
...     fibo.append(a)
...     a, b = b, a+b
...

So what do we get?

>>> print fibo
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4
181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 83
2040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 18
36311903, 2971215073L, 4807526976L, 7778742049L, 12586269025L, 20365011074L, 329
51280099L, 53316291173L, 86267571272L, 139583862445L, 225851433717L, 36543529616
2L, 591286729879L, 956722026041L, 1548008755920L, 2504730781961L, 4052739537881L
, 6557470319842L, 10610209857723L, 17167680177565L, 27777890035288L, 44945570212
853L, 72723460248141L, 117669030460994L, 190392490709135L, 308061521170129L, 498
454011879264L, 806515533049393L, 1304969544928657L, 2111485077978050L, 341645462
2906707L, 5527939700884757L, 8944394323791464L, 14472334024676221L, 234167283484
67685L, 37889062373143906L, 61305790721611591L, 99194853094755497L, 160500643816
367088L, 259695496911122585L, 420196140727489673L, 679891637638612258L, 11000877
78366101931L, 1779979416004714189L, 2880067194370816120L, 4660046610375530309L,
7540113804746346429L, 12200160415121876738L, 19740274219868223167L, 319404346349
90099905L, 51680708854858323072L, 83621143489848422977L, 135301852344706746049L,
 218922995834555169026L]

Did we get them all?

>>> print len(fibo)
100

Ah yes.

Merging Lists

The next problem is to write code that will merge two lists by creating a new list that shows alternate elements from your two source lists.

The spec doesn't say what to do if the lists are not the same length. We could imagine the case where the merged list has to show members of alternate lists and so it has to stop if either of the lists stops.

Or we could have the case of a process that is handling elements from two sources in a balanced way, so if one list comes to the end it is free to continue just with the other one.

So let's do it both ways.  Starting with three lists, two the same length and one longer:-

>>> stooges = ["Curly", "Larry", "Moe"]
>>> marxes = ["Groucho", "Harpo", "Chico"]
>>> dwarfs = ["Grumpy", "Dopey", "Happy", "Larry", "Linus", "Charlie", "Bob"]

Now for the case where the merged list stops if either list has stopped - so if we get to the end of xs or ys we return the empty list: otherwise create a new list of the first two elements of the source lists and concatenate this onto the rest of the result from the recursion:-

>>> def merge_lists_1(xs, ys):
if xs == [] or ys == []:
    return []
else:
    return [xs[0], ys[0]] + merge_lists_1(xs[1:], ys[1:])

No horses were scared in the creation of that function.  Does it work?

>>> merge_lists_1(stooges, marxes)
['Curly', 'Groucho', 'Larry', 'Harpo', 'Moe', 'Chico']

And it stops when the shorter list stops:-

>>> merge_lists_1(stooges, dwarfs)
['Curly', 'Grumpy', 'Larry', 'Dopey', 'Moe', 'Happy']

Now for the other case.  If one list comes to the end then return the other list; otherwise get two elements and join to the recursion as before:

>>> def merge_lists_2(xs, ys):
if xs == []:
    return ys
elif ys == []:
    return xs
else:
    return [xs[0], ys[0]] + merge_lists_2(xs[1:], ys[1:])

Now for lists of the same length:-

>>> merge_lists_2(stooges, marxes)
['Curly', 'Groucho', 'Larry', 'Harpo', 'Moe', 'Chico']

And if one list is longer then we finish off the longer list:-

>>> merge_lists_2(stooges, dwarfs)
['Curly', 'Grumpy', 'Larry', 'Dopey', 'Moe', 'Happy', 'Larry', 'Linus', 'Charlie', 'Bob']
>>> 

Monday 15 June 2015

It's...

The boys at Programming Throwdown have drawn attention to a post by Santiago L. Valdarrama provocatively titled Five programming problems every Software Engineer should be able to solve in less than 1 hour.

Is that one hour each or one hour altogether?  Doesn't say.  Anyway I'm curious because it's a chance for me to prove that I really am as clever as I think I am.  That's the draw of a title like that, surely? You say: I will either solve the problems, thereby proving that other software engineers who can't solve them are idiots: or else I can't solve them, proving that the guy who posted the problem is the idiot.  Either way you can't lose...

Also the Throwdown team have mentioned a substitute text shell called Babun that they reckon is worth checking out.

This Babun shell comes with Python.  I've never tried Python so this is a good excuse.  I understand it is supposed to be easy to pick up, but also people do write serious systems with it.  Python has been sitting in the background of the programming world for years patiently waiting for Perl to die, and now it finds that Ruby has appeared from nowhere and claimed its patch.

Anyway, the first task is to write code that works out the sum of a list of numbers three ways, by a for loop, by a while loop, and by recursion.

So, here goes.

Start up Python from the fancy new shell:-

{ ~ }  » python  ~
Python 2.7.8 (default, Jul 28 2014, 01:34:03)
[GCC 4.8.3] on cygwin
Type "help", "copyright", "credits" or "license" for more information.

Python 2.7 classes itself as "legacy" - the current thinking is in Python version 3.  However.

Create a list of numbers with a nice easy sum:

>>> numbers = [50,25,12,7,3,2,1]

Now to use for - well, looks like Python has several way to use a for construction. First we can for over a range of consecutive numbers. Note that in Python, lists start at element zero.  Thank you, note taken.  The range you specify starts at the first number and stops before the second number you specify.  That makes it easy: to scan over all the elements of the array we do this:

>>> sum = 0
>>> for ix in range(0, len(numbers)):
...     sum = sum + numbers[ix]
...
>>> print sum
100

Using sum to accumulate the result each time of course.

>>> is the Python shell prompt at the top level, and ... is the prompt when you are inside a multi-line construction.  Block structure is defined in the syntax by the indentation.  Bold move.

There is also a for construction that gives you the elements in a collection without your having to pick an index, so alternatively we can say this:

>>> sum = 0
>>> for n in numbers:
...     sum = sum + n
...
>>> print sum
100
>>>

To run over the list with a while construction I'll use two index variables, ix to step through and iy to be the first index I don't want to see, which will be the length of the list. I set this before I go into the loop as I don't want to have to evaluate the len() function more than once if I don't have to.

So:-

>>> sum = 0
>>> ix = 0
>>> iy = len(numbers)
>>> while ix < iy:
...     sum = sum + numbers[ix]
...     ix = ix + 1
...
>>> print sum
100
>>>

Yes, I derive an obscure comfort from naming variables after Z80 registers. It's a bit like making a drink in a favourite cup or taking notes with a favourite pen.  You just know where you are, you see.

Now, lst[0] corresponds to (CAR lst) in Lisp.  You get the first element from the list.  In addition to writing lst[ix] to pick a specific element you can get sub-lists.  For example lst[1:] returns the list of elements starting after the zero element in the list - so this corresponds to (CDR lst) in Lisp. With these two in mind we can write the recursive solution that looks just like a Lisp one:

>>> def sum_list(ns):
...     if ns == []:
...             return 0
...     else:
...             return ns[0] + sum_list(ns[1:])
...
>>> print sum_list(numbers)
100
>>>

Hey, we are Python-enabled.  Cool.  Spam.

Did that take an hour?  I don't know, I lost track of time watching Babun download.

Wednesday 27 May 2015

Echo the Command Line Arguments

ok another little toy: echo the command line arguments back to the terminal:-

module Main
    where

import System.Environment(getArgs)

main = do
  args <- getArgs
  mapM_ putStrLn args

This time we want the function getArgs from the library System.Environment

This has type

getArgs :: IO [String]

so naturally enough we get a list of strings back when the action is performed.

The IO action that writes to the string, function putStrLn, has the type:

putStrLn :: String -> IO ()

So this takes a string and gives you back the IO action that writes to the terminal but does not return any value.  We want to apply this to a list of strings and get an IO action that will write all of them to the terminal.  As before this is a job for mapM_, which has the type:

mapM_ :: Monad m => (a -> m b) -> [a] -> m ()

The (a -> m b) corresponds to our String -> IO ()  and the [a] bit to our [String]

I know I'm labouring this a bit but I want to get it clear in my head.  So let's call the resulting program echoargs:

>ghc main.hs -o echoargs.exe
Linking echoargs.exe ...

>echoargs curly larry moe
curly
larry
moe


Print Working Directory

How about a tiny program that does something useful: that is, tells me what directory I am currently in...

If you simplify your DOS prompt:

>prompt $G

then it doesn't show you but it does leave more space for typing.

Right.  The program looks like this:-

module Main
    where

import System.Directory(getCurrentDirectory)

main = do
  pwd <- getCurrentDirectory
  putStr pwd

This goes in a file main.hs and defines the main indeed only module with the entry point main.

To get access to the required system call we import the system library called System.Directory but specify (in the brackets) that the only reference we want to make is to the function getCurrentDirectory.

Now our main function consists of two IO actions that are stacked one on top of the other inside the do construct, which has the overall effect of taking the first action and then the second.

The first action calls the system function getCurrentDirectory and assigns the identifier pwd to the result.

The type of getSystemDirectory is

getCurrentDirectory :: IO FilePath

In other words it's an IO action that returns a value of type FilePath - and FilePath is just a synonym for the String type, so we can display this without further manipulation using a function that takes a string parameter.

So the second action prints the value of pwd to the terminal.

ok now to compile - compile the file main.hs and specify the output file to be called pwd.exe:

>dir
 Volume in drive C has no label.
 Volume Serial Number is 6496-80C4

 Directory of C:\Users\polly\Documents\Projects\Haskell\pwd

20/05/2015  21:17    <DIR>          .
20/05/2015  21:17    <DIR>          ..
20/05/2015  21:17               131 main.hs
20/05/2015  21:04               112 main.hs~
20/05/2015  21:16             1,389 notes.txt
20/05/2015  21:14             1,309 notes.txt~
               4 File(s)          2,941 bytes
               2 Dir(s)  273,825,931,264 bytes free

>ghc main.hs -o pwd.exe
[1 of 1] Compiling Main             ( main.hs, main.o )
Linking pwd.exe ...

Now I can run it and see my working directory:

>pwd
C:\Users\polly\Documents\Projects\Haskell\pwd
>

Question and Answer

The next quickie comes from Yet Another Haskell Tutorial by Hal Daume III

We write a string asking for the user's name, and then write back out a reply containing the name:-

module Main
    where

import System.IO

main = do
  hSetBuffering stdin LineBuffering
  putStrLn "Enter your name: "
  name <- getLine
  putStrLn ("Hello " ++ name ++ " have a scone")

But first... we apply the action hSetBuffering to the standard input with the option LineBuffering
so that the input does not wait to fill a block buffer before moving on but returns as soon as it has a line of input to work with.

The next action writes the string

Then we read a line from the terminal and assign name to the return value

Now we can concatenate a new reply together and write it out.

Now, when I did this import line:

import IO

I got this message from the compiler:

main.hs:4:8:
    Could not find module `IO'
    It is a member of the hidden package `haskell98-2.0.0.2'.
    Use -v to see a list of the files searched for.

But the compiler was happy when I changed this to

import System.IO

It looks from the documentation that the one embraces the other.  Something to look up.

>ghc main.hs -o helloname.exe
[1 of 1] Compiling Main             ( main.hs, main.o )
Linking helloname.exe ...


>helloname
Enter your name:
Rocky
Hello Rocky have a scone

Wednesday 20 May 2015

FizzBuzz

This example illustrates the use of the case construction.  An expression is  evaluated and the result is matched against a sequence of possible values to determine which further expression is to be evaluated to be the  return value of the whole expression.

The underscore character is a wildcard that matches anything.

The aim is to create the fizzbuzz functions, which takes a number and returns "Fizz" if the number is a multiple of 3, "Buzz" if the number is a multiple of 5, "Fizzbuzz" if the number is a multiple of 15, and otherwise just the number.

We can evaluate the mod of the number against both 3 and 5 at the top of the function and match the results in a tuple.  We don't have to check explicitly for a multiple of 15 because multiples of 15 are the numbers that are multiples of both 3 and 5.

fizzbuzz :: Int -> String
fizzbuzz x =
    case (x `mod` 3, x `mod` 5) of
      (0, 0) -> "Fizzbuzz"
      (0, _) -> "Fizz"
      (_, 0) -> "Buzz"
      (_, _) -> show x

You know that nagging feeling that there is a better way.  Caused by the fact that the text strings Fizz and Buzz show up in two places.

We can't return the number as the final clause of the function because the return value has to be a string - we use the function show to convert a string.

The command :load will load your code into the REPL.

Therefore the function fizzbuzz has type Int goes to string:

*Main> :t fizzbuzz
fizzbuzz :: Int -> String

And I can view thr fizzbuzzes from 1 to 100 in the REPL:

*Main> map fizzbuzz [1..100]
["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11",
"Fizz","13","14", "Fizzbuzz","16","17","Fizz","19","Buzz",
"Fizz","22","23","Fizz","Buzz","26", "Fizz","28","29",
"Fizzbuzz","31","32","Fizz","34","Buzz","Fizz","37","38",
"Fizz","Buzz","41","Fizz","43","44","Fizzbuzz","46",
"47","Fizz","49","Buzz", "Fizz","52","53","Fizz","Buzz",
"56","Fizz","58","59","Fizzbuzz","61","62",
"Fizz","64","Buzz","Fizz","67","68","Fizz","Buzz",
"71","Fizz","73","74" ,"Fizzbuzz","76","77","Fizz",
"79","Buzz","Fizz","82","83","Fizz","Buzz"
,"86","Fizz","88","89","Fizzbuzz","91",
"92","Fizz","94","Buzz","Fizz",
"97","98","Fizz","Buzz"]
*Main> 

OK, but instead of seeing these in the REPL I want to print them out.  Instead of mapping to a string I want to map fizzbuzz to an IO action that writes a string to the terminal, plus a line feed.  The library function I want is putStrLn:

*Main> :t putStrLn
putStrLn :: String -> IO ()

So the function to call fizzbuzz and get the IO action to write the reulting string to the screen is the combination of these, created by function composition operator which is a dot . thus

*Main> :t (putStrLn . fizzbuzz)
(putStrLn . fizzbuzz) :: Int -> IO ()

Right, so I want to map this combined function onto the integer list 1..100. We need the right version of the map function, though, this one:

*Main> :t mapM_
mapM_ :: Monad m => (a -> m b) -> [a] -> m ()

So mapM_ will take our function that goes from an Integer to an IO action, apply this to a list of Integers, and give us back an IO action that we can plug straight into the main function, like this:

main :: IO ()
main = do
  mapM_ (putStrLn . fizzbuzz) [1..100]

fizzbuzz :: Int -> String
fizzbuzz x =
    case (x `mod` 3, x `mod` 5) of
      (0, 0) -> "Fizzbuzz"
      (0, _) -> "Fizz"
      (_, 0) -> "Buzz"
      (_, _) -> show x

So, in DOS:

>ghc fizzbuzz
[1 of 1] Compiling Main             ( fizzbuzz.hs, fizzbuzz.o )
Linking fizzbuzz.exe ...
>fizzbuzz
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
...
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz

Well, I got that right but only because I've been round this loop a few times before.