Official haskell logo! :)

Hi everyone, I'm really happy to see that you guys enjoyed the first part of the series about Haskell and proving your programs. All lessons are listed down below.

Last time we looked at the very basics of Haskell and I gave you a short overview of why Functional Programming Languages are cool.
This time I'll give you the basics of lists in Haskel. These are an essential part of the programming language. We'll be looking at how they work and how you can use them and how you can prove the correctness of your recursion when using lists.

List 

Basics

Last time we've seen different base types such as Int, Bool, ...
Lists are a type, too. In languages like for example Java you declare a variable as a list of Strinks like this:

List<yourType> list;

In Haskell lists are of course generic, too. So you can use them with all types that are available.
Lists in Haskell look as follows:

[1,2,3,4,5]

But this is actually only syntactic sugar they provide. This representation is exactly the same as this one:

1:(2:(3:(4:(5:[]))))

It's okay to use the first way but you'll have to keep in mind how the actually look like if you want to prove them.

• The empty list is simply and always: []
• A non-empty list looks like this: (x:xs)

What does that (x:xs) mean?
It's simple: x is the first element and xs are the following elements as a list.
In our example list

• x would be 1
• xs would be [2,3,4,5] = 2:(3:(4:(5:[])))

The empty-list also indicates that no elements are coming anymore.

How can write what generic type our list is?
Let's say you want to write a function that takes a list of integers as an argument and returns a list of Strings, you would write it like this:

intToString :: [Int] -> [String]

So in general we can say for a type T, we write [T] when the elements of list are of type T.
So if we have a list (x:xs) we say that x has the type T and xs the type [T] and the elements of xs have type T.

Standard functions with lists

• length: Takes a list as an argument and return how many element are in there
• ++ : appends a list at the end of another list
  Just a short annotation: "++" has they type [T] -> [T] -> [>T] and ":" has the type T -> [T] -> [T]. This means that they're not equivalent and you can't write 1 ++ [2,3,4] instead of 1:([2,3,4]) . You would have to write then [1] ++ [2,3,4] for the equivalent result.
• head return x of a list (x:xs) (this means the first element), tail returns the xs of a list (x:xs).
• sumList
  this looks like :

sumList :: [Int] -> Int    -- This is the type of the function

sumList list       -- here's the function

 | (list.length == 0) = 0   -- end of recursion

 | otherwise = (head list) + (sumList (tail list))   -- recursion

As you see we use recursion for doing that. No loops!!!
But you can write your code more readable then the one above if you write it likes this:

sumList :: [Int] -> Int

sumList [] = 0       -- Base case again, end of recursion

sumList (x:xs) = x + (sumList xs)    -- Recursion

This makes the code much more readable. Instead of using guards you're writing functions for each seperate case. As you see, the type declaration doesn't need to be written again.

Patterns

The arguments are checked if they have the proper form. so therefore you won't be able to create "wrong" lists. You'll only be able to create lists that are matching the pattern you're giving when saying the type of the function.

Patterns are inductively defined like this:

•  Constants: −4,  's' , True, [ ]
•  Variables: x, foo Wild card:
•  Tuples: (p_1, p_2, . . . , p_k), where pi are patterns
•  Lists: (p_1 : p_2), where p_i are patterns 

Okay, we didn't look at tuples but I don't think it's necessary.

HOMEWORK part 1:

I'd like to give you some homework now:

Write a insertion sort program in Haskell. You can you following skelletton:

insertionSort :: [Int] -> [Int]



--this is your part



insert :: Int ->> [Int] ->> [Int]     --this is a helper function

--you'll have to implement this too ;)

Tips on writing in Haskell:

1. define the type (I already did this for you in the homework)
2. enumerate the cases
3. define the simple cases
4. define the others
5. (simplify your version)

I'll provide the solution next time or maybe in the comments, not sure how. If you have questions feel free to write your question below in the comment. The same goes also for solutions, you can submit them in the comment section!
Tell me please if you prefer the solution in the comments, in the next post or in this post (I'll edit it then)!!!

List comprehension is awesome

Something I personally love about Haskell is that you can generate Lists like you can generate Sets in Math.

Let's say in Math you want the set of numbers that are in the set {1,2,3,...,100} and dividable by 2. You would simply write:
{ x | x element of {1, ... , 100} and x mod 2 = 0}

In Haskell it's nearly the same, you can write there

[ x | x<-[1 ... 100], (x 'mod' 2 == 0)]

* [1 ... 100] generates a list from 1 to 100, but you could replace these two numbers for generating another list of course

• <- means that x is element of
• different predicates (boolean values) are seperated with a ','
• You can add as many predicates as you want of course

I hope you enjoyed part 1 about List in Haskell. Next time we'll look at much more functionalities of lists in Haskell. AND we'll learn how to proof programs using list. So stay tuned, work on your skills and enjoy your day (or evening or whatever time it is in your time zone when you're reading this :D )

If you want to praise the Lord for Haskell, have any question, solution or whatever you want to share with us about Haskell, comment below. I would love to read again from you guys.

Cheers!

All Lessons

Lesson 1: Introduction to Functional Programming and Formal Methods

Lesson 2: Haskell Lists Part 1