Invisible wrote:
> I have absolutely *no clue* what the hell any of that means. But try it 
> yourself here:

That makes sense except to the extent that I don't know what LIFT{[]} means.

> Indeed, all Haskell types are ADTs. Except things like integers, 
> arguably. OTOH, you could claim that Integer is defined as
> 
>   data Integer = 1 | 2 | 3 | 4 | ...

An abstract data type has to define the operators also.

> As for "like say a stack", I'm not really sure what you mean.

Well, an ADT has to define the type in terms of the operations on that type, 
not in terms of a list of values/literals. So the ADT for "Either" would be 
something like

Left (Left x) = x
Right (Right x) = x

where the first word in each is a function call and the second is a data 
constructor.

A stack is usually defined as something like
new :: -> Stack  // Give me a new stack
empty :: Stack -> Bool  // Tell me if stack is empty
push :: (Stack, Value) -> Stack // Give me a new stack with the value pushed
pop :: Stack -> Stack // Remove value from top of stack
top :: Stack -> Value // Tell me what's on top

empty(new)    // New stacks are always empty
not empty(push(S, V)) // Nothing with something pushed is empty
S = pop(push(S, V)) // pop is inverse of push on all stacks for all values
V = top(push(S, V)) // top returns most recent thing pushed
// And I think there's one other rule you need to make it work, but
// I forget what it is. I could look it up if you care.
// It might involve showing that top(new) and pop(new) are bottom.


In other words, for an ADT, there is no indication at all of the 
representation of values. The value of the stack with 1, 2, and 3 pushed is 
actually
  push(push(push(new,1),2),3)
and not some list expression. *That* is an ADT.

The advantage is that you can prove things about the behavior without 
understanding what it's "supposed" to do. For example, you can see it's 
impossible to pop an empty stack, or to look at the top element of an empty 
stack, because there's no matching expression for top(new). You can also do 
things like prove you've covered all the possibilities, prove that one ADT 
is a superset of another, and so on.

> I wonder if this is why Linux doesn't "need" a defrag tool?

That and a number of other things like that, methinks. I wasn't trying to 
turn it into a Linux bash, tho, since a lot of other environments do this too.

-- 
   Darren New, San Diego CA, USA (PST)
   Why is there a chainsaw in DOOM?
   There aren't any trees on Mars.

Post a reply to this message