lwheng

keep learning. keep improving.

Lists

| Comments

In my previous post, I mentioned Lists briefly. I had shown you examples of valid and invalid lists, some enumeration techniques and some operators you can use with lists. But there is so much more we can learn about Lists. We’ve barely scratched the surface. That is why I’ve dedicated this post entirely to Lists.

Hello again, Lists

TMNT

A List is a collection of elements. The elements of a list can be of any type, as long the elements are of the same type. Let’s have a look how a list look like in a type signature using a simple example with the reverse function:

1
reverse :: [a] -> [a]

A List contains its elements within the square brackets [] separated by commas. So what is a? a is type variable, it can be of any type. This means we can even have a list of lists e.g. [[1,2,3], [2,3,4]]. You can start to imagine how powerful and complex lists can be.

Fundamental Requirements

In general when we talk about arrays, arraylists, sets, collections etc, we normally require them to have some basic features and capabilities.

Add

There are 2 ways to add element(s) to a Haskell list. The first way is the cons operator, :. The : operator only allows you add an element to the front of the list i.e. it becomes the first element. The second way is by the concat operator, ++. This operator takes 2 lists and append them together.

1
2
3
4
5
6
7
8
ghci> :type (:)
(:) :: a -> [a] -> [a]
ghci> 1 : [2..10]
[1,2,3,4,5,6,7,8,9,10]
ghci> :type (++)
(++) :: [a] -> [a] -> [a]
ghci> [1..5] ++ [6..10]
[1,2,3,4,5,6,7,8,9,10]
Search

There are many ways in Haskell we can check whether an element is found in a list. Without introducing too many new terms, the elem function is probably the simplest way to go. It is more intuitive to use elem infix, so this is how we can use it: 1 `elem` [1,2,3] will give you True, False if otherwise.

Retrieve

Some times we want to get an element at the i th position. For that we have the !! function. E.g. [1,2,3] !! 0 will give you 1. As usual, index starts with zero and if you specify an invalid index it will cause an exception.

Delete

Because of the behaviour and nature of lists, this is not as straightforward. The way I see it, there are 2 basic ways of deleting elements. The first way is to delete all from the list that matches the requirements. We can filter for the elements we are interested in.

1
2
3
4
5
6
7
ghci> let mylist = [1,2,3,2,1,2,3,4,3,2,1,2,3,4]
ghci> :t filter
filter :: (a -> Bool) -> [a] -> [a]
ghci> filter (/= 1) mylist
[2,3,2,2,3,4,3,2,2,3,4]
ghci> filter (odd) mylist
[1,3,1,3,3,1,3]

filter is a function that takes a predicate and a list as arguments. You can see its type signature in Line 3 above: The predicate, (a -> Bool), and the list, [a]. Finally it returns another list [a]. The predicate is also a function. It is a function that returns a Bool. Intuitively filter means: For every element that returns True from the predicate function, include it in the output list.

The second way is to delete the n th item from the list. I’m guessing this kind of operation is not common in Haskell programming, despite searching for it I wasn’t able to find a neat answer. The intuition of the following method is to first cut the list into 2 parts at the n th item. Then we remove that n th item before joining the 2 parts back together. Let’s look at this example which tries to delete the element 4 from the list.

1
2
3
4
5
6
7
-- Deleting 4 from our list
ghci> let a = [1..10]
ghci> let pair = splitAt 3 a
ghci> pair
([1,2,3],[4,5,6,7,8,9,10])
ghci> (fst pair) ++ (drop 1 (snd pair))
[1,2,3,5,6,7,8,9,10]

There are several new terms and functions here, so let us go through them one by one.

1
let a = [1..10]

This assigns the list to a.

1
2
ghci> :t splitAt
splitAt :: Int -> [a] -> ([a], [a])

splitAt is a function takes an integer (the position) and a list, and then returns a tuple of 2 lists. This is the cutting function. What is a tuple? It is a data structure that contains multiple parts. I like to see it a ordered group of things. In this example, we have a tuple of 2 elements. You can have, however, as many elements in a tuple as you like. We saw that the outcome of splitAt was ([1,2,3],[4,5,6,7,8,9,10]) when we split at index 3, which is element 4 in our list.

1
2
3
4
5
6
ghci> :t fst
fst :: (a, b) -> a
ghci> :t snd
snd :: (a, b) -> b
ghci> :t drop
drop :: Int -> [a] -> [a]

fst and snd are functions for tuples. fst is short for first, snd is short for second. Looking at the type signatures, it is easy to tell what is going for each function.

As for drop, it is a function that removes a specified number of elements from the beginning of a list. We will talk more about it in the later section of this post.

So in Line 5 of our example, Deleting 4 from our list, we get the first part of the tuple and join with the second of the tuple, with the 1st element of the second part removed. And there you have it.

Basic Functions on Lists

There are many more basic functions we can apply on lists.

length

1
2
3
4
ghci> length [1,2,3,4,5,6,7,8,9,10]
10
ghci> length []
0

This should be straightforward enough.

null

1
2
3
4
ghci> null [1,2,3,4,5,6,7,8,9,10]
False
ghci> null []
True

