Seven Languages In Seven Weeks: Haskell - Day 2
I just finished day 2 of Haskell from my Seven Languages in Seven Weeks book. Today, Tate actually talked about a lot of the stuff that I talked about yesterday; so, reading this section, I felt that I was already a little ahead of the game. And, as I said before, languages like Haskell really do show you how awesome it can be to work with lists.
The homework problems in this section were broken up into two parts: the homework, and then the more "challenging" homework. Due to a late meeting at the office, I wasn't able to start my homework until much after I would have hoped. That, and the fact that the basic homework felt quite challenging on its own, didn't leave me time to tackle the "challenging" problems.
HW1: Write a sort that takes a list and returns a sorted list.
Honestly, I don't enjoy writing sorting algorithms. Other than the bubble sort - the least efficient of all sorting algorithms - I've never internalized the way they work; and as such, I tend to have to look them up each time that I want to use them. And, when it comes to a new language, like Haskell, that basically means copying exactly what someone else did.
So, rather than simply going all "stenographer" on the problem, I chose to use it as an opportunity to learn more about the core Haskell libraries. As with most compiled languages, there is a set of core libraries that get automatically linked. Beyond that, there are a large number of libraries that can be manually imported. For this problem, I needed to import the Data.List module in order to gain access to the native sorting functions.
-- Write a sort that takes a list and returns a sorted list.
-- Define our module.
module Main where
-- Import the List module which has native sorting functions.
import Data.List
-- Sort the list using the native sortBy and custom comparator.
-- Haskell uses the Ordering data type as the comparator return
-- value: LT, GT, EQ.
--
-- In the following signature, we are setting the "constraint"
-- that all values of "a" must be of an "orderable" type. This
-- is because we are using a comprator.
sortList :: (Ord a) => [a] -> [a]
-- Sort the list using the native sortBy.
sortList list =
sortBy
(\a b -> if (a < b) then LT else GT)
list
As you can see here, I am importing the Data.List module such that I can have access to the native "sortBy" function. The sortBy function uses a comparator method in order to sort the values in the list. The comparator method needs to return an instance of the Ordering class. So, rather than returning -1, 0, or 1, the comparators in Haskell return instances of LT, EQ, and GT.
That took me a while to figure out; but, what took even longer than that was trying to figure out the method signature of my sortList function. It takes a list and returns a list; but, after much Googling, I figured out that it also needed a "constraint." If you look at the method signature above, you'll see that it starts off with:
(Ord a)
What this "constraint" is saying is that this while this function accepts and returns a list of "a" types, those types must uphold the orderable interface; that is, they must be sortable. You can't just pass any old lists to this function - those lists need to conform to a certain interface.
This took me a good 30 minutes to figure out. The irony of this is that if you simply leave out the method signature, the sortList() method worked fine. Method signatures seem to be a double-edge sword - they provide more information; but, you can also shoot yourself in the foot pretty quickly if you try to "guide" the compiler.
Anyway, when we load the above code and run it, we get the following console output:
Prelude> :load hw1.hs
[1 of 1] Compiling Main ( hw1.hs, interpreted )
Ok, modules loaded: Main.
*Main> sortList( [ 1, 10, 4, 5, 8, 2, 9 ] )
[1,2,4,5,8,9,10]
As you can see, our list has been sorted.
HW2: Write a sort that takes a list and a function that compares its two arguments and then returns a sorted list.
In the first problem, my comparator was encapsulated within the function. This time, we are simply writing a function that requires that the comparator be passed-in.
-- Write a sort that takes a list and a function that compares its
-- two arguments and then returns a sorted list.
-- Define the module.
module Main where
-- Import the List module which has native sorting functions.
import Data.List
-- Our function simply acts as a proxy to the native sort
-- function that does exactly the same thing.
sortList :: (Ord a) => (a -> a -> Ordering) -> [a] -> [a]
-- Sort the list using the given comparator.
sortList comparator list = sortBy comparator list
By passing-in the comparator, you can see that our method signature now has to contain the signature of the comparator method itself. When we load the above code and run it, we get the following console output:
*Main> :load hw2.hs
[1 of 1] Compiling Main ( hw2.hs, interpreted )
Ok, modules loaded: Main.
*Main> sortList (\a b -> if (a < b) then LT else GT) [ 1, 10, 4, 5, 8, 2, 9 ]
[1,2,4,5,8,9,10]
Just as in the first problem, our comparator function is a lambda (a.k.a. anonymous) function.
HW3: 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.
When I read this problem, I thought, "Sweet! - this is gonna be easy!" I thought this, because the concept is so simple and would be wicked easy in all the programming languages that I know:
- Step 1: Strip out the non-numeric characters (ie. "$" and ",").
- Step 2: Convertthe result string to a number.
My first instinct was to use regular expressions. With the character class [$,] I could quickly strip out the unwanted characters. Unfortunately, it looks like the regular expression support in Haskell is not so stellar. Or, at least, nobody uses it. I couldn't find a single online tutorial about how to use regular expressions to replace values. I found one or two tutorials on how to use RegEx to search a string (using absurdly complex compiler hinting); but, nothing on replace.
My next thought was then just to use a standard string replace approach. Well, it looks like this wasn't so easy to find either. I refuse to believe that a language doesn't have solid string-replace support; so I'm just going to chalk this one up to a case of poor Googling techniques.
What I finally had to do was use the foldl() function to fold the original string into the new string:
-- Write a Haskell function to convert a string to a number. The
-- string should bein the form of $2,345,678.99 and can possibly
-- have leading zeros.
-- Define our module.
module Main where
-- Convert the incoming dollar string to a float.
parseDollar :: String -> Float
-- When doing this, we are going to map the incoming string
-- onto a new string in which the "$" and "," have been
-- stripped out.
--
-- NOTE: When reading the value (read), we need to supply the
-- compiler with a hint (:: Float) as to the type of conversion
-- that we are performing.
parseDollar value = read strippedValue :: Float
where
-- Set the stripped value as the incoming string with
-- the special characters replaced.
strippedValue =
foldl
(\ newString c ->
if (c == '$' || c == ',') then
newString
else
newString ++ [c]
)
""
value
As you can see, I am building the new string - strippedValue - by copying each character of the old string into the new one, skipping, of course, the characters that I don't want. Then, once I had the stripped value, I am parsing it into a Float.
The string-to-number conversion is being done by the read() method. This also took me a long time to figure out because you need to provide the compiler with some insight (ex. ":: Float") as to what kind of conversion you are performing. So, it's kind of like the read() method is a verbose form of "cast".
Anyway, when we load the above code and run it, we get the following console output:
*Main> :load hw3.hs
[1 of 1] Compiling Main ( hw3.hs, interpreted )
Ok, modules loaded: Main.
*Main> parseDollar( "$2,345,678.99" )
2345679.0
As you can see, it worked quite nicely. I have to say, though, that this problem shook me up a bit. The problem was so seemingly simple and yet it took me a really long to solve it. I know, I know, I know this is only my second day with the language; but, I couldn't help but feel like some really basic types of functionality (ie. regex replace, string replace) were missing... or, at least, are very well hidden.
HW4: 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 eighth number, beginning with x + y.
-- 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 two functions through composition to
-- return every eigth number, beginning with x + y.
-- Define our module.
module Main where
-- I return an infinite range starting at X and then
-- selecting every 3rd valud after that.
every3rd x = [x, (x + 3) ..]
-- I return an infinite range starting a Y and then
-- selecting every 5th value after that.
every5th y = [y, (y + 5) ..]
-- For our "8th" version, we are going to take the result
-- of both our 3rd and 5th lists and then zip them together,
-- adding each value to the other.
every8th x y =
(zipWith (+) (every3rd x) (every5th y))
Both Haskell and Clojure have this idea of lazy sequences. These are sequences whose values don't get evaluated until they are needed. So, in this case, we can create an infinite sequenze without crashing the computer or running out of stack space. Actually, we're creating two infinite sequences and then zipping them together (taking the values of each list and combining them using a zipping function).
When we load the above code and run it, we get the following console output:
*Main> :load hw4.hs
[1 of 1] Compiling Main ( hw4.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 10 (every8th 10 20)
[30,38,46,54,62,70,78,86,94,102]
The take() method allows us to take one of these infinite, lazy sequences and pop off N values (in this case, 10).
HW5: 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.
Earlier, I was talking about how Haskell implicitly curries almost all of its function calls. As the programmer, you can also do this explicitly by invoking a method with an incomplete number of arguments. This will result in a curried function in which the supplied arguments are now embedded within the execution logic.
-- 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.
-- Define our module.
module Maine where
-- Curry the division operator with 2. This means that anything
-- passed to the halfzies function will be divided by 2.
halfzies = (/ 2)
-- Curry the ++ oprator to append the "\n" to any string.
newLine = (++ "\n")
As you can see here, we are taking the division operator (/) and the list concatenation operator (++) and creating curried function with static values. These curried functions can then be used subsequently with only one operand:
*Main> :load hw5.hs
[1 of 1] Compiling Maine ( hw5.hs, interpreted )
Ok, modules loaded: Maine.
*Maine> halfzies 10
5.0
*Maine> putStr ((newLine "hello") ++ (newLine "world"))
hello
world
While the concepts in this assignment appeared simple, the implementations seemed to take a good deal of elbow grease. And, I know this might seem extremely shallow, but when I google, "Haskell regular expression replace" and nothing very useful comes up in the search results, well, I don't take that as a good sign.
Want to use code from this post? Check out the license.
Reader Comments
Haskell regular expressions:
http://www.serpentine.com/blog/2007/02/27/a-haskell-regular-expression-tutorial/
http://www.haskell.org/haskellwiki/Regular_expressions
http://book.realworldhaskell.org/read/efficient-file-processing-regular-expressions-and-file-name-matching.html (scroll down about a quarter of the article)
Man, your code comments are longer than the homework code itself :)
btw. i liked reading the "seven languages ..." posts. they provided me with the insight without the pain connected with learning a new language.
@Sean,
Thanks for the links. In my Googling, I only found the first of those three. Either I've had just a really long week, or my Googling skills are not what they used to be. Even looking at those links, though, it looks like there might not be native "replace" feature of RegEx, just matching and extracting.
At least day 2 was better than day 3 (which I am embarassing about to blog)... I had epic #Fail last night :(
@Nelle,
Anything worth commenting is worth commenting excessively :P In all fairness, when it comes to something like this, I put in a lot of comments because I'm pretty much trying to explain to *myself* what is going on in the code.
Glad you're enjoying the series. It's just about coming to a close.