Programming in Haskell Series. III: Lists Part I

Lists are the bread and butter of functional programming, and in fact they are extensively used in any programming language. In this article we are going to define our own list in Haskell, and we will use it to solve a couple of interesting problems. Finally we will review the capabilities that Haskell and the standard library provide in terms of lists.
This article is divided in three parts. In the first one we will see what is a list, and how to define it in Haskell. In part two we will explore Pattern Matching and will use it to build functionality using our own list type. In the third part we will see what Haskell and its library has to say about lists (and I guarantee you that we will not use our own list ever again).

What is a list

A list is a sequence container. What? Ok, don't panic. A list is a type of data type that can contain values. For intance a list can contain phone numbers, or the words of a sentence, or the characters of a word. A list is sequential in the sense that the element in a list are organized in sequence, one after the other. If you want to go through the elements on a list, you have to go in sequence from the first to the last.
We use lists in programming for almost anything. You may be building an application to manage a group of students. Most probably those students will be kept in some sort of list. There will be also a list of subjects, a list of teachers, ... you name it.

Show me some code

Ok, let's open ghci and have some fun:

>ghci
GHCi, version 7.6.3 [NG/7.6.3.5]: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude>

In haskell we represent an empty list by a pair of matching square brackets:

Prelude>:t []
[] :: [a]

I have asked Haskell to tell me the type of [], and it has answered that it is a list of some type a. Fair enough, Haskell cannot know what our list is supposed to contained, but it knows that it has to contain things wiht a type, and all of them must have the same type:

Prelude>: [3]
[3] :: Num t => [t] 

Now Haskell has a bit more information and can determine that whatever we put in the list must be of type Num. Don't worry about the syntax for the moment. To define a list with several elements simple write them inside the square brackets and separate them by commas:

Prelude>:t [1,2,3]
[1,2,3] :: Num t => [t]

Prelude> [1,2,'a']

<interactive>:10:2:
    No instance for (Num Char) arising from the literal `1'
        Possible fix: add an instance declaration for (Num Char)
        In the expression: 1
            In the expression: [1, 2, 'a']
            In an equation for `it': it = [1, 2, 'a']
            

Ups! We tried to create a list mixing types, and that is not allowed in Haskell. Haskell tends to be super verbose when reporting errors. This is scaring in the beguining, but quite nice once you understand what those messages are telling you. Let me quickly show you now how to append an element to begining of a list, and how to concatenate 2 lists:

Prelude> 3 : [1,2]
[3,1,2]
Prelude> [1,2] ++ [3,4]
[1,2,3,4]

Very easy indeed!

Defining our own list type

Let's think for a second how we can represent a list. A list has to fundamental states:

• Empty
• An element followed by a list

Traditionally an empty list in functional languates is called nil, and an element followed by a list is refered to as cons. We can represent the list [1,2,3] as 1 cons ( 2 cons (3 cons nil)), if we use cons as an infix operator, or cons 1 (cons 2 (cons 3 nil)). Haskell provides syntax sugar for cons and nil. Cons is represented as ':', and nil as []. Multiple cons are represented as commas like in [1,2,3].
Let's write some code. Create an empty file and call it Main.hs:

module Main where

-- Algebraic data type. A list is either Empty or
-- is an element followed by a list
data List a = Empty | Cons a (List a)
                      deriving Show

-- Convenience function that returns an empty list
nil :: List a
nil = Empty

-- Append an element to the front of a list
-- Given an element and a list returns a new list
cons :: a -> List a -> List a
cons x = Cons x

Load it in ghci, and let's create our own new list!:

julio@juliohome:~/haskell/blog/mylist$ ghci Main.hs
GHCi, version 7.6.3 [NG/7.6.3.5]: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( Main.hs, interpreted )
Ok, modules loaded: Main.
*Main> cons 1 (cons 2 (cons 3 nil))
Cons 1 (Cons 2 (Cons 3 Empty))

What to do next

• Explore the links provided in this post
• Understand algebraic datatypes and how they are defined

I will see you soon in Part II.
Enjoy!

Checkout my new C++ programming blog: cpluscplusbaremetal.blogspot.com

Hi all,

I have just started a new blog specifically focused on C++, and more particularly in modern C++. The first few post are going to deal with the basics:

• Hello World (of course!)
• Setting up gcc
• Setting up CMake
• Setting up testing infrastructure
• Creating a template project that will be used as the starting point for subsequent articles

I hope you drop by and get yourself started in the super exciting world of native code!

http://cplusplusbaremetal.blogspot.ie/

By the way, check out #goingnative in Channel 9: https://channel9.msdn.com/Events/GoingNative

Happuy native coding!

Haskell Coding Kata I: FizzBuzz

At the end of the Haskell programming series II, I proposed the readers a coding Kata. FizzBuzz is a very simple problem:

Given a number N, if the number is multiple of 3 print Fizz, if the number is multiple of 5 print Buzz, if the number is multiple of both print FizzBuzz. Nothing really fancy. As promised, here you have one possible solution for a little variation of the problem, in Haskell:

