Haskell — Day Two -- Charlie Harvey

Day two of the Haskell section has been once again very challenging for me. I’m sure that some of the conceptual territory would be easier to navigate were I a proper mathematician. But, after some head/keyboard bashing and rather more than my usual couple of hours allotted to Seven Languages In Seven Weeks sessions I managed to get most of the excercises done, except the string splitting excercise, which I’m going to have a crack at in another session.

There have been a few times when I’ve felt annoyed at Haskell’s strong typing, but its actually kept out of my way most of the time, in contrast to my experience of Scala where I was fighting the type system all the way. The syntax is elegant when I can get my head round what is going on and I’m feeling rather smug about a couple of the functions that I’ve written. The other thing that I’ve noticed is that Haskell is nippy. Even the REPL is pretty darned fast. That is very different from Clojure, where I had to wait for the JVM startup when I was running from the CLI (though it was less of an issue from the REPL). Apparently Haskell code compiles to rather efficient binaries, not quite as fast as C but not far off. That’s one reason for the strong typing.

Like I said, Day Two stretched me a fair bit. The material that Tate covers includes

Higher order functions, lambdas, maps, folds, zips and zipWiths
Partially applied functions and function currying
Function composition
Lazy evaluation

Haskell is clearly a language that is very geared towards higher order functions. Lambdas are almost trivial and frequently used in a lot of the sites that I’ve browsed. I thought that I got function composition, but the 4th homework assignment made me doubt that. Lastly, lazy evaluation is easy to do but not necessarily easy to understand. But very cool.

qsort.hs

Write a sort that takes a list and returns a sorted list

I started off by rewriting what seems to be the canonical sort in Haskell, quicksort. But then I started playing around a bit and came up with a (sort of actually more bubbly) insertion sort that is rather elegant in how it is written, perhaps less so in how it runs. It relies on the insert function from Data.List within a right fold. I’ll let the CS folks work out its big Oh. It seems OK on the lists that I can be arsed to type. The ease of quicksort implementation has sort of blown my mind, by the way.module Main where import Data.List quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = (quicksort lt) ++ [p] ++ (quicksort gt) where lt = filter (< p) xs gt = filter (>= p) xs insertionsort :: Ord a => [a] -> [a] insertionsort = foldr insert []

Let’s take them for a testdrive.Prelude> :load qsort.hs [1 of 1] Compiling Main ( qsort.hs, interpreted ) Ok, modules loaded: Main. *Main> quicksort [9,1,3,8,2] [1,2,3,8,9] *Main> insertionsort [9,1,3,8,2] [1,2,3,8,9]

mysort.hs

Write a sort that takes a list and a function and returns a sorted list.

I reused my quicksort code, got very stuck on the syntax I needed to use, then finally realized this was exactly how one should use function compositions (in not . cmp). The cmp function (named for perl’s) should return true if the other element is greater than or equal to the first, or false otherwose. I’d not really taken on board the fact that you could implement the Ordering type when I wrote it. I guess one could pass in a cmp function that used compare though.module Main where mysort :: (a -> a -> Bool) -> [a] -> [a] mysort _ [] = [] mysort cmp (p:xs) = (mysort cmp lt) ++ [p] ++ (mysort cmp gte) where lt = filter (not . cmp p) xs gte = filter (cmp p) xs

The run is as expected. *Main> :load mysort.hs [1 of 1] Compiling Main ( mysort.hs, interpreted ) Ok, modules loaded: Main. *Main> mysort (\x y -> if y>=x then True else False) [9,1,3,8,2] [1,2,3,8,9] *Main>

atof.hs

Write a Haskell function to convert a string to a number. The String should be in the form of $2,345,678.99 and can possibly have leading zeros

My implementation here is rather sketchy, though it does meet the spec. I just wouldn’t use it in real life. It would, for example, break if it were to encounter a pound sign. I really wanted a filter where I could say "filter (not isDigit and not == '.')" — maybe that exists. In this implementation, I filter out $ signs, then take that output and filter out commas then take that and drop leading zeros, then use the read function to convert to a double. Again, this seemed to me what function composition was made for. If you spotted the reference to C, then good for you ;-)atof :: String -> Double atof str = read $ dropWhile (=='0') $ filter (/=',') $ filter (/='$') str

