Euler Down

Euler, problem #3: What is the largest prime factor of the number 600851475143 ?

main = do {
  print (factors 1300); -- demonstrate factor lists
  print (last (factors 600851475143))
}

factors :: Integer -> [Integer]
factors num = factorise num 2


My solution is to produce a stream of factors, starting with the lowest. As you can see, I hand off from ‘factors num’ to ‘factorise num 2′. In order to test different factor values I need to include them (the factor values) in the method. I am using the value 2 (or ‘factor’ below) as a primitive state object. It only ever contains one value. It is incremented and passed down to further calls to factorise, and it is not returned. BUT it is definitely a state.

Before I would use multiple definitions for a method, with pattern matching to decide which definition would be used. The ‘pipe’ method below is the exact same thing, we just dont have to type ‘factorise num factor’ two extra times. And we don’t have to define num+factor for our conditionals. Also, the pipe visually associates all the definitions, making it more readable.

The matchers present a test – some pattern or condition – followed by a definition (stuff after the equals). The last matcher is the keyword ‘otherwise’, which will match all the leftovers.

factorise :: Integer -> Integer -> [Integer]
factorise num factor
  | factor > num = []
  | (mod num factor == 0) = factor : factorise (div num factor) factor
  | otherwise = factorise num (factor+1)


This method returns a list of integers. When the factor is greater than the num, it returns an empty list. When the factor moduloes to zero, then we put it in the front of the list, and try again. Finally, if the factor moduloes to non-zero, we need to try a different factor – so increment the current factor.

This is not an efficient method. The best improvement would be to replace the (factor+1) with something like ‘(nextPrime factor)’. We don’t need every single number, we should be able to skip just to the primes.

So I guess thats my next challenge, to create a state object that skips to the primes.

Euler Up

My goal du jour is to solve some Euler problems.  I’ve been through this once before with scala, so the problems themselves are clear.  Just doing the same thing with haskell is in question.

I am tackling euler #2:  http://projecteuler.net/index.php?section=problems&id=2 Sum up all even values in the fibonacci sequence below 4 million.

Here is the core of my solution, a sequence that produces fibonacci numbers.  I wish I had a ‘zipWith’ function in scala; it sure cleans up the the ‘tuple bubble’ problem (see the end of this post).

• fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Here is how it works:  The first two values are defined zero and one.   All subsequent values are produced by a sequence generated by zipWith().  This function takes two sequences and produces a third sequence.  In this case the two inputs are the fibonacci numbers and the fibonacci numbers SKIPPING the first element (=tail).  We apply the plus operation to each pair of values from the two sequences.  The result is that zipWith() produces first (0+1) … then (1+1) … then (1+2) …  and so on.  This wonder works due to the magic of lazy loading (as in, don’t do no work until you need a number).

The rest of the solution is fairly prosaic.  Take all fibonaccis beneath some limit:

• fiblist limit = takeWhile (<limit) fibs

Take the stream of fibonaccis, filter out the evens:

• evenlist limit = filter even ( fiblist limit )

Sum up all values in the fibonacci stream:

• solve limit = foldr (+) 0 (evenlist limit)

Print the solution:

• main = print ( solve 4000000 )

Of course the commands are ass-backwards from my euler-002.hs file.  Main comes first, and the fibs definition is last.  And we could pump most of it into a single line … but who can read that?

What is this ‘tuple bubble’?   In scala the closest thing to zipWith() is the zip().  You can combine two streams, but instead of applying a function to paired elements, it produces a stream of tuples.  A tuple is an object, so it uses up memory and processing power.  Rudimentary benchmarking in scala show that traversing two arrays and applying a function is up to 40 times faster than producing a tuple and then processing it.

So I think my next mini-project will be to build a zipWith() for scala.  Meet me over in my other blog to see the results.
http://fwhaslam.wordpress.com/2010/04/21/zipwith-challenge/

Colon Scope

Lets talk a little bit about declaring functions.

rx :: [a] -> a -> [a]
rx [] r = [r]
rx (x:xs) r = x : rx xs r

It is not entirely obvious what the various bits are, so let’s use some long names to make it more readable.

myInfix :: [something] -> something -> [something]
myInfix [] atEnd = [ atEnd ]
myInfix (listHead:listTail) atEnd = listHead : ( myInfix listTail atEnd )

Something magical and weird is happening at the double colon ::  We are declaring the type for our method myInfix.  If this were another language, we would think about the type declaration as:  My Function takes a List and an Element, then produces another List.  If that were the case, we would expect to see the following:

• myInfix :: ( [something] , something) -> [something]

But that conception is false.  Instead, we are saying:  My Function takes a List, then produces another (invisible) Function which takes an Element, which in turn produces a List.  So we can conceptually group that as follows:

• ( (myInfix :: [something]) -> something ) -> [something]           – but do not actually group this way, as it won’t compile

Next to consider ::  ’something‘ is not an actual type.  Instead it represents any type that we decide to use with the function.  The fact that ‘something‘ is mentioned in three places does create a constraint.  We must use and expect the same type in each of the three places.  So the following examples work:

• myInfix [1,2] 6    produces [1,2,6]
• myInfix “hi” ‘o’   produces “hio”

But the following fail:

• myInfix [1,2] ‘n’
• myInfix[False,True] 8

The Fix is In

So I’ve been playing with the infix operator.  Note that haskell has functions and operators and other syntax stuff that I’m not paying attention to yet.  Operators seem to exist at the compiler level; while Functions are defined in some module and are built out of operators and other syntax stuff.   Operators include things like add(+), subtract(-), multiply(*), divide(/), and power(^); while Functions include things like head, tail and last.

Let’s talk about two of the list operators:  infix (:)  and concat(++).  Here are some examples of them at work:

• 1:[]   produces   [1]
• 1:2:[]   produces  [1,2]
• 1:[2..4]   produces  [1,2,3,4]
• ‘a’:['b','c']   produces  ”abc”   (which is equivalent to ['a','b','c'])
• [1,2]  ++ [3,4]   produces   [1,2,3,4]
• []  ++  [5,3,1]   produces  [5,3,1]
• “hi” ++ “there”   produces  ”hithere”

Here are some examples that produce errors:

• 1:2
• []:1
• 1 ++ [2,3]
• [5,4,3] ++ 8
• 1:”hi”
• [1,2]++”there”

So, infix only works with an element of some type and a list of the same type.   While concat only works with two lists of the same type.

I then went looking for an operator to handle the ‘element on the right’ case for infix, but I couldn’t find one.  So, I made the following (which ONLY handles the case of list followed by element):

rx :: [a] -> a -> [a]

rx [] r = [r]

rx (x:xs) r = x : rx xs r

I tear apart a list one element at a time until I hit the empty list, then I reconstruct it backwards.  Tada!

• rx [1,2,3] 8   produces [1,2,3,8]
• [2,3]  `rx` 1   produces [2,3,1]
• rx “hi” ‘o’   produces “hio”
• rx [3,6] -1   produces an error = No instance for (Num (t -> [t]))     arising from a use of `-’ at …
• rx [3,6] (-1)   produces [3,6,-1]

The error results from providing the minus operator as an input to my function.   While it looks like it is attached to the one, it is actually parsed as a separate element.  Including the parentheses forces the subtract one to resolve into minus one.

Oh, and here is the mo’ betterer implementation

• let rx list right = list ++ [right]

Out of Sorts

My next goal is to implement some sorting algorithms.  As a first step I am having a look at sorting examples.  Here is an implementation of the popular quicksort:

quicksort [] = []
quicksort (x:xs) =  [y|y<-xs,y<x] ++ [x] ++ [y|y<-xs,y>x]

There is a log going on in these two lines.  It took me a while to sort everything out.  Let’s start at the top and work our way down:

• quicksort [] = []

The first line simply states that sorting an empty list will produce an empty list.  Pretty intuitive.

• quicksort (x:xs) = …

The special notation (x:sx) will match a list, and break it into two variables:   x = head(list)  xs = tail(list) .   So internally the values x and xs become …

• quicksort [1,2,3]
• x = 1      and     xs = [2,3]

Not so intuitive, but sensible.  The next statement can be broken into three parts:

• [y|y<-xs,y<x] ++ [x] ++ [y|y<-xs,y>x]
• A list of everything in xs less than x ++    a list which only contains x ++   A list of everything in xs greater than x

The connecting ++ values will append lists together.  This is why the central piece is a list containing x.  The outer pieces are ‘list comprehensions’.  They resemble mathematical expressions, but are not identical.

• [ y | y<-xs, y<x ]
• a list of y such that    y is a member of xs and    y is less than x

My interpretation of <- as ‘member of’ is not really accurate.  In haskell a better interpretation would be ‘each member in turn’.  The difference was obvious when I did the following experiment:

• [ y | y <- [1,2,3] ,   y<-[2,3,4]  ]
• Expected Math Solution = [2,3]
• Haskell produces [2,3,4,2,3,4,2,3,4]    (why?  we traversed xs from 1 to 3, then for each element also traversed the list 2,3,4 producing 9 elements)

Compile Post

You can compile your *.hs files using the ghc utility.  Your file should define some module; but you can use the default module Main with no declarations.  You simply need to create a main function which returns an IO Monad:

• main = print( “Hello World” )

Compile and run as follows:

• ghc my-haskell-file.hs
• ./a.out

For all the stuff I am not bothering with right now, do this:

• ghc –help

My-Haskell-File.hs and Editing

Haskell files are extended as *.hs.  Any text editor can be used, although Aquamacs has some language support.  You can load a file into ghci at launch time:

• ghci my-haskell-file.hs

This will load as a default module named Main.  All function declarations are read from file and become accessible via ghci command (no let keywords necessary).

The module Main seems to include a default reference to a function main.  If your file deines a function main then it must return some type of IO monad.  Below are two examples, the first succeeds, the second fails.

• main =  print ( fib 10 )   — loads successfully
• main = fib 10    — fails to load

Using a file, I can now create multiple line functions; like fibonacci below.  When I was just using ghci commands, the second ‘let fib ..’ would remove the first ‘let fib..’

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

You can edit your file via ghci as follows:

• :set editor vi
• :edit
• :reload

But instead, I recommend you use simply edit with an external tool, then :reload as you make changes.

Simple Simon Sequences

I love infinite sequences.  They are often the most correct way to think about a problem.  Obviously you can’t retrieve an entire sequence, but haskell gives you some tools to retrieve partial sequences.  The following will both return the list of numbers from 1 to 100:

• take 100 [1..]
• takeWhile(<=100) [1..]

The list syntax provides easy ways to generate simple sequences.  Simply leave off a terminating value:

• [1,1..]   — nothing but ones
• [1,3..]   — the odd numbers
• [5,9..]   — every other odd number starting at 5

I also to produce sequences using (lazy) recursive methods.  Note that my methods end with an ‘s’.  This seems to be a haskell convention.

• let ones = 1 : ones   — nothing but ones
• let odds = 1 : map (2+) odds   — odd numbers
• let fivems = 5 : map (4+) fivems

Here is one of the worst possible ways to generate a sequence of square numbers:

• let ones = 1 : ones
• let odds = 1 : map (2+) odds
• let squares = 0 : zipWith (+) odds squares

Mo’ betterer square sequence:

• let squares = map (^2) [1..]

Let It Be

I am able to do simple operations in ghci. Each of the following produces a logical result:

• 1
• 1+2
• [1,2]
• 1:[2]
• [1..10]

But I am initially unable to create functions.  This is especially annoying as I try to copy+paste examples from http://projecteuler.net/   I am trying to make a super-simple sequence to produce odd numbers:

• odds = 1 : map (2+) odds

When I enter this as a command in ghci, it tells me:

<interactive>:1:5: parse error on input `=’

It turns out that the line is valid when it is part of a haskell file, but needs a preceeding ‘let‘ command in ghci.

• let odds = 1 : map (2+) odds
• take 100 odds

Tada!  An infinite sequence of odds produced by a self-referential generator.  I know that the following is simpler, but that is not the point.

• [1,3..]

Getting Started with Haskell

My journey with haskell starts with installing the Glorious Glasgow Haskell Compilation System.  I worked from the following post: http://www.haskell.org/haskellwiki/Mac_OS_X  Once this is on your system you have two tools (that I know of):

• ghc – a compiler that builds executables from *.hs files
• ghci – a command line interpreter

My next step was to start reading the “Gentle Introduction to Haskell” from http://www.haskell.org/tutorial/index.html

Next I fired up the command line ghci and started interacting with haskell. My first problem was that I could not exit the application. After some reading up I discovered that all the meta-commands are preceeded by a colon. So my micro-lesson du jour is this:

• :help – to figure things out
• :quit – to run away screaming