module Main where  
 
main :: IO()  
main = do  
   putStrLn "Enter a number"  
   nb <- readLn  
   fizzBuzz nb  
   main  

fizzBuzz :: Int -> IO()  
fizzBuzz x = do  
   if (x `mod` 3 == 0) then putStrLn "Fizz" else return ()  
   if (x `mod` 5 == 0) then putStrLn "Buzz" else return ()  

A more elaborated solution that prints the first N FizzBuzz executions could be as follows:

module Main where  
main :: IO()  
main = do  
   putStrLn "Enter a number"  
   nb <- readLn  
   putStrLn $ show $ map fizzBuzz $ take nb [1,2..]  
   main  

fizzBuzz :: Int -> String  
fizzBuzz x =  
   if (fb == "") then show x else fb  
   where fb = fizz x ++ buzz x  

fizz :: Int -> String  
fizz = matchModule 3 "Fizz"  

buzz :: Int -> String  
buzz = matchModule 5 "Buzz"  

matchModule :: Int -> String -> Int -> String  
matchModule modulo message nb  
   | nb `mod` modulo == 0 = message  
   | otherwise = ""  

The output of an execution is as follows (using ghci):

 > ghci  
 GHCi, version 7.6.3 [NG/7.6.3.5]: http://www.haskell.org/ghc/ :? for help  
 Loading package ghc-prim ... linking ... done.  
 Loading package integer-gmp ... linking ... done.  
 Loading package base ... linking ... done.  
 Prelude> :load Main.hs   
 [1 of 1] Compiling Main       ( Main.hs, interpreted )  
 Ok, modules loaded: Main.  
 *Main> main  
 Enter a number  
 15  
 ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]  
 Enter a number  
 9  
 ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz"]  
 Enter a number  

Happy Haskell!

Programming in Haskell Series. II: Getting Started

In this article we are going to see how to setup a Haskell development environment, and we are going to write our own "Hello Haskell" program. There are a number of things that are necessary for pretty much every language you want to work with:

• Compiler/Interpreter
• Source code editor/IDE
• Build system
• Documentation

Compiler/Interpreter

There are many Haskell compilers available, but the one that seems to be more widely used is GHC (the Glasgow Haskell Compiler).

One of the nice things about Haskell is that it can be interpreted as well as compiled. The GHC interpreter is call GHi. They normally come bundled together in the so called Haskell Platform. Installing the platform will get you both.

To install the Haskell Platform, go to http://www.haskell.org/platform/ and follow the steps for your particular platform. I use Debian Linux (version 7.0,Wheezy). The official Debian package repositories include a Haskell-platform version that, although is not the latest and greatest, is enough to get started. Installation in Debian is pretty simple:

 > sudo apt-get install haskell-platform  

To verify that everything was successfully installed execute the following commands:

 > ghc --version  
 The Glorious Glasgow Haskell Compilation System, version 7.6.3  
 > ghci  
 GHCi, version 7.6.3 [NG/7.6.3.5]: http://www.haskell.org/ghc/ :? for help  
 Loading package ghc-prim ... linking ... done.  
 Loading package integer-gmp ... linking ... done.  
 Loading package base ... linking ... done.  
 Prelude> 3+3  
 6  
 Prelude>   
 Leaving GHCi.  

You can also try Haskell on the browser: http://tryhaskell.org/

Source code editor/IDE

The debate editor vs IDE has become a sort of religious programming battleground. In most cases there is no debate at all, just groups of angry people yelling at each other how awesome their choice is, and how much the guys on the other side are missing out. I won't contribute to it.

The Haskell wiki offers detailed information about IDEs, editors and tools for Haskell development. Personally I prefer using an editor, and my editor of choice is Emacs. As almost everything else emacs can be installed via apt-get. I am not going to lie to you, Emacs is not easy to use. There are gazillions of commands that need to be learnt, but once you get passed the initial stages, you won't be needing a mouse any more, and you'll be able to write and browse your code very very fast indeed. Emacs has a mode for Haskell, which was very creatively named haskell-mode. This mode can also be installed via apt-get:

 > sudo apt-get install emacs  
 > sudo apt-get install haskell-mode  

If you prefer Eclipse, there is a plugin for Haskell development. It is called Eclipse FP Plugin. 

Build system

If you don't know what a build system is, and what it does for you, I recommend you read the build automation entry in the wikipedia. In most of this Haskell learning series we are going to use only packages that are included in the standard library. For that reason, the use of a build system will not be necessary, but you can use one if you want.

In the world of Haskell there is one build system that rules all the others. It is called Cabal, and comes bundled with the Haskell Platform.

Documentation

There is only one website you need to remember when it comes to Haskell documentation; Hoogle. Hoogle is an immensely powerful search engine for Haskell documentation.You can search method names, packages and so on, but you can also provide the type of a method ( a -> b -> c), and hoogle will show you all the methods with that type. Types are a very important concept in Haskell, and being able to search by type is a very useful feature.

Putting it all together: Hello Haskell!