So far so good.

reverse

1
2
3
4
ghci> reverse [1,2,3,4,5,6,7,8,9,10]
[10,9,8,7,6,5,4,3,2,1]
ghci> reverse []
[]

Well, need no explanation.

head, tail, init, last

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ghci> head [1,2,3,4,5,6,7,8,9,10]
1
ghci> head []
*** Exception: Prelude.head: empty list

ghci> tail [1,2,3,4,5,6,7,8,9,10]
[2,3,4,5,6,7,8,9,10]
ghci> tail []
*** Exception: Prelude.tail: empty list

ghci> init [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9]
ghci> init []
*** Exception: Prelude.init: empty list

ghci> last [1,2,3,4,5,6,7,8,9,10]
10
ghci> last []
*** Exception: Prelude.last: empty list

head, tail, init and last are some of the most commonly used functions for lists. However, sometimes, they also considered unsafe. Yup, they don’t work with empty lists. This exception cannot be caught during compile time, so be mindful whether you are dealing with empty lists.

I really like the illustration from Learn You A Haskell For Great Good. It is the best I’ve seen, and it really helped me understand these functions.

The List Monster

take, drop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ghci> take 0 [1,2,3,4,5,6,7,8,9,10]
[]
ghci> take 3 [1,2,3,4,5,6,7,8,9,10]
[1,2,3]
ghci> take 20 [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10]
ghci> take 3 []
[]

ghci> drop 0 [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10]
ghci> drop 3 [1,2,3,4,5,6,7,8,9,10]
[4,5,6,7,8,9,10]
ghci> drop 20 [1,2,3,4,5,6,7,8,9,10]
[]
ghci> drop 3 []
[]

ghci> :type take
take :: Int -> [a] -> [a]
ghci> :type drop
drop :: Int -> [a] -> [a]

take and drop are functions that returns sub-lists from lists. Unlike the previous 4 functions, they are more safe and do not cause exceptions when applied on empty lists. If you look at their type signatures, you can see that both of them take an Int and a list and returns a list. The Int, integer, is simply the number of elements you wish to take/drop.

To be continued…

Okay, we have gone through the fundamentals and numerous basic functions for Lists. But we are not done yet. There are many more advanced functions like map, zipWith, foldl and foldr that can be applied to lists. However due their complexity, I’ll have to leave them for the next post!

References

List Monster from Learn You A Haskell For Great Good

Getting Started With Haskell

| Comments

Get Your Machine Ready With Haskell

In order to compile and run Haskell files and commands, you’ll first need to get the Haskell Platform on your machine. You can download it here. The installation instructions on that site should be clear enough for whatever platform you are on. If you are on Windows, you should see several programmes, e.g. GHCi, added to your Start Menu. If you are using a Mac, then you should get comfortable with using the Terminal application (Spotlight > Search ‘Terminal’). If you are using Linux, well, I’m sure you know your stuff.

Coding Haskell with Sublime Text

You will also need a text editor to code your Haskell files. For that, I’d recommend Sublime Text. It supports syntax highlighting for Haskell which makes it more readable and easier to understand. It is also free! If you are comfortable with using command-line editors like vim or emacs, please go ahead!

Trying out ghci

1
2
3
4
5
6
7
8
lwheng:~ $ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
ghci> reverse [1,2,3]
[3,2,1]
ghci>

Once you are done with the installation, fire up the Terminal or launch GHCi on your machine. You should see some information about the version of GHCi you installed, followed by a prompt, e.g. ghci>. If you do not see the same prompt, or if you wish to change the prompt: :set prompt "<your preferred prompt>"

The GHC, Glasgow Haskell Compiler, is the open-source compiler for Haskell. GHCi is the interactive interpreter that you can use to quickly try out Haskell commands and functions. It is similar to the Python interpreter, you type in a command or expression and the interpreter attempts to evaluate it and prints out an adequate response. You can try out more by referring to here or here.

1
2
3
4
5
6
7
8
9
10
11
ghci> 1 + 1
2
ghci> 3 * 2
6
ghci> 3 / 4
0.75
ghci> sqrt 9
3.0
ghci> True && False
False
ghci>

As you learn Haskell, the most important command in GHCi that I think you must know is the :type command. :type <expression> or :t <expression> for short. It is useful because it returns the type signature of the expression you just entered, so you know what you are dealing with or whether you are on the right track!

1
2
ghci> :t reverse
reverse :: [a] -> [a]

You read it as: reverse is a function that takes in a list of elements of type a and returns a list of elements of type a.

Lists

Lists are simply, lists. Shopping list, item list, name list etc. In Haskell, a list can only store elements of the same type. To illustrate:

1
2
Valid lists   : [], [1,3,5], ['a', 'd', 'g'], ["a", "apple"], [True, True, False], "abcd"
Invalid lists : ['a', "asd"], [-20, 3.214], [1, 'a', True]

What? “abcd” is a list? Yes, "abcd" == ['a','b','c','d'] i.e. a String in Haskell is just a list of Char.

