Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 [Haskell-tut] Lists
Index -> Programming, General Programming -> Functional Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
wtd




PostPosted: Fri Nov 19, 2004 5:07 am   Post subject: [Haskell-tut] Lists

Recap

We have integers, floating point numbers, characters, and strings.

What's new?

Lists are collections of a single type of data.

What does a list look like?

A simple list of integers looks like:

code:
[1, 2, 3, 4]


Of course, a simple range like this can be more succinctly represented as:

code:
[1 .. 4]


How is a list defined?

This really deals with the very first operator/function we'll see for dealing with lists.

code:
1 : [2, 3, 4]


Yields:

code:
[1, 2, 3, 4]


So, really, we can rewrite that as:

code:
1 : 2 : 3 : 4 : []


code:
[]


Of course, is an empty list.

That's nice, but...

Lists are roughly analogous to arrays in other languages, and there are similar operations available.

Finding the length of a list:

code:
length ["hello", "world"]


Getting the first element:

code:
head [42.3, 57.6, 98.2]


Getting everything else:

code:
tail [42.3, 57.6, 98.2]


Adding two lists together:

code:
[1, 2, 3] ++ [4, 5]


Finding any element in a list (in this case, the 3rd):

code:
[1 .. 5] !! 2


Finding if an element is in a list:

code:
elem "foo" ["foo", "bar", "baz"]


Or, using the infix form of any function which takes two arguments:

code:
"foo" `elem` ["foo", "bar", "baz"]


Which should read as "is foo an element of this list".

Now, if we want to apply a function to each element in a list, to square each:

code:
(** 2) `map` [1 .. 6]


Or say we want to filter a list:

code:
(> 2) `filter` [1 .. 4]


Another look at the last two

Haskell offers a special bit of syntactic sugar for list operations, called the list comprehension. Python borrowed this feature.

Squaring 1 through 6 can look like:

code:
[x ** 2 | x <- [1 .. 6]]


And the filter operation can look like:

code:
[x | x <- [1 .. 4], x > 2]


What about loops?

Loops and lists (or arrays) usually go hand in hand. Haskell has no looping construct. So how is "map" possible?

Recursion

Let's consider the map function again.

How do you suppose they do that?

Well, they apply the function to the first item in the list, then recursively do the same to the rest of the list. Obviously the result of mapping a function to an empty list is another empty list.

code:
map _ []     = []


The _ in this case indicates an argument, but one whose value we don't care about. In this case we're going to get the same result, no matter what function we pass to map.

code:
map f (x:xs) = f x : map f xs


The function argument in this case is "f".

code:
(x:xs)


Might look a bit familiar. It has that ":" we associated with building a list. Indeed, x is the first element of a list, and xs is the rest of the list.

code:
f x : map f xs


We call the function f with argument x, and merge it to the list returned by calling the function recursively for the rest of the list.

So, breaking down:

code:
map (** 2) [1, 2, 3, 4, 5]


We get:

code:
1 ** 2 : (2 ** 2 : (3 ** 2 : (4 ** 2 : (5 ** 2 : ([])))))
1 ** 2 : 2 ** 2 : 3 ** 2 : 4 ** 2 : 5 ** 2 : []
1 : 4 : 9 : 16 : 25 : []
[1, 4, 9, 16, 25]


Take another look

code:
map _ []     = []
map f (x:xs) = f x : map f xs


This is a basic pattern you'll find when it comes to recursion, and it provides all the power of a loop in an imperative language.

Another example: sum

The problem: given a list of numbers, find their sum.

First analysis: summing an empty list will always give us zero.

code:
sumList []     = 0


Second analysis: we can calculate the sum by adding the first element of the list to the sum of the rest of the list.

code:
sumList (x:xs) = x + sumList xs


code:
sumList [1 .. 4]


Breaks down to:

code:
1 + (2 + (3 + (4 + (0))))
1 + (2 + (3 + (4)))
1 + (2 + (7))
1 + (9)
10


Now a different take on this

So far we've been doing pretty simple recursion, and handling the recursion ourselves. There's a method which avoids this, called "folding".

Consider a deck of 52 cards which can represent a list metaphorically. They each have a number on them. To count them, we could add the top two cards and put a card with that value back on top of the deck. We then do the same thing all over again until we're left with one card with the final result.

One of the things we need in a fold is a function which takes two arguments which represent the two cards. Since our list might only have one element, we provide a starting value for the first time around. For a sum, we should start out with an intial value of zero.

code:
foldl (\a b -> a + b) 0 [1 .. 4]


code:
\a b -> a + b


Is a function. The only thing it lacks is a name.

Of course, we can simplify this even further by realizing that we don't need to construct the extra function.

code:
foldl (+) 0 [1 .. 4]


And we can partially apply the function to create a general sumList function.

code:
sumList = foldl (+) 0


Or even:

code:
sumList = (+) `foldl`0


One last thing

The "l" in "foldl" stands for "left". It starts on the left side of a list and works its way to the other end. The "foldr" function works identically except that it works through the list in the opposite direction.

Take some time...

I realize all of this will take some time to digest, so sit back and think about it a bit. Another good idea is to try the code I've posted to see that as weird as it looks, it works. Smile
Sponsor
Sponsor
Sponsor
sponsor
Mazer




PostPosted: Fri Nov 19, 2004 12:12 pm   Post subject: (No subject)

So far it looks almost exactly like Miranda. But can you tell me just what uses there are for which using a functional programming language would be an advantage? I see easy to use lists, but aside from that...
wtd




PostPosted: Fri Nov 19, 2004 2:51 pm   Post subject: (No subject)

Well, type safety. Every type error is going to be caught at run-time.

For Haskell at least, the fact that it's purely functional means that a function given the same arguments will always produce the same result. This means a good compiler can implicitly memoize.

Tail call recursion optimization. A basically factorial function, for instance:

code:
fact 0 = 1
fact n = n * fact (n - 1)


Can have the recursion optimized away into an iterative loop by a good compiler.

Type inference. You don't waste time writing out types if you don't want to.

Concise syntax. Consider the legendary Haskell quicksort:

code:
qsort []     = []
qsort (x:xs) = qsort lt ++ [x] ++ qsort gt
        where
                lt = [y | y <- xs, y <= x]
                gt = [y | y <- xs, y > x]


Compare it to a quicksort in C++. It pretty much has to be C++, since few other languages support generic programming well enough to give us a quicksort that will work on any data type for which <= and > are defined. Two quicksort functions in Turing, for instance, would have to be written to sort both ints and strings.
wtd




PostPosted: Fri Nov 19, 2004 8:46 pm   Post subject: (No subject)

An addition

To get a certain number of elements from the front of a list, use the "take" function.

code:
take 3 [1, 2, 3, 4]


Yields:

code:
[1, 2, 3]
Display posts from previous:   
   Index -> Programming, General Programming -> Functional Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 4 Posts ]
Jump to:   


Style:  
Search: