[Haskell-cafe] Collections

[Tillmann Rendel]

Andrew Coppin wrote:
>> [...] type (a,b) [...]
> 
> That's a rather special type; I haven't seen anything remotely 
> like it in any other language.

This type isn't that special in Haskell (apart from being 
syntax-sugared), it could be defined as

   data Pair a b = Pair a b

The equivalent of this definition introduces pairs in other languages, 
too. Consider Java:

public class Pair<A, B> {
   public A fst;
   public B snd;
   public Pair(A fst, B snd) {
     this.fst = fst;
     this.snd = snd;
   }
}

But there's Lisp, wich doesn't allow custom algebraic data types, but 
instead build all data from pairs. They are called cons cells, and could 
be defined like this in Haskell:

   data Cons = Nil | Cons Cons Cons

In Lisp, pairs are indeed special.

> A tree represents a recursive loop quite nicely. ;-)

What's a recursive loop?

> My point of course was that an array is a loop just as much as a list 
> is. 

No, it isn't. A loop has the following properties:

   (1) you can access only the current value
   (2) you can move only forward by computing some new current value

A (single linked) list has the following properties:

   (1) you can access only the current value
   (2) you can move only forward by following the next pointer

An array has the following properties:

   (1) you can access each value
   (2) you don't need to move around

In a lazy language, "following the next pointer" triggers "computing the 
new value", so loops are similar to lists, but different from arrays.

> [...] whichever way it's implemented internally. 

The point is: Some usage of Haskell lists is internally implemented as 
loops. for example this haskell code

   let result = 1 : zipWith (+) result result in result !! 10

is equivalent to this c code

   int result = 1;
   for (int i = 0; i < 10; i++)
     result = result + result;

and is hopefully compiled to something like this c code.


Of course, you can loop over most collections, in the sense of 
repeatedly running some code for each element. This is expressed in 
Haskell in a bunch of type classes, most notably Functor.

> Same goes for a set. Or even a dictionary (looping over key/value
> pairs), whichever way it's implemented internally.

I take your "wichever way" to apply to all collections you mentioned. 
Let's consider this set representation:

   type Set a = a -> Bool

   dual a x = not (a x)
   member y a = a y
   notMember y a = dual a y
   empty y = False
   insert x a y = x == y || a y
   remove a x y = x /= y && a y
   union a b y = a y || b y
   intersection a b y = a y && b y
   difference a b = intersection a (dual b)
   filter = intersection

(Function names and their meaning is taken from Data.Set. a and b stands 
for sets, x and y for set elements and f for some function. the dual set 
is the set containing all elements except those in the original set)

What has a set represented like this in common with a loop?

   Tillmann