1) Create a file called Main.hs with the following content:

 module Main where  
 -- A simple expression that returns a String                                                  
 hello :: String  
 hello = "Hello Haskell"  
 -- Executable's entry point. It's type IO denotes                                                
 -- that this method can have side effects, like writing                                             
 -- on the standard output.                                                           
 main :: IO ()  
 main = putStrLn $ hello ++ " " ++ (reverse hello)  

2) Compile it with GHC

 > ghc Main.hs  
 [1 of 1] Compiling Main       ( Main.hs, Main.o )  
 Linking Main ...  

3) Execute

 > ./Main   
 Hello Haskell lleksaH olleH  

We can do the same with GHCi:

1) Open GHCi and type the following commands

 > ghci  
 GHCi, version 7.6.3 [NG/7.6.3.5]: http://www.haskell.org/ghc/ :? for help  
 Loading package ghc-prim ... linking ... done.  
 Loading package integer-gmp ... linking ... done.  
 Loading package base ... linking ... done.  
 Prelude> let hello = "Hello Haskell"  
 Prelude> putStrLn $ hello ++ " " ++ (reverse hello)  
 Hello Haskell lleksaH olleH  

Conclusions

Now that we are all set for Haskell development it is time to start learning more about other fundamental concepts like:

• Lists
• Pattern Matching
• Functions and function composition
• Haskell type system
• ...

We will be talking about these topics in future installments of this learning series. Before finishing this article, I want to challenge you to implement a very simple programming exercise. I ẃill provide my own solution to it in the next Haskell Learning series article. 

Problem: FizzBuzz

Programming in Haskell Series. I: "Introduction and reading a file example"

This is the first article in what I hope will be a series of articles on Haskell. Haskell is a pure functional programming language, with static typing and lazy evaluation. If you fell at home thinking in abstract/mathematical concepts you are going to love Haskell. It really makes you feel like a computer scientist and not as a coding monkey any more.

• Pure as in functions don't have side effects, which leads to the much desired referential transparency
• Static typing means that every single value and expression has a type, and it cannot change during the execution of a program. This allows the compiler to catch a lot of mistakes. Besides, Haskell type system is incredibly expressive and flexible. In Haskell you spend most of your type defining types.
• Lazy as in Haskell only evaluates the minimum amount of information that it requires to keep moving forward with the execution. For instance it is possible to define a infinite list of integers and then request the first element (head in functional programming parlance). In this case only that first element will be determined and the execution will complete happily.

You may be thinking that a language with no side effects is pretty useless. I can't write to a file or the screen, get output from a user, etc. In fact Haskell provides a mechanism to clearly separate your "unsafe"  (with side effects) code from your pure code. These two cannot be mixed. This mechanism is the IO Monad (oh yeah so early and already mentioning Monads).

Now, let's see a bit of code. Hopefully the comments will make it pretty clear

  -- define a new module   
  module Main where   
  -- main is the entry point for the execution of your program  
  -- The first line declares the type (it is optional in Haskell most of the time) whereas  
  -- the second actually defines what the main function is/does  
  main :: IO ()   
  main = do   
    putStr "File name please?"   
    filename <- getLine   
    putStr filename   
    return()   

The Haskell program must have a Main module and a main function. The type of the main function must be IO (), but I won't go into the details now. What we have here is pretty much all unsafe code. This type of code is also monadic (the do construct is syntactic sugar for monad).

Now lets's see how we can actually read all the lines in the file, and then print them all back to the user:

 module Main where  
 main = do  
    putStr "Tell me something\n"  
    filename <- getLine  
    putStr $ "Attempting to open " ++ filename  
    contents <- readFile filename  
    putStr contents  
    return ()  

This is clearly not very functional. Let's do something different. Lets count the number of lines in the file, in a more functional style.

 module Main where  
 main = do  
    putStr "Tell me something\n"  
    filename <- getLine  
    -- Haskell function application associates to the left. The $ function associates  
    -- to the right and saves us a good number of brackes. We want to print the result  
    -- of the expression on the right handside of the $  
    putStr $ "Attempting to open " ++ filename ++ "\n"  
    contents <- readFile filename   
    putStr $ "There are " ++ nbOfLines contents ++ " lines in the file\n"  
    putStr contents  
    return ()  
 -- Here we are declaring the type of the function nbOfLines  
 -- It takes a String and returns a String  
 nbOfLines :: String -> String  
 -- The dot is function composition as in maths. f.g x = f ( g (x) )   
 nbOfLines = show.listSize.lines   
 -- Takes a list of any type and return an Int  
 listSize :: [a] -> Int  
 listSize [] = 0  
 listSize (x:xs) = 1 + (listSize xs)  

How do we execute this? There are many ways of executing Haskell code, in this occasion we are going to compile to machine code and then execute. Install the Haskell Platform and:

$ ghc FilaName.hs -o myexecutable
$ ./myexecutable

There is a lot to understand here. Hopefully we will be able to make progress towards Haskell proficiency in the next posts in this series.