#2 HASKELL LISTS pt. 1 [Functional Programming and Formal Methods]

in #technology • 7 years ago (edited)


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

#programming #science #education #teaching
7 years ago in #technology by
$0.03
  • Past Payouts $0.03
  • - Author $0.03
  • - Curators $0.00
10 votes
Reply 5
Sort:  
  • Trending
    • [-]
     7 years ago  

    Thanks for taking the time. I want to learn Haskell to write better functional JavaScript. I was planning to start for a while but didn't really get to it until I saw your first post.

    [-]
     7 years ago  

    That's great. One more in the Haskell family :)

    $0.00
      Reply
      [-]
       7 years ago (edited) 

      BTW GUYS: TOTALLY FORGOT
      I don't know why my code sections look that f*cked up, anybody who can help? :o)
      //Even when I edit the post, sometimes it puts even more lines >:(

      $0.00
        Reply
        [-]
         7 years ago  

        I can recreate this bug by switching back and forth b/w plaintext markdown editor and WYSIWYG editor. It's a typical bug of crappy WYSIWYG editors. Not sure why it works this way.

        I suggest you only use plaintext editor and submit a bug report to Steemit devs, if there isn't already.

        [-]
         7 years ago  

        Congratulations @besick! You have completed some achievement on Steemit and have been rewarded with new badge(s) :

        Award for the number of upvotes
        Award for the number of comments received

        Click on any badge to view your own Board of Honor on SteemitBoard.
        For more information about SteemitBoard, click here

        If you no longer want to receive notifications, reply to this comment with the word STOP

        By upvoting this notification, you can help all Steemit users. Learn how here!

        $0.00
          Reply