Re: [Haskell-cafe] Collections

21 Jun 2007


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