Now try typing this into GHCi: [1..50]. Or this: [1,3..50] Woah! The .. characters denote an enumeration. And yes, by specifying the first 2 elements, Haskell can detect the step size for the enumeration. It only works for those types that you can enumerate though. ["foo".."bar"] won’t work as there is no sensible way to enumerate that.

There are 2 operators you can use with lists: ++ (“concat”) and : (“cons”). Now that you already know of the :type command, let’s look at their type signatures and try to understand them.

1
2
3
4
ghci> :type (++)
(++) :: [a] -> [a] -> [a]
ghci> :type (:)
(:) :: a -> [a] -> [a]

Notice the brackets around the operators. They are needed when we use the :type command with operators. So we can read: ++ is a function that takes 2 arguments; a list of elements of type a and a list of elements of type a then returns a list of elements of type a. Can you guess what is happening for :?

1
2
3
4
ghci> [3,1,3] ++ [3,7]
[3,1,3,3,7]
ghci> [] ++ [False,True] ++ [True]
[False,True,True]

Note that the operators are used in infix form for convenience. We can write them in prefix form too: (++) [3,1,3] [3,7].

The order of the arguments is important. Let’s see a simple example with the : operator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ghci> 1 : [2,3,4]
[1,2,3,4]
ghci> [2,3,4] : 1

<interactive>:5:2:
    No instance for (Num t0) arising from the literal `2'
    The type variable `t0' is ambiguous
    Possible fix: add a type signature that fixes these type variable(s)
    Note: there are several potential instances:
      instance Num Double -- Defined in `GHC.Float'
      instance Num Float -- Defined in `GHC.Float'
      instance Integral a => Num (GHC.Real.Ratio a)
        -- Defined in `GHC.Real'
      ...plus three others
    In the expression: 2
    In the first argument of `(:)', namely `[2, 3, 4]'
    In the expression: [2, 3, 4] : 1

<interactive>:5:11:
    No instance for (Num [[t0]]) arising from the literal `1'
    Possible fix: add an instance declaration for (Num [[t0]])
    In the second argument of `(:)', namely `1'
    In the expression: [2, 3, 4] : 1
    In an equation for `it': it = [2, 3, 4] : 1
ghci>

When we run 1 : [2,3,4], we can see that 1 was successfully attached as the head of the list, [2,3,4]. When we ran [2,3,4] : 1, we see several lines of error messages. Pay special attention to Line 16. It is telling us: Hey! There is something wrong with the first argument you provided for the function! Similarly for Line 22. Looking at these error messages and the type signature of :, we can understand what’s wrong with our expression.

A simple Haskell Program

We have been working with GHCi for a while now. What about writing Haskell code that we can actually compile and execute? Use your favourite text editor and enter the following:

1
2
3
4
5
6
7
8
-- file: LineCount.hs
-- lines beginning with "--" are comments.

main = interact lineCount
    where lineCount input = show (length (lines input)) ++ "\n"

-- Original code from Real World Haskell
-- (http://book.realworldhaskell.org/read/getting-started.html#WC.hs:main)

Then just create any text file with some number of lines of text. You can also download them here. Don’t worry about understanding the code for now. Once ready, just run the program with the following. If everything goes well, you should see the number of lines of text in your text file.

runghc LineCount < MyTextFile.txt

Hurray! You just wrote your first Haskell real-world program!

Okay, that’s all I have for this post! Thanks for reading it! I’ll be working on the next post soon!

Hello World

| Comments

How can anyone who has done at least a tiny bit of programming not start everything with a Hello World? So here it is, the first post of my blog.

Reason For This Blog

1
2
3
4
5
6
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort smaller) ++ [p] ++ (quicksort bigger)
    where
        smaller = filter ( < p ) xs
        bigger = filter ( >= p ) xs

For those who are not familiar, this is the implementation of the Quick Sort written in Haskell. Look at it. Just look at it. Now compare it to the implementation in Java. Isn’t she a beauty?

The first programming language I learned was Java. We were mainly taught the concepts of object oriented programming. It was fun. Putting thoughts and ideas into lines of code, compile and see them run. That was when I fell in love with programming.

Several years later, I first learned of Haskell in my university days when I took a module called Programming Language Concepts. I fell in love with programming, again. It is a functional programming language. It is totally different from what I learned from Java. It is clean and concise. It is awesome.

I have since decided to continue to learn Haskell.

Dijkstra’s Letter

I recently came across this letter written by Edsger Dijkstra. It is one of the best letters I’ve seen about Haskell. It really got me inspired to start writing this blog about this great programming language that is lacking the attention it deserves.

It is not only the violin that shapes the violinist, we are all shaped by the tools we train ourselves to use, and in this respect programming languages have a devious influence: they shape our thinking habits.

I must say, ever since I started learning more on Haskell, I feel that I’m becoming a better programmer.

Goal

What I intend to write in this blog is my learning journey of the language. I’ll be referring to materials from these 2 books that are both available for free online: Real World Haskell and Learn You A Haskell For Great Good!. Ultimately, I want to master the language and functional programming. At the same time spread awareness and share the love for this great programming language.

In my next post…

I will be talking about the following:

  • Get your machine ready for Haskell
  • Trying out ghci
  • Lists
  • Write a simple Haskell program

References