*Main> :load atof.hs [1 of 1] Compiling Main ( atof.hs, interpreted ) Ok, modules loaded: Main. *Main> atof "$2,345,678.99" 2345678.99 *Main> atof "$0002,345,678.99" 2345678.99 *Main> atof "000$2,345,678.99" 2345678.99 *Main>

num_composition.hs

Write a function that takes an argument x and returns a lazy sequence that has every third number, starting with x. Then write a function that includes every fifth number, beginning with y. COmbine these functions through composition to return every eithth number, beginning with x+y.

Like I said, I think I misunderstood how function composition works, so I ended up just using zipWith rather than function compostion.module Main where i3 x = [x, (x+3) ..] i5 y = [y, (y+5) ..] i8 x y = (zipWith (+) (i3 x) (i5 y))

Here comes the science. *Main> :load num_composition.hs [1 of 1] Compiling Main ( num_composition.hs, interpreted ) Ok, modules loaded: Main. *Main> take 5 $ i8 0 1 [1,9,17,25,33] *Main>

partial_app.hs

Use a partially applied function to define a function that will return half of a number and another that will append \n to the end of any string.

This time the nod is to VBScript rather than to C. After such mind benders this seemed straightforward. I was worried that I may have missed something. As you can see I also made the lf and crlf functions for the sake of completeness. Or something.module Main where half = (/ 2) cr = (++ "\n") lf = (++ "\r") crlf = cr . lf

This yields*Main> :load partial_app.hs [1 of 1] Compiling Main ( partial_app.hs, interpreted ) Ok, modules loaded: Main. *Main> cr "Charlie roolz" "Charlie roolz\n" *Main> crlf "Charlie roolz" "Charlie roolz\r\n" *Main> half 10 5.0 *Main>

Extra Credit Part One

These extra problems were presented as well. I shall probably have a crack at the last three another day. I did the first two which were both a bit mathematical for my taste.

gcd.hs

Write a function to determine the greatest common denominator of two integers.

I did what I always do when someone asks me a maths question and looked it up on Wikipedia. Well, Wikipedia has a recursive implementation of "the Euclidean algorithm" in pseudocode. So I nicked that and turned it into Haskell. Which is maybe not the brainy thing to do. But then again I’m finished now, so maybe it is.module Main where mygcd x 0 = x mygcd x y = mygcd y (x `mod` y)

That is kind of beautiful, innit? And it works as advertised. *Main> :load gcd.hs [1 of 1] Compiling Main ( gcd.hs, interpreted ) Ok, modules loaded: Main. *Main> mygcd 90 300 30 *Main> mygcd 54 24 6 *Main>

primes.hs

Create a lazy sequence of prime numbers

I laughed out loud when I read this. You see, back in the mists of time, I applied for a Java programming job where one of the interview questions was "how would you find the prime numbers between one and a million". Apparently "with Google" wasn’t the answer they were looking for and I didn't get the job. However, I did learn about the Sieve of Eratosthenes, which has been entirely useless to me for most of my adult life. Until now. The tricky bit was applying the sieve to an infinite set, and when I figured out that you could do it with a list comprehension and then it worked I felt proper smug about it.myprimes = sieve [2..] where sieve (p:rest) = p : sieve [x|x <- rest, x `mod` p > 0]

*Main> :load primes.hs [1 of 1] Compiling Main ( primes.hs, interpreted ) Ok, modules loaded: Main. *Main> take 10 myprimes [2,3,5,7,11,13,17,19,23,29] *Main>take 100 myprimes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541] *Main>So, yes it works. Though I imagine it won’t be hugely efficient, being as it has to look up the mods of all those xs all the time. Well, as we all know, premature optimization is the root of all evil, right?So, yes it works. Though I imagine it won't be hugely efficient, being as it has to look up the mods of all those xs all the time. Well, premature optimization is the root of all evil, right?

Signing off

For now that is all, though I still have a couple more excercises to complete. Day two is hard. But I have had a lot of fun.