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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
