On 2003-12-11T03:26:54-0500, FranklinChen@cmu.edu wrote:
> That printing code is not faithful to your intention, which was
> data SuperList a = SuperList a (SuperList [a])
> The code you wrote reflects the intention
> data SuperList a = SuperList a (Maybe (SuperList [a]))
> which is quite different.
If the printing code I gave is not faithful to my intention, then
neither is the data structure definition that you gave, even though
you explicitly asked me whether the definition you gave is faithful to
my intention. A C++ pointer can be either null or non-null; non-null
pointers can be expressed in C++ as references.
> C++'s NULL is a value, not a type, so it is impossible, as you correct
> indicate, to write a function template using an encoding of Maybe in
> which NULL is a Nothing and a pointer is a Maybe.
Are you drawing a distinction between C++ and Haskell here, in that
C++'s null is a value where as Haskell's Nothing is a type? But in
fact, Nothing in Haskell is a value, not a type.
In any case, I would be happy to switch as you did to the Haskell data
type definition
data SuperList a = SuperList a (Maybe (SuperList [a]))
However, the two approaches to coding in C++ you presented are not as
expressive as Haskell type classes. To be more concrete, let me provide
not just the above data type definition but also some Haskell code
manipulating that data type in a way that I (still) don't know how to
achieve with C++ (templates).
Here is a complete Haskell program incorporating the data type
definition above:
> module Main where
> data SuperList a = SuperList a (Maybe (SuperList [a])) deriving Show
> make :: a -> Int -> SuperList a
> make a 0 = SuperList a Nothing
> make a n = SuperList a (Just (make [a,a] (n - 1)))
> main :: IO ()
> main = getLine >>= print . make True . read
The crucial point here is that the "make" function takes an arbitrary
integer and returns a SuperList of that depth. The main program ("main"
above) simply reads an integer (say "n") from standard input and returns
a SuperList of that depth (namely "make True n").
Here are some sample sessions in which I use the same compiled program
to generate SuperLists of varying depth:
cruella:~$ ./a.out
0
SuperList True Nothing
cruella:~$ ./a.out
1
SuperList True (Just (SuperList [True,True] Nothing))
cruella:~$ ./a.out
2
SuperList True (Just (SuperList [True,True] (Just (SuperList [[True,True],[True,True]] Nothing))))
cruella:~$ ./a.out
3
SuperList True (Just (SuperList [True,True] (Just (SuperList [[True,True],[True,True]] (Just (SuperList [[[True,True],[True,True]],[[True,True],[True,True]]] Nothing))))))
cruella:~$ ./a.out
4
SuperList True (Just (SuperList [True,True] (Just (SuperList [[True,True],[True,True]] (Just (SuperList [[[True,True],[True,True]],[[True,True],[True,True]]] (Just (SuperList [[[[True,True],[True,True]],[[True,True],[True,True]]],[[[True,True],[True,True]],[[True,True],[True,True]]]] Nothing))))))))
cruella:~$ ./a.out
5
SuperList True (Just (SuperList [True,True] (Just (SuperList [[True,True],[True,True]] (Just (SuperList [[[True,True],[True,True]],[[True,True],[True,True]]] (Just (SuperList [[[[True,True],[True,True]],[[True,True],[True,True]]],[[[True,True],[True,True]],[[True,True],[True,True]]]] (Just (SuperList [[[[[True,True],[True,True]],[[True,True],[True,True]]],[[[True,True],[True,True]],[[True,True],[True,True]]]],[[[[True,True],[True,True]],[[True,True],[True,True]]],[[[True,True],[True,True]],[[True,True],[True,True]]]]] Nothing))))))))))
It does not suffice in C++ to simply define a Show class with a virtual
member function for printing to an ostream, because that solution does
not extend to
- comparing two SuperLists of possibly different depth for
equality (say by overloading operator==);
- storing multiple SuperLists of possibly different depth in a single
container, say vector.
Two SuperLists should be compatible for equality comparisons or storage
in a homogeneous array iff their root type ("a" above) is the same, even
if they may be of different depth. Indeed, different branches of the
same SuperList may be of different depth, so a C++ solution that encodes
the depth or shape of a SuperList in its type is overly specific. On
the other hand, two SuperLists whose root types are different should not
be eligible for equality comparisons, even if they are both printable to
ostreams.
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
Remember 9/11 * "It's untidy. And freedom's untidy. And free people are free
to make mistakes and commit crimes and do bad things." -- Donald Rumsfeld
Attachment:
signature.asc
Description: Digital signature