[2009.10.01] Some Haskell features for F#

I learned a bit of both Haskell and F#. I love them both but I don't think I am going to get a job with either of them anytime soon! Either way, in my quest for knowledge, there were some features of Haskell I wished were in F#. Of course, I am sure the F# folks have their reasons why things are the way they are. Moving on...

[1] Function signature and definition

In Haskell, you can simply write down your function definition and follow that with your implementation as shown in Line 1

  1: fibonacci :: Int -> Int

  2: fibonacci 0 = 0

  3: fibonacci 1 = 1

  4: fibonacci n = fibonacci(n-1) + fibonacci(n-2)

In F# however, you cannot add the function definition at the start of the function implementation. Instead, you need to add it to a separate F# Signature File. As such the same definition in F# is:

  1: let rec fibonacci = function

  2:     | 0 -> 0

  3:     | 1 -> 1

  4:     | n -> fibonacci(n-1) + fibonacci(n-2)

[2] Haskell is more explicit about side effects

If you want to deal with Input/Output (IO) in Haskell, you have to be explicit about it. For instance, the definition of the putStrLn function is given as: String -> IO() This clearly states that this function has side effects and it is identified from the get go by the IO parameter. However, in F# you can write a function that has side effects but the function signature may not tell you that.

[3] Functions as equations

Looking back at the two fibonacci functions defined both in Haskell and F#, I can say I prefer the Haskell way of doing things. While the F# way is very close, I like the fact that in Haskell I can set up function conditions as a set of equations. You cannot use the same function name more than once in F# as in Haskell.

This was just a short post based on some of my observations. With that said, it's time to get back into the F# game.

[2009.05.10] The Haskell Road to Logic, Math and Programming [Exercises 1.15 – 1.21]

Listing for Exercises 1.15, 1.16, 1.17, 1.20, 1.21

Exercise 1.15: Write a function srtString :: [String] -> [String] that sorts a list of strings in alphabetical order.

Exercise 1.15 solution:
Actually this is a pretty simple solution which could have been realized from Example 1.11. All I have to do is modify the type signature to make it a generalized/ polymorphic type that derives from the Ord class. In addition, this function uses the removeFst function from Exercise 1.10.

-- type definition
srtStrings :: (Ord a) => [a] -> [a]
srtStrings [] = [] -- base case
srtStrings xs =
    let m = minimum xs
    in m : (srtStrings . removeFst (==) m) xs -- [1]
-- NOTE: [1] can be traditionally be written as:
-- m : (srtInts (removeFst (==) m xs))

Example of Use:
*Main> (srtStrings . words) "this will be a sorted line"
["a","be","line","sorted","this","will"]
--NOTE: I used the words function to split the line at whitespaces to create the array of Strings.

Example 1.16: Suppose we want to check whether a string str1 is a prefix of a string str2. Then the answer to the question prefix str1 str2 should be either yes (true) or no (false), i.e., the type declaration for prefix should run:
prefix :: String -> String -> Bool.
Prefixes of a string ys are defined as follows:

1. [] is a prefix of ys,
2. if xs is a prefix of ys, then x:xs is a prefix of x:ys,
3. nothing else is a prefix of ys.

Exercise 1.16 solution:
My implementation is a bit different than what was asked for as it is more generalized and as such, can be used for other types, not just strings. In addition, the predicate is used to describe the comparison function being used to test the prefix and the rest of the list.

prefix :: (a -> a -> Bool) -> [a] -> [a] -> Bool
prefix _ xs [] = False -- 2nd list cannot be empty
prefix _ [] ys = True -- [] is prefix of a non-empty one
prefix eq (x:xs) (y:ys) = (x `eq` y) && prefix eq xs ys

Example of Use:
*Main> prefix (==) "this" "this is cool"
False

*Main> prefix (==) "this" "that is not"
False

*Main> prefix (==) [1,2,3] [1..10]
True

Exercise 1.17: Write a function substring :: String -> String -> Bool that checks whether str1 is a substring of str2.
The substrings of an arbitrary string ys are given by:

1. if xs is a prefix of ys, xs is a substring of ys ,
2. if ys equals y:ys' and xs is a substring of ys', xs is a substring of ys,
3. nothing else is a substring of ys.

