++ efficiency. Reply
Mike Jones [EMAIL PROTECTED] writes on ++ efficiency how do I approximate its efficiency compared to adding one element at a time? In a "regular" situation, xs ++ ys needs the number of "steps" proportional to (length xs). This is according to the simplest Haskell program you could suggest for (++) - guess, what is this program? Does 1:2:3:4:5:6:7:8 execute faster than [1, 2, 3, 4] ++ [5, 6, 7, 8], where the first case is executed recursively in a function? This literally expressions the compiler is likely to evaluate at the compile time. They would both cost zero at the run-time. But if at the run-time ys = [5,6,7,8] is "ready", after this [1,2,3,4]++ys costs 4 "steps", while 1:2:3:4:5:6:7:8 costs 8 steps. The "lazy" evaluation makes the truth of these considerations depend highly on the concrete situation in the program. Also if some designer implements Haskell basing on some different internal model for the lists (God save!), then one could make (++) regularly cost 1 step ... Generally, beware of the (++) danger in some situations. -- Sergey Mechveliani [EMAIL PROTECTED]
English in basAlgPropos
I recall one particular point about Basic algebra proposal for Haskell http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/ Its English is not perfect. Naturally, the corrections are welcome. -- Sergey Mechveliani [EMAIL PROTECTED]
recent summary for basAlgPropos discussion
The recent state of basAlgPropos discussion reveals the important points enclosed below. You also will find its copy in the directory http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/ in separate file, notes1.txt, or such. -- Sergey Mechveliani [EMAIL PROTECTED] Hackers and snobs - Let us call for the recent basAlgPropos discussion a hacker any Haskell user who do not like to care of mathematics, especially, of its most abstract parts. And call a snob any user that feels it quite different. For example, I am a snob, and several other members in this list are too. I would like the committee to be a snob. The source and origin of the functional programming is snobby. But to my mind, the snobs of the Haskell community should respect and take care of the needs of hackers. And the hackers should not aggressively destroy everything they do not understand. Harmless for hackers, advanced for snobs I am going to prove (can I ?) that basAlgPropos is so. The approach is: do not mention advanced features in the hacker program, and the program would not bite you. Generally, the recent state of Haskell is so that it looses many- many useful scientific possibilities. And its aim has to be to recover this possibilities - preserving the room for the hackers, not forcing them to study any new notions. Few explicit categories, many implicit ones --- AddSemigroup ... Ring, EuclideanRing ... are the explicit categories - there are provided the *classes* for them. How the hacker uses them? One simply takes (+) from Additive, (*) from Multiplicative, dimRem from EuclideanRing - instead of Num, Integral of old Haskell-98. When one wants the instance for the type T with, say, (*), one needs to declare for it instance Set T -- skip implementation ! instance Multiplicative T where (*) = ... Also one writes, for example, zero x instead of zero `asTypeOf x`. One might also need to write instance ... compare_m (..) (..) = ...Just GT instead of old ... compare (..) (..) = ...GT (`compare', () being derived automatically from compare_m). I hope, the changes will not be essentially more than this. Is simplicity possible? --- Some people say here, that this is impossible, that the compilation errors become the run-time ones ... I do not see, so far, in what way these matters may occur serious. For the critics, it is a good point to provide some schematic examples. As to me, if the user, say, skips the advanced operation definitions like baseSet of Set, then, one's program does not rely on what baseSet produces. And the library implementation can be built so that such cases it would not essentially use the attributes in baseSet. For example, I like to skip for the user types the fromInteger instance in Haskell-98, for some reason. Sometimes my program makes by error some implicit use of fromInteger, which leads to the run-time error. First, this is not so a great tragedy. I find this place and improve and consider this expense as less than the benefits given by the above trick with fromInteger. But the main consideration is: the implementors of the basAlgPropos library can pay special attention to the flex usage of the advanced part of basAlgPropos. The difference is: the designers and implementors of Haskell-98, probably, did not expect some snob ignoring fromInteger. Let us mark also the possibility of *dummies*. For example, baseSet _ = dummy_baseSet -- the program does not expect this -- part to be really used compare_m = compareTrivially -- minimal partial ordering Together with the design implementation care, this is likely to satisfy the hackers. Implicit categories are for snobs - Hackers, ignore them! Also they can be rejected by the committee, the rest of proposal does not essentially depend on this feature. But I hope, they would not be rejected. FiniteSet, FiniteGroup, RingWithUnity ... are implicit. They are given as the *attributes*, mostly as the property names in the lists produced by `base' operations from explicit categories. For example, (baseSet _) yields osetProperties, and the latter list may contain (Finite,v). Depending on this v - [Yes,No,Unknown], the program can more precisely partially (and dynamically) solve in what real category the computation takes place. For example (Finite,Yes) means it operates in FiniteSet. A nice feature here is that thousands of useful categories for different user tastes may appear in this way, and this would not require introducing new standard classes and instances. Careless definition or usage of the attributes produced
Re: recent summary for basAlgPropos discussion
I think the way to proceed with basAlgPropos is to implement it outside the language as a library. (Since it redefines the basic arithmetic symbols and so on it will be necessary to tell the user to import Prelude() or qualified and perhaps provide an alternative version of the Prelude.) The GHC folks at any rate seem to be fairly open to allowing people to add their code to the GHC distribution, so basAlgPropos could be well distributed in this way. Then both hackers and snobs can take basAlgPropos or leave it as they desire. Should basAlgPropos become very popular (for example, as part of large symbolic algebra routines) then it will maybe be time to think of standardising it. At the moment I feel it would be better to let it evolve.
-fadvancedAlgebra sub-proposal
People, please, what would you say of the
-fadvancedAlgebra key proposal
contained in the middle of this letter?
This is new, I had not thought much about it and doubt what might be
wrong there. It is very short and, hope, can improve much.
--
Sergey Mechveliani
[EMAIL PROTECTED]
-
Marcin 'Qrczak' Kowalczyk [EMAIL PROTECTED] writes
basAlgPropos announces that the operations like `baseSet' also can
be ignored by everyone who is lazy to consider it.
"Ignored" means "made returning \"don't know\" or even bottom",
and this is a bad design.
First, such instance is useless. The information that something is
not known gives us nothing.
For some users - it gives, for others does not.
As with all operations in Haskell-98 too.
For example, I do not use fromInteger, and no tragedy occurs.
You should not skip it, unless this is an unfortunate case where
particular classes do not fit well into what we are defining and
there is not any good definition of fromInteger.
The situation with my application program is exactly as you describe.
And it often repeats with different users and different operations,
and there is no tragedy about this.
Second, such instance cannot be improved. It has been defined,
and there can be only one instance for a given class+type pair in
a program. If someone needs a more complete instance, he is stuck.
No. In the *standard* instances, say, for (,), Fraction ...,
it is defined thoroughly. And the user may use it or not.
For the user types and instances, it a business of the user how
(and whether at all) one is going to exploit such operation.
You should not force other programmers to make a decision: either
define poor instances or spend time writing instances that will
probably never be used.
In the worst case, the hacker defines one extra *dummy* Set
instance.
This is - in addition to the absolutely necessary
Additive, AddSemigroup, Ring
to appear. You may relax, the community will accept them, in my
proposal, or maybe, in someone's next.
Maybe, people would agree that this all is not so principal.
But I agree that this a nasty technical detail, politically
important. Here is the preliminary
advancedAlgebra key proposal
-
To introduce the standard compilation key -fadvancedAlgebra
Without this key, the compiler inserts automatically the dummy
definitions for all the necessary instances for the user types
from certain fixed list of "advanced" categories - like
Set, AddSemigroup, MulMonoid ...
--
For example, the user program exploits +, *, divRem for C a.
The user defines Additive, Multiplicative, EuclideanRing for C
- this is natural in this situation.
But suppose one does not want even to recall the fancy names
`Set',`AddGroup' ...
needed to define dummy super-instances for C a ?
Then, without -fadvancedAlgebra the compiler sees easily that
their instances are needed for T, adds the dummy ones and
reports a warnings.
I sometimes get warnings on skipping the operation definitions in
some standard classes. And find it natural.
Now, it would appear also the warnings of dummy instances.
People, how do you think, can this approach, minimally supported,
satisfy both the hackers and the snobs?
must think about Show instance, and define partial ordering first,
then make it total ordering.
What one can do without Show? It is needed everywhere.
Of course not! From all standard library types, in practice Show is
used almost only for numeric types, except some debugging messages.
OTOH almost all types are Ord.
[..]
There is no problem about this. In any case, the dummy Show can
be generated automatically, by the compiler, if the user skipped it.
Let it put for example,
showsPrec _ = ("Dummy Show"++)
Would you then cry that it had printed occasionally what you did not
like to see for T, if you had not bothered to define it for T ?
I admire, how people like to make problems from nothing instead of
looking for really serious questions related to the subject.
Superclasses are needed only:
- when our class makes little sense without the superclass, to
simplify contexts, or
- when a default method implementation requires that class, and we
feel that the importance of having such default implementation is
larger than the inconvenience of having a superclass.
"Only" or not only, but this is sufficient. Because we have to add
"
when our class makes little sense without the superclass
- in many particular situations that can be possibly created by
the user types.
"
This is a good reason to make Show a superclass.
At least - if this can be made in a manner
Show class on ADT with function
Hi, I want to put a function in an ADT and make the ADT an instance of Show. Like the following small example: data Fn = Fn (Float - Float) Int deriving Show But, I get the error from GHC as follows: Stimulus.hs:12: No instance for `Show (Float - Float)' When deriving classes for `Fn' Compilation had errors make: *** [Stimulus.o] Error 1 Is there any way to do this? Note that it would be ok to generate blank text. Thanks, Mike
non-standard basAlgPropos. Reply
George Russell [EMAIL PROTECTED] writes 05 May 2000 I think the way to proceed with basAlgPropos is to implement it outside the language as a library. [..] GHC [..] At the moment I feel it would be better to let it evolve. You mean: non-standard library. There is no need in decision to allow a thing out of standard. For example, free DoCon CA program written in Haskell already "evolves" for several years, already has right to evolve 100 years more, and the copyright of DoCon-2 allows it, in particular, to be included everywhere as a library without asking its author (only requires the appropriate reference). basAlgPropos is much simpler that DoCon, because it aims the standard. If I was asked to help basAlgPropos to evolve as non-standard, for me personally, this might have sense only as a messy, routine (and paid!) work. Because I already help to evolve DoCon CA program. This always was the work No 1. And it would be slightly better to base this DoCon thing on some better standard than exists. On the other hand, I do not complain much even on Haskell-98. This is why I said once "do not care much of what it would happen with basAlgPropos". Also I like, for example, the idea of a good Rule extension of the language. Why, I would probably, experiment with the nice Maude language and system. For thinking people there always exists a field, a standard is not the main in scientific programming. Generally - do not like to talk of standards. They are already silently built-in somewhere in each science. It remains only to extract them to the programming. Several persons in this list showed a great interest in new standard and spent a couple of letters to encourage me personally to write a thing. Maybe, I wrote wrong thing, do not know. It was spent 20 days to create it, assuming that the whole approach was developed for 2-3 years before. Hence, I should not avoid discussing it for several days and have a moral right to require from the committee considering it and issuing an official decision. Please, let us perform our duty. -- Sergey Mechveliani [EMAIL PROTECTED] http://www.botik.ru/~mechvel
Re: Show class on ADT with function
Mike Jones wrote: [...] data Fn = Fn (Float - Float) Int deriving Show But, I get the error from GHC as follows: Stimulus.hs:12: No instance for `Show (Float - Float)' When deriving classes for `Fn' [...] Functions are not an instance of Show, so you have to supply instance Show (a - b) where showsPrec _ _ = showString "function" or add `import ShowFunctions' (in the upcoming GHC 4.07's package lang). Cheers, Sven -- Sven PanneTel.: +49/89/2178-2235 LMU, Institut fuer Informatik FAX : +49/89/2178-2211 LFE Programmier- und Modellierungssprachen Oettingenstr. 67 mailto:[EMAIL PROTECTED]D-80538 Muenchen http://www.informatik.uni-muenchen.de/~Sven.Panne
Re: recent summary for basAlgPropos discussion
Fri, 5 May 2000 13:36:19 +0400 (MSD), S.D.Mechveliani [EMAIL PROTECTED] pisze: Let us call for the recent basAlgPropos discussion a hacker any Haskell user who do not like to care of mathematics, especially, of its most abstract parts. And call a snob any user that feels it quite different. How to call a person that does care about mathematics and about structure of numeric etc. types and classes in Haskell - but dislikes basAlgPropos, feeling it's extremely inelegant, complex, illogical and does not fit into the Haskell style at all? I'm not against the principle of redesigning this area. But I am against doing things that way, against very many aspects of basAlgPropos. I want Haskell to remain beautiful. The approach is: do not mention advanced features in the hacker program, and the program would not bite you. It will bite when another person in his library relies on instances like Set to be meaningful. It's easier to add an instance that was not present (and the compiler told so when somebody tried to rely on it), than to locate and fix an instance that was poorly written because it's presence was forced by artificial superclasses or badly designed grouping of overloaded operations into classes, not by any real need of that time. Also one writes, for example, zero x instead of zero `asTypeOf x`. This is one of many cases where I have no doubt basAlgPropos is poorly designed. Sample arguments are bad, because: 1. They present a confusing interface. This looks like a function, but the real meaning is a constant. Neither mathematics nor programming languages treat zero as a function from any unused number to the zero value. 2. They usually make code larger. Even when a constant is overloaded (instead of being only polymorphic), usually the exact type can be deduced from usage. Haskell is not C++, it can infer types from contexts of usage too. 3. They don't add any functionality or expressiveness. 4. They make interfaces inconsistent. Some constats have sample argument, some don't. Do you expext Nothing to have a sample argument?! 5. They hurt performance, Not always they can be optimized out. Of course they (or something other, like "data Tag a = Tag") must be present in cases where the rest of the type does not contain the type that we parametrize over, like in Haskell98's RealFloat class. Fortunately they are very few cases. Some people say here, that this is impossible, that the compilation errors become the run-time ones ... I do not see, so far, in what way these matters may occur serious. For the critics, it is a good point to provide some schematic examples. One party makes a polymorphic use of the cardinality function from your proposal. Another party defines a type, defines the Ord instance for it, is forced to define a Set instance because of your superclasses, but does not bother to provide cardinality, because you told it's not necessary if they don't want to use it. Now the first party, or some third party, wants to use the function using cardinality on the type mentioned. If a class were designed well, they would be two possibilities: - The second party indeed did not define cardinality. The compiler complains that the second type is not an instance of the class that implements cardinality. Then anybody can add it. - The second party did define cardinality. Everything works. But with your proposal, the third possibility arises: - We silently get an incorrect program that will bomb at runtime that it needs cardinality that has not been provided. For example, I like to skip for the user types the fromInteger instance in Haskell-98, for some reason. Sometimes my program makes by error some implicit use of fromInteger, which leads to the run-time error. This leads to the question whether the situation is common enough that fromInteger should be moved to a different class. (IMHO it's not common enough, you should define fromInteger for any numeric type, because it's almost always needed for numeric types, so it should remain in Num. Unless you use Prelude classes for things they are not designed for.) Let us mark also the possibility of *dummies*. For example, baseSet _ = dummy_baseSet -- the program does not expect this -- part to be really used compare_m = compareTrivially -- minimal partial ordering Together with the design implementation care, this is likely to satisfy the hackers. It does not satisfy me. Why should I be forced to make a dummy instance? A Set class is very poorly designed in itself. It is a superclass of almost all basAlgPropos classes, so it should really contain fundamental operations that almost all types support. But it has three methods: - belongs, that does not make any sense for me and I could not hear any rationale where it could be ever used. - compare_m, which
Re: -fadvancedAlgebra sub-proposal
Fri, 5 May 2000 16:53:12 +0400 (MSD), S.D.Mechveliani [EMAIL PROTECTED] pisze:
You should not skip it, unless this is an unfortunate case where
particular classes do not fit well into what we are defining and
there is not any good definition of fromInteger.
The situation with my application program is exactly as you describe.
And it often repeats with different users and different operations,
and there is no tragedy about this.
But it's an unfortunate exception. It should not be forced all the
time, saying that it sometimes happens so it must be good.
Second, such instance cannot be improved. It has been defined,
and there can be only one instance for a given class+type pair in
a program. If someone needs a more complete instance, he is stuck.
No. In the *standard* instances, say, for (,), Fraction ...,
it is defined thoroughly. And the user may use it or not.
I talk about new types I define, and standard instances that are not
needed by me but forced by superclass relationships.
For the user types and instances, it a business of the user how
(and whether at all) one is going to exploit such operation.
I don't want to answer the question how many elements my type contains
if the only thing I want is to let FiniteMap use my type as the key.
But I also don't want to prevent somebody from answering this question
himself and making use of the answer in a standard way if he has
such need.
It really can be done well. The simplest way it to put cardinality
either in a separate class, or in a class with some related operations
which are generally used and defined together.
In the worst case, the hacker defines one extra *dummy* Set instance.
No dummy instances at all!
advancedAlgebra key proposal
-
To introduce the standard compilation key -fadvancedAlgebra
Without this key, the compiler inserts automatically the dummy
definitions for all the necessary instances for the user types
from certain fixed list of "advanced" categories - like
Set, AddSemigroup, MulMonoid ...
No dummy instances, neither user-defined or compiler-generated.
They are not needed. If some library needs them, fix the library.
Or let it define them itself (I don't care what libraries I don't
use define), without forcing anybody to have a contact with this
ill design.
Please don't hide bad design under the carpet. It will not make it
better:-)
I sometimes get warnings on skipping the operation definitions in
some standard classes. And find it natural.
It is not natural. I always use -Wall and make my code warning-free,
excluding the development time of course. Warnings are good and
meaningful.
What one can do without Show? It is needed everywhere.
Of course not! From all standard library types, in practice Show is
used almost only for numeric types, except some debugging messages.
OTOH almost all types are Ord.
[..]
There is no problem about this. In any case, the dummy Show can
be generated automatically, by the compiler, if the user skipped it.
NO! It does not make any sense. Why on Earth should a type that is
not showable have the Show instance?
Let it put for example,
showsPrec _ = ("Dummy Show"++)
Would you then cry that it had printed occasionally what you did not
like to see for T, if you had not bothered to define it for T ?
I did not define it either because it's impossible (e.g. it's a state
monad implemented as a function) or because I wanted to write some
code quickly, and make non-essential instances later when necessary.
I want the compiler to refuse to compile a code which requires a Show
instance for such type in both cases. In the first case the code or
the usage of the code is broken anyway and needs to be fixed. In the
second case a real Show instance should be added.
I admire, how people like to make problems from nothing instead of
looking for really serious questions related to the subject.
basAlgPropos has tens or more of those little problems. They together
make the proposal inappropriate for any serious consideration to be
put into the core library in this form.
If they are so many misdesigns in simple places I understand, I wonder
how many are there in more complex places that I don't understand.
Superclasses are needed only:
- when our class makes little sense without the superclass, to
simplify contexts, or
- when a default method implementation requires that class, and we
feel that the importance of having such default implementation is
larger than the inconvenience of having a superclass.
"Only" or not only, but this is sufficient. Because we have to add
"
when our class makes little sense without the superclass
- in many particular situations that can be possibly created by
the user types.
"
This is a good reason to make Show a superclass.
It does not. Show is not necessary for () or any other Ord method
to be
Re: Show class on ADT with function
Fri, 05 May 2000 16:17:42 +0200, Sven Panne [EMAIL PROTECTED]
pisze:
data Fn = Fn (Float - Float) Int
deriving Show
Functions are not an instance of Show, so you have to supply
instance Show (a - b) where
Better supply a Show instance for Fn, not by deriving, but by
instance Show Fn where ...
Show instance for functions should not be needed. It is only for lazy
programmers who want to make a quick dirty instance, for debugging
perhaps.
--
__("Marcin Kowalczyk * [EMAIL PROTECTED] http://qrczak.ids.net.pl/
\__/ GCS/M d- s+:-- a23 C+++$ UL++$ P+++ L++$ E-
^^ W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
QRCZAK 5? X- R tv-- b+++ DI D- G+ e h! r--%++ y-
Re: Show class on ADT with function
Marcin 'Qrczak' Kowalczyk wrote: Show instance for functions should not be needed. It is only for lazy programmers who want to make a quick dirty instance, for debugging perhaps. And why not? There is no problem with Showing functions with finite domains. For example, try: module ShowFun where instance (Show a) = Show (Bool - a) where show f = show ((f True),(f False)) instance (Show (a - b - c)) = Show ((a,b) - c) where show f = show (\ a b - f (a,b)) If you load this into Hugs (with -98) then you will be able to show functions like and not,and much more complicated ones like (\ (a,(b,c)) (d,e) - length (filter id [a,b,c,d,e])) Indeed since show returns a string which can be infinite I suppose you can just as well define instance (Show a) = (Show (Int - a)) But you will need to be clever about interleaving if you want to be able to show functions of type Int - Int - a in such a way that all strings are distinguishable. (I realise this message has no serious purpose whatsoever and apologise to people whose time it has wasted. But it's the weekend after all.)
