Zip is simple. No mind-bending new abstractions here. Zip is one of quite a number of "tools" for dealing with lists. If you haven't figured it out already, a big part of learning Haskell is learning to think in terms of lists. It turns out that many of the things you use loops for in imperative languages can be handled using a list. Once you start thinking about your problem in the form of a list, Haskell has many things on hand to help you.
The idea with "zip" is to start out with two lists and end up with one. In general the lists are of equal length, but not necessarily. "Zip" comes in several flavors.
First we take a side trip to discuss tuples. A tuple is like a short list. Perhaps the most common tuple has 2 items and is called a pair. It is written with parenthesis and looks like this:
(a,b)The reason for diving into this is that "zip" generates a list of 2-element tuples (i.e. "pairs"). It looks like this:
newlist = zip [ 1, 2, 3 ] [ 100, 200, 300 ]This yields: [ (1, 100), (2,200), (3,300) ]
newlist = zipWith fn list1 list2Here fn is a function that takes 2 arguments, and you should be able to guess what happens. Consider our two lists from above and supply a function to add elements together:
newlist = zipWith (+) [ 1, 2, 3 ] [ 100, 200, 300 ]This yields: [ 101, 202, 303 ]
Just for the record there is "zipWith3" that takes 3 lists, a function and yields a new list.
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)I ask for "fib 13" and I get "233", which is correct but not as interesting as what follows.
Suppose I want all of the Fibonacci numbers! Let's just ask for them all (there are a lot).
Here is the classic Haskell code to "get 'em all" --
fibs = [0,1] ++ zipWith (+) fibs (drop 1 fibs)Rather than asking Haskell to print them all, we make a shorter list of the first 14 and ask Haskell to print that for us:
main = putStrLn $ show $ take 14 fibs [0,1,1,2,3,5,8,13,21,34,55,89,144,233]If you want element 13 from this list (or any list) you use this syntax to fetch it:
value = fibs !! 13The original line of code to generate these is worthy of quite a bit of discussion.
First of all, it generates and infinite list. This is perfectly OK, even good in Haskell. The trick is that Haskell is lazy. It doesn't actually do anything until it absolutely needs to. In effect it says, "yeah, I know how to do that, and I'll remember if you ever ask me to do something with it". Beyond that, when we finally reference "fibs" in the "take" function it doesn't generate any more of the list than is actually needed. No infinite loop with the computer going off into the weeds forever and filling memory.
All that aside, note the recursion on the "fibs" function. We start the list off with the two elements 0 and 1, the concatenate a list which will follow. That list is generated by zipWith, and it zips one list against the same list with the first element discarded. So the zipping goes 0+1, 1+1, 1+2, 2+3, 3+5, ...
They were first described by Leonardo of Pisa (also known as Leonardo Fibonacci) in 1202! They arose in a hypothetical calculation invoving the population of breeding rabbits. The question was, how many rabbits would we have in a years time. We start with a pair of breeding rabbits. A new pair is born every month, and after a year becomes fertile. No rabbits ever die.
Knuth has a section on Fibonacci numbers in his first book "Fundamental Algorithms" on page 78 (section 1.2.8) with many interesting bits of information. Many books have been written. They are involved with fractals, or can be. Knuth mentions a publication called "The Fibonacci Journal". They show up in all kinds of unexpected places.
Tom's software pages / tom@mmto.org