Exercise 1.17 solution:
First, I will change the parameters of the problem a little bit to make the function more generic, so it can work on arbitrary lists, rather than just list of string.

Then, I will use the sliding window approach here and will make use of the prefix function from Exercise 1.16. Basically, at each iteration, call prefix which will test elements in the corresponding lists to see if there is a match. If there is not a match, that is, the first string is not a prefix of the second string then simply remove the first element from the second string, and apply prefix to the remainder of the second list. However, the first list that must be passed to the prefix function has to be the original one.

subString :: (Eq a) => [a] -> [a] -> Bool
subString [] _ = True
subString _ [] = False
subString (x:xs) (y:ys) =
    if prefix (==) (x:xs) (y:ys)
    then True
    else subString (x:xs) ys

Example of Use:
*Main> subString "true" "true"
True

*Main> subString "true" "false"
False

*Main> subString "true" "falsetruefalse"
True

*Main> subString [1,2,3] [1..10]
True

*Main> subString [] [1]
True

*Main> subString ['a','b'] "my abcs"
True

Exercise 1.20: Use map to write a function lengths that takes a list of lists and returns a list of the corresponding list lengths.

Exercise 1.20 solution:
This is a very simple solution actually. Note the use of point-free style as the argument is implied.

lengths :: [[a]] -> [Int]
lengths = map length

Example of Use:
*Main> lengths [[1..10],[2,3]]
[10,2]

Exercise 1.21:
Use map to write a function sumLengths that takes a list of lists and returns the sum of their lengths.

Exercise 1.21 solution:
Again, another simple solution using the lengths function from Exercise 1.20.

sumLengths :: [[a]] -> Int
sumLengths xs = foldl (+) 0 (lengths xs)

Example of Use:
*Main> sumLengths [[1..10],[2,3]]
12

[2009.05.03] The Haskell Road to Logic, Math and Programming [Exercises 1.09 – 1.14]

I started learning Haskell a few weeks ago by reading Real World Haskell and following the examples they have there. However, personally, some of the material was a bit more than I expected, so I decided that I should at least scale back my approach and try to work on some other Haskell type programming problems. As such, I began reading "The Haskell Road to Logic, Math and Programming" by Kees Doets and Jan van Eijck. While I have asked and not yet received the list of solutions to the exercises as of this writing (May 03 2009), I have decided that as I work the exercises, I will post my solutions to the problems. This will help me understand Haskell as well as others who are in my position.

NOTE: I will not post every single exercise, as some may either too trivial or examples stated in the book. Unfortunately, I will not be able to bring in code that is nicely colored as in my F# posts, as I have not yet found a good Eclipse plugin that will export Haskell code to HTML.

Here is the listing for Exercises 1.09 - 1.14.

EXERCISES

Exercise 1.09: Define a function that gives the maximum of a list of integers. Use the predefined function max.

Exercise 1.09 solution:

-- type definition
myMax :: [Int] -> Int
myMax [] = error "empty list"
-- base case for singleton list
myMax [x] = x
-- remove the first element of the list and compare it to
-- the recursive result of the rest of the list
myMax (x:xs) = max x (myMax xs)

Exercise 1.10: Define a function removeFst that removes the first occurrence of an integer m from a list of integers. If m does not occur in the list, the list remains unchanged.
NOTE: After I wrote my version, I remembered that the Haskell library has a similar function in the Data.List module called deleteBy. I liked that version better as it was more flexible than what was asked for so I implemented mine the same way which is basically what is in the module.

Exercise 1.10 solution:

-- eq is a predicate to use to make the comparison
-- in this case, when executing the function,
-- you can use (==) as the predicate
-- Ex: removeFst (==) 2 [1,2,3,4,2] and get [1,3,4,2]

-- type definition
removeFst :: (a -> a -> Bool) -> a -> [a] -> [a]
-- base case, empty list returns empty list
removeFst eq x (y:ys) =
    if x `eq` y
    then ys
    else y : removeFst eq x ys

Example 1.11: We define a function that sorts a list of integers in order of increasing size, by means of the following algorithm:

• an empty list is already sorted.
• if a list is non-empty, we put its minimum in front of the result of sorting the list that results from removing its minimum.

Even though this is given as an example in the book, I have replicated it here with some minor adjustments to highlight some additional features, namely using the built in minimum function and replacing parenthesis with point-free programming style.

Example 1.11 solution:

-- Find the minimum of the list, remove it and
-- append it to the result of recursively calling
-- the rest of the list members

-- type definition
srtInts :: [Int] -> [Int]
srtInts [] = [] -- base case
srtInts xs =
    let m = minimum xs
    in m : (srtInts . removeFst (==) m) xs -- [1]
   
-- NOTE: [1] can be traditionally be written as:
    m : (srtInts (removeFst (==) m xs))

Example 1.12: Here is a function that calculates the average of a list of integers. The average of m and n is given by (m + n) / 2, the average of a list of k integers n₁ , ..., n_k is given by (n₁ + ... + n_k) / k.
Again here I have my own implementation, using the built in foldl function rather than sum and using realToFrac to convert from Int to Float.

Example 1.12 solution:

-- type definition
myAvg :: [Int] -> Float
myAvg [] = error "empty list"
myAvg xs =
    realToFrac (foldl (+) 0 xs) / realToFrac (length xs)

Exercise 1.13: Write a function count for counting the number of occurrences of a character in a string. In Haskell, a character is an object of type Char, and a string an object of type String, so the type declaration should run:
count :: Char -> String -> Int.

Exercise 1.13 solution:

-- define an auxiliary function to get a list
-- of similar characters
count' :: Char -> String -> [Char]
count' _ "" = []
count' x (y:ys) =
    if x == y
    then y : count' x ys
    else count' x ys

-- use our main function to get the length
-- of the list returned by the auxiliary function
count :: Char -> String -> Int
count x = (length . count' x) -- point free style

Exercise 1.14: A function for transforming strings into strings is of type String -> String. Write a function blowup that converts a string a₁a₂a₃ ... to a₁a₂a₂a₃a₃a₃ ....
blowup "bang!" should yield "baannngggg!!!!!". (Hint: use ++ for string concatenation.)

Haskell has its own replicate function but for my own benefit, I decided to write my own (and no I didn't peek at the source code at all), called myReplicate which takes an integer and a type of object and creates a list of objects based on the input integer. In addition, I have added an auxiliary function called blowup' which is used to abstract additional computations required to make the function work correctly.

Exercise 1.14 solution:

-- type definiton
blowup :: [a] -> [a]
blowup xs = blowup' 1 xs

-- type definition
myReplicate :: Int -> a -> [a]
myReplicate 0 _ = [] -- no replication
myReplicate n x = x : myReplicate (n-1) x

-- type defintion
blowup' :: Int -> [a] -> [a]
blowup' _ [] = []
blowup' n (x:xs) =
    myReplicate n x ++ blowup' (n+1) xs

This was a complete and utter pain to format and try to colorize even a little bit. But the fact that I am taking the time to make this look more appealing should indicate my passion for this stuff.

[2009.04.02] Haskell and Eclipse [Part 2]

The post, Haskell and Eclipse, outlines how to set up the Haskell plugin in Eclipse. This is a follow up, illustrating how to get started developing in Haskell now that you have an IDE to work with.

Let's begin with just starting Eclipse and looking at some of what we have to work with as shown in Fig. 1.

Fig.1 Haskell Perspective of the Eclipse IDE

In order to start working with code, you need to create a project. Under the Navigator tab, right click and select New to see the options as shown in Fig. 2. Choose:
Haskell Project -> Name the project -> Select where to save it -> Finish Fig. 2 - 4 walk through this stage.

Fig.2 Create a new Haskell Project 1

Fig.3 Create a new Haskell Project 2

Fig.4 Create a new Haskell Project 3

Now take a look at the structure of the project you created. The src directory is where you will put your Haskell files. With the src directory selected, choose New and you will be given several options as to the type of files (or even a sub-project) you can create. See Fig. 5.

Fig.5 Creating different Haskell related files

Mostly, you will either create a Haskell Module or a standalone Haskell file. To create the standalone file, choose File, give it a name and the extension .hs.
NOTE: Both module and standalone file names should start with an uppercase letter. For example, I will create a new Haskell source file called AddIntList as shown in Fig. 6.

Fig.6 Creating a Haskell source file

For example, I will add code to the file to sum a list of integers. Once done, simply follow the points on the list which is also shown in Fig. 7.

• Highlight all the code
• Right click
• Select Run As
• Choose the compiler to use (I have GHC installed so pick GHCi)

Fig.7 Running Haskell code in Eclipse

NOTE: If you started a new project and then added a file rather than a new module, to compile, right-click and choose Run As on the actual project folder in the Navigation Pane, then when the GHCi window in Eclipse shows that the module loaded message (Ok, modules loaded:), then type in the name of the function and pass the arguments along as well.

The code used for this demo is as follows:

addIntList :: [Int] -> Int
addIntList x = foldl (+) 0 x

Once the code has successfully been compiled, you will see a message in the Console window indicating that. At the prompt, you can just type in the function you want to execute with arguments and hit enter as shown in Fig. 8.

Fig.8 Executing functions in the console window

Happy coding!

[2009.03.01] The Haskell Plugin and Eclipse [Part 1]

Now that I am more comfortable with F#, I feel that it is about time I started learning Haskell. Well another reason is that I got sick and tired of hearing some of these Microsoft people like Erik Meijer, Brian Beckman and Joe Duffy talk about Haskell :-)

Given that F# was born out of Haskell concepts to fit on the .NET platform, I figure it would be good to have the parent language under my belt. In addition, given that Haskell has support for concurrency and parallel programming, and the software and hardware world is shifting in that direction, then it is only natural to evolve along these patterns as well. Actually, I am more curious about Haskell and what it has to offer and I figure that learning it will make me a better and more conscientious developer. From some of the interviews coming out of Microsoft, it is clear that the Parallel and Concurrent working groups are also borrowing ideas from Haskell. I am glad I got into F# first, as it is making Haskell much easier to understand.

Even though Haskell has been around for a while, in terms of tools and IDE support, that area is still lacking. While everyone has their preference, I would like to use my first post to you how to use Haskell in the Eclipse IDE.

• Download and install the latest version of Eclipse. If you are already using Eclipse for Java Development, then either skip this step or get the latest version. As of this writing, I am using Eclipse Version 3.4.1 Ganymede.
  Note: There really isn't any 'install' step for Eclipse. All you have to do is extract the compressed file to a location on your computer and run eclipse.exe.
• Download and install the Haskell. As of this writing, I am using Version 6.10.1 (released on 2008/11/04) on the Windows Server 2008 SP1 Operating System.
• After installing Haskell, you can begin using the command line interpreter, GHCi to muck around. For Windows folks, go to Start -> Run and type in ghci. Fig 1 shows the result.

Fig.1 Haskell GHCi in Windows

• The next step is to get the Haskell Plugin for Eclipse. First, fire up Eclipse and you may need to set up a Working Environment if this is the first time you are running Eclipse. The Working Environment is basically setting up a folder to put your projects and files in.
  In Eclipse, go to :
  Help -> Software Updates

Fig.2 Software Updates

• Click the Available Software tab. Select the Add Site... button on the right of the new window that opens up and enter the URL:
  http://eclipsefp.sf.net/updates. Click Ok.

Fig.3 Adding Functional Programming Plugin

• You are now ready to install the plugin. The Available Software tab may look something as shown in Fig 4. Simply check expand the node of the site you entered previously and select the component to install as shown in the figure. Once it is done installing, restart Eclipse.

Fig.4 Installing the Haskell plugin

• Once you restart Eclipse, the first thing you will want to do is configure the plugin to point to the ghc.exe you installed previously. Go to
  Window -> Preferences and notice in the Preferences window, there is a nested view for Functional Programming. Go to the Compiler option as shown and navigate to where you installed Haskell. Find and select ghc.exe as shown in Fig 5. It can be seen that I installed Haskell on my C Drive, just navigate to where you put it and select the correct file.

Fig.5 Configure the GHC

• The next step is to switch to the Haskell Perspective. Eclipse's default is set to the Java Perspective. To change perspectives, go to
  Window -> Open Perspective -> Haskell as seen in Fig 6. Also you can do this by clicking the Haskell button in the top right corner of the Eclipse Window.

Fig.6 Switching to Haskell Perspective

This concludes how to get Haskell and Eclipse to play nice with each other. My next post will show to to use the plugin for development as this post is already too long.