Wed Jun 20 20:43:25 EDT 2007

```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
```