[Haskell-cafe] Collections

[Andrew Coppin]

Tillmann Rendel wrote:
> 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;
>   }
> }

OK, I don't even understand that syntax. Have they changed the Java 
language spec or something?

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

I just observe that in most programs, almost all looping constructs are 
to do with looping over *collections*, and it doesn't really matter what 
kind of collections they are...

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

Sadly, in Haskell you can't do that to "collections" that can only 
contain a specific type of element. I'm kinda hoping that Associated 
Types will fix this...?

>> 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?
I don't even understand that... :-S