This has been sat on my pad for about a week now.

My marks for Chapter 3 of Programming in Haskell.

Exercise 1 - What are the type of the following values?

Part 1:

[ 'a', 'b', 'c' ]
-- has type 
[ Char ]

Correct

Part 2:

( 'a', 'b', 'c' )
-- has type 
( Char , Char , Char )

Correct

Part 3:

[ ( False , 'O' ) , ( True , '1' ) ]
-- has type 
[ ( Bool , Char ) ]

Correct

Part 4:

( [ False , True ] , [ '0' , '1' ] )
-- has type 
( [ Bool ], [ Char ] )

Correct

Part 5:

Here is what I thought:

[ tail , init , reverse ]
-- has type   
[ ƒ ]

I was wrong. I was unsure how to denote the type of a function within the context of the type of another function, but seeing the output from Hugs helped me realise how this is done. You denote a functions type by writing out its type, if you follow.

The correct answer: 

[ tail , init , reverse ]
-- has type   
[ [ a ] -> [ a ] ]

Incorrect

I've learned, or rather realised something from getting part 5 wrong, the way to express the type of a function. This really was a moment of realisation, as I've correctly written the type [o \rrrrrrrrrrrrrrrrrrrrrrrrrrrttttttf cat on the keyboard] of a function in my working for Problem 1 of Project Euler. It was so obvious, I couldn't see the wood for the trees.

Exercise 2 - What are the types of the following functions?

Part 1:

second xs    = head (tail xs)
-- has type 
second       :: [ a ] -> a

Correct

Part 2:

swap ( x , y ) = ( y , x )
-- has type 
swap           :: ( a , b ) -> ( a , b )

Correct (ish)

I was right in theory but I used x and y to denote the types for the arguments however; it is Haskell convention that type variables are usually a, b, c... I made this same mistake in the rest answers but as I was correct in the theory, if not the notation, I've given myself the mark.

Part 3:

pair      = ( x , y )
-- has type 
pair      :: a -> b -> ( a , b )

Again, I originally used x and y for the type variables.

Correct

Part 4:

double x    = x * 2
-- has type 
double      :: Num a => a -> a

Correct

Part 5:

palindrome xs   = reverse xs == xs
-- has type 
palindrome      :: Eq a => [ a ] -> Bool

Correct

Part 6:

twice ƒ x    = ƒ ( ƒ x )

-- has type 
twice        :: ƒ -> x

(Completely) Incorrect

I got that last one wrong! As mentioned before, not realising how to write the type of a function within the type of another function, I was looking for some way to express "argument blah is a function". Having made the realisation stated earlier, the correct answer makes complete sense.

Exercise 3 requires no formal answers but in working through my answers using Hugs I gained the understanding of how to express a function.

Exercise 4 - Why is it not feasible in general for function types to be instances of the Eq class? When is it feasible? Hint: two functions of the same type are equal if they always return equal results for equal arguments.

Answer: It is not feasible for the majority of functions to be instances of the Eq class, and therefore return the same result given the same arguments because you would rarely (if ever) implement two functions which took the same arguments and did the same thing. It might be feasible if you were writing two different implementations of a software for fail safe reasons. Maybe.

I'm not going to lie, I'm about to learn something in a moment when I flick to the PDF of answers and find out what the correct answer is.

And the winner is... 

Incorrect

The correct answer is that it's too complicated and time consuming to check all possible combinations of inputs and output of a function when it has a lot of possible inputs and outputs. It is feasible to check the equality of a function when it has few inputs and few outputs.

This was my first thought (and it's a really obvious one) but I have a tendency to over think things and get too deep into the problem. 

Marks for Chapter 3 : 9 out of a possible 12 but some important lessons learned. 

I originally did this problem about a year ago using C# so I already had the answer but in my quest to learn Haskell I've chosen to re-do it. 

I have a couple of notes I'd like to document, partly for my own benefit and partly to state my purpose. Firstly I've left the actual answer out so as not to give the entire game away. Secondly, I'm not sure on my Haskell style as yet, as this is the first program I've written. I've only read two and a half chapters or Programming in Haskell so I'm not fully l33t at it yet so I think I'm gonna reserve the right to come back in the future and amend the code below. I guess we'll see as I post some more answers and get more familiar with Haskell, and lastly, the first time I run this code in WinHugs I get the time stated below, the second and subsequent runs reports 0.0000000000000000 seconds. I've used the time greater than zero just to have a time as I'm not sure if this stuff is cached or not. As and when I learn the correct method to benchmark a Haskell script I'll update this with a more accurate time.

While I'm on about benchmarking, I'm currently working on a Dell Precision M4400 running a Core 2 Duo P8600 (2.4GHz) with 4GB ram, a 500GB 7200rpm Seagate Momentous disk all running Windows 7 Pro 64Bit. It get's a 5.9 on the Windows Experience Index with the lowest score coming from the.

 

This will be the same hardware for all the timings unless I get something new from but I doubt that for a while.

So without further ado. here is my solution for Problem 1.

-- Project Euler - Problem 1
-- http://projecteuler.net/index.php?section=problems&id=1
-- If we list all the natural numbers below 10 that are 
-- multiples of 3 or 5 we get 3, 5, 6 and 9. 
-- The sum of these multiples is 23.
--
-- Find the sum of all the multiples of 3 or 5 below 1000.
--
-- 08/09/2010
--
-- Time taken: 0.0312002000000000 sec

import Text.Printf
import Control.Exception
import System.CPUTime


-- program

isMultiple		::	Int -> Int -> Bool
isMultiple n x	= 	(x `mod` n) == 0

is5				::	Int -> Bool
is5 x 			=	isMultiple 5 x

is3				::	Int -> Bool
is3 x			=	isMultiple 3 x


problem1		::	[Int] -> Int
problem1 []		= 	0
problem1 (x:xs)		=	if is3 x || is5 x
					then
						x + problem1 xs
					else
						0 + problem1 xs



-- utils

time 			::	IO t -> IO t
time a 			=	do
    start <- getCPUTime
    v <- a
    end   <- getCPUTime
    let diff = (fromIntegral (end - start)) / (10^12)
    printf "Computation time: %0.16f sec\n" (diff :: Double)
    return v
 
main 			=	do
    putStrLn "Starting..."
    time $ problem1 [1..999] `seq` return ()
    printf "Result: %d\n" (problem1 [1..999])
    putStrLn "Done."

 

 

 

 

I found time last night to read the second chapter of Programming in Haskell. Here are my results for the exercises:

Exercise 1 - Parenthesise the following arithmetic expressions.

Part 1:

 2 ^ 3 * 4
-- becomes
 ( 2 ^ 3 ) * 4

Correct

Part 2:

 2 * 3 + 4 * 5
-- becomes
 ( 2 * 3 ) * ( 4 * 5 )

Correct

Part 3:

 2 + 3 * 4 ^ 5
-- becomes
 2 + ( 3 * ( 4 ^ 5 ) )

Correct

Exercise 2 - No solution required.

Exercise 3 - The script below contains three syntactic errors. Correct these errors and check your script works properly using Hugs.

 N = a 'div' length xs
     where
      a = 10
     xs = [1, 2, 3, 4, 5]

-- becomes

 n = a ‘div‘ length xs
     where
       a = 10
       xs = [1, 2, 3, 4, 5]

The issues are:

1. The function name N is upper case and should be lower case.
2. The function call 'div' is enclosed in the wrong type of quotation marks.
3. The local definitions for a and xs are incorrectly indented. 

Correct

Exercise 4 - Show how the library function last that selects the last element of a non-empty list can be defined using the functions introduced in this chapter.

Part 1:

-- first definition of last
last xs = head reverse xs

Incorrect

I get a compile error in Hugs as I did not parenthesize the call to reverse xs. The code should have looked like this:

last xs = head ( reverse xs )

Part 2:

-- second definition of last
last xs = xs !! n
          where 
            n = ( length xs ) -1

The example given is more concise than my version but is fundamentally the same:

last xs = xs !! (length xs − 1)

Correct

Exercise 5 - Show how the library function init that removes the last element from a list can be defined in two different ways.

Part 1:

-- first definition of init
init xs = take n xs
          where
            n = ( length xs ) - 1          

Again, the solution defines the number to take without using a local definition but the formula is essentially the same, and I think I like the where syntax better than in-lining everything.

Correct

Part 2:

-- second definition of init
init xs = reverse tail reverse xs

Incorrect

I've made the same mistake here that I made in exercise 4. I haven't correctly parenthesized my function calls and as such I get Type error:

ERROR file:{Hugs}\packages\hugsbase\Hugs.hs:13 - Type error in application
*** Expression     : reverse tail reverse xs
*** Term           : reverse
*** Type           : [e] -> [e]
*** Does not match : a -> b -> c -> d

 

Conclusion

That makes me 8 out of a possible 10 for chapter 2. I can't say I'm surprised as I only just checked my working in Hugs as I was writing this post. I didn't have the laptop turned on last night so I didn't actually do Exercise 2. If I had, I might have learned the parenthesization of function calls before going on to complete the other exercises. This will be a lesson to myself.

I just read the first chapter of Programming in Haskell by Graham Hutton, afterwhich I watched the accompanying lecture by Erik Meijer on Channel 9. I then did the exercises from the end of the chapter. Here are my results.

Exercise 1 - Give another possible calculation for the result of double ( double 2 ).

    double ( double 2 )  
 =     { applying the outer double }
    ( double 2 ) + ( double 2 )
 =     { applying second double }
    double 2 + ( 2 + 2 )
 =     { applying the first double }
    2 + 2 + 2 + 2
 =     { applying plus }
    8

This isn't in the official solutions document but I can't see how it's invalid. If I find out otherwise I'll update this post. For now I'm giving myself a mark for this exercise.

Correct

Exercise 2 - Show that sum [x] = x for any number x.

    sum [ 3 ]
 =    { applying sum }
    3 + ( sum [] )
 =    { applying sum }
    3 + 0
 =    { applying plus }
    3

I marked myself as correct for this as the working out is right however I did make a note to myself that, when proving something for x, the working out should use x. In my working out I have an assumed a that x is 3.

Correct

Exercise 3 - Define a function product that produces the product of a list of numbers, and show using your definition that product [ 2. 3. 4 ] = 24.

Part 1 - define product

product [ ]        =  1
product [ x : xs ] =  x * ( product xs )

Now I originally had product [ ] = 0, but realised quickly as I was doing my working out that anything multiplied by zero equals zero, and therefore the identity of multiplication is 1. Therefore the product of the empty list must be 1.

Part 2 - proof that product [ 2, 3, 4 ] = 24.

    product [ 2, 3, 4 ]
 =     { applying product }
    2 * ( product [ 3, 4 ] )
 =     { applying product }
    2 * ( 3 * ( product [ 4 ] ) )
 =     { applying product }
    2 * ( 3 * ( 4 * ( product [ ] ) ) )
 =     { applying product }
    2 * ( 3 * ( 4 * 1 ) )
 =     { applying * }
    24

Marked as Correct, but with the note that the identity of multiplication is 1.

Exercise 4 - How should the definition of the function qsort be changed so that it produces a reverse sorted version of the list? 

I got this correct from a logic point of view, but I think my lecturer (if I had one) might have mentioned that did a bit more than was asked, I defined a new function rqsort (for reverse qsort) rather than just showing the change I would have made to qsort. Not incorrect but not exactly what was asked.

rqsort [ ]        =  [ ]
rqsort [ x : xs } =  rqsort larger ++ [ x ] ++ rqsort smaller
                     where
                        smaller = [ a | a <- xs, a <= x ]
                        larger  = [ b | b <- xs, b > x ]

Correct

Exercise 5 - What would be the effect of replacing <=  by < in the definition of qsort?

The effect of replacing <= by < in the definition of qsort would be that any elements from the input list would only appear a single time in the resultant list. This is because we are removing the the logic that allows elements of equal value to the first element to be added to the resultant list.

Marked as Correct.

So that's five out of five for my first lesson, but with a few notes to take on board for next week.