Hello Malcolm, Thursday, February 23, 2006, 1:58:36 PM, you wrote: MW> People often overlook the useful facility of the module system to group MW> multiple common imports into a single re-exporting super-module. With MW> my proposal, you would simply replace the implicit "import Prelude" with MW> an explicit "import Prelude.Standard" (or use a build flag like MW> -fimplicit-prelude, or +98). MW> The idea is that backward compatibility with the old Prelude is MW> preserved as much as possible, but the experimental ability to replace MW> or remove parts of the Prelude is gained. import Prelude ($) can't solve this problem? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Malcolm Wallace wrote:

Yes, many trivial programs would acquire one extra import decl - is that such a big deal?

No, but overall it feels like a slight loss, because I'd expect the modules that gained a line to be shorter on average, and adding a line to a shorter module seems like a bigger deal than deleting a line from a longer module. The impact would be especially noticeable on one-liners like main = putStr (s++show s) where s="main = putStr (s++show s) where s=" In fact, this suggests a compromise: how about implicitly importing the Prelude only if the module header is omitted? That way there'll be no impact on short (single-module) programs. -- Ben

Malcolm Wallace writes:

One of the problems with the current mechanism for overriding Prelude definitions, is that every module that /uses/ such an entity must also explicitly hide the original Prelude:

I guess I don't quite understand what you are trying to achieve. Case one: existing project where you want to replace the Prelude Subcase a: the project already has a dummy module MyPrelude which just reexports the Prelude, and which is imported everywhere. - Great, all you need to do is modify MyPrelude! - Benefit from your proposal: you could skip import Prelude () from all .hs files (or -fno-implicit-prelude from your Makefile) - Drawback: anybody actually *do* this in real code without concrete plans for Prelude replacement? Subcase b: you don't have a MyPrelude. - Too bad, you need to modify all your .hs files *anyway* (Unless the good and benevolent secret keepers of the compiler code would implement a -fprelude-is MyPrelude switch) Subcase c: you want an alternative Prelude only in some of your files. Well, you are going to need to modify those files. At least you get to leave the rest alone. Case two: a new project with a different Prelude Well, if you're starting a new project, you can of course choose your own imports as you wish. Currently, the cost in one extra line in each file or the -fno-implicit option. I don't think saving one line from each file in projects using alternative Preludes justify adding one line to each file in projects using the standard Prelude. If there is any reason to think custom Preludes will outnumber the standard one, I'll change my mind. This sounds like yet another feature that is greatly interesting and wonderful to language hackers, and mostly annoying to the average programmer - partly by requiring extra overhead and boilerplate stuff, and partly by breaking old code. To summarize: * I don't think this is a good solution to name clashes; to use e.g. Set (and, hey, I agree with Okasaki and you that it should probably be used more instead of lists) I would need to use fine-grained imports management which adds administrative overhead. (A simple rename of a couple of offending identifiers would solve the problem. Why not 'isEmpty' instead of 'null', for instance?) * The standard Prelude is IMO going to be vastly more common than custom replacements. Custom Prelude users are also likely to be more accomplished Haskell programmers. Any administrative burden should be on the custom Prelude users. * That said, I'm all in favor of a switch to tell the compiler to use a custom module instead of the implicit Prelude. Or perhaps more generally: provide an implicit, project-wide import? Something like: ghc --make -fno-implicit-prelude -fimplicit-import MyPrelude Main.hs * Much of my resistance would go away if I had better tools to manage module interfaces more automatically. As it is now, import/export administration is already enough of a chore to be noticeable. -k -- If I haven't seen further, it is by standing in the footprints of giants

Ketil Malde wrote:

...

One of the problems with the current mechanism for overriding Prelude definitions, is that every module that /uses/ such an entity must also explicitly hide the original Prelude:

I guess I don't quite understand what you are trying to achieve.

The problem, as I see it, is that the Prelude steals too many good names from the user. For instance, there are complaints about the Numeric class hierarchy being inconvenient. So if you want to re-define arithmetic using groups, rings, and whatnot, then you must really use new names for (+), (*), etc, or force every user module to hide the Prelude. Neither alternative is terribly attractive.

* The standard Prelude is IMO going to be vastly more common than custom replacements. Custom Prelude users are also likely to be more accomplished Haskell programmers. Any administrative burden should be on the custom Prelude users.

A valid point. At the moment however, I think the burden on custom users is too high.

This sounds like yet another feature that is greatly interesting and wonderful to language hackers, and mostly annoying to the average programmer - partly by requiring extra overhead and boilerplate stuff, and partly by breaking old code.

There may well be other (small but) breaking changes in Haskell-prime. We shouldn't break things just for the sake of it, but this is an attempt to make the language smaller rather than to extend it.

* That said, I'm all in favor of a switch to tell the compiler to use a custom module instead of the implicit Prelude. Or perhaps more generally: provide an implicit, project-wide import? Something like:

ghc --make -fno-implicit-prelude -fimplicit-import MyPrelude Main.hs

Yes, there may be other ways to achieve the same goal.

* Much of my resistance would go away if I had better tools to manage module interfaces more automatically. As it is now, import/export administration is already enough of a chore to be noticeable.

Agreed. Regards, Malcolm

Malcolm Wallace writes:

you would simply replace the implicit "import Prelude" with an explicit "import Prelude.Standard" (or use a build flag like -fimplicit-prelude, or +98).

Why not keep it implicit? If you want the alternative behavior, you know where to get it (import Prelude (), -fno-implicit-prelude, etc). This way, you avoid breaking a lot of existing code, and also a lot of "hello world"-class programs could be written without any explicit imports or special tricks. Any programs written to use a more granular set of Prelude modules, would likely need an array of imports anyway, so the loss would be less in that case.

Some data-structures people (e.g. Chris Okasaki) are of the opinion that lists tend to be over-used (because they are built-in), when other datatypes might be much more appropriate.

Hmm...so the best way to educate programmers about this is to make lists harder to use? :-) Anyway, I'll see your Okasaki, and raise you one Simon Thomson (since "The Craft.." is the only Haskell book I have on my desk at the moment). Lists aren't mentioned until chapter 4, but chapter 4 and 5 discuss lists, chapter 5 is called "Generalization", but as far as I can tell, still talks exclusively about lists, and in the remaining chapters, there are lists on nearly every page. Over-used, perhaps, but the fact is that lists are - like it or not - a staple of FP in general, and Haskell in particular. Now, I'm sure a lot of uses for List could be replaced by more specific and appropriate types: Stack, LazyStream, IterationMonad, Deque, FingerTree etc etc. But this adds complexity to your program - if a list does the job well enough, why not use it? I'm reminded of one of the XP idioms: always first try to solve the problem in the simplest way that can possibly work. </hubris> :-) -k -- If I haven't seen further, it is by standing in the footprints of giants

John Meacham wrote:

On Thu, Feb 23, 2006 at 10:58:36AM +0000, Malcolm Wallace wrote:

...

Some data-structures people (e.g. Chris Okasaki) are of the opinion that lists tend to be over-used (because they are built-in), when other datatypes might be much more appropriate.

While this may be true of lesser languages and compilers, for a whole lot of stuff lists end up faster and more efficient than other data structures.

I think the issue here is not to decide between lists or trees, but to write programs in such a way that this decision is not made too early and can be easily changed later: it is between using a concrete collection data type and an abstract one (a.k.a. type class). We had this discussion before. respectfully submitted, -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------

Cale Gibbard wrote:

This is exactly why lists are so common. If people ask why lists are so common in lazy functional languages, they ought also to ask why loops are so common in imperative languages.

A loop is a sequence of actions. In FP, I don't typically have actions, rather I collect values, so I'd need several collections types, among them: sequences, and among them: classical left-biased lists. I admit that my typical Haskell program does use such lists all over the place, but mostly in monad comprehensions: do x <- ... ; guard ; let ... ; return ... and often it's a list only because there is no such syntactical convenience for, e. g. Sets. (I have to write lots of setToList/mkSet, which look plain ugly.) Even if I really want sequences, I rarely rely on the left-biased representation. (E. g. in the above example, there's no visible pattern matching on the 'cons'.) For reference, in Java, List<> is an interface, not a type (it has instances like LinkedList<> and ArrayList<>). And, there's nice syntactic sugar for looping over collections: Collection<E> c; for (E item : c) { ... } (it hides the pre-1.5 Iterator.hasNext/next stuff. I'd say this is an example of moving away from a left-biased representation, or at least freeing the programmer from having to think about it). Respectfully submitted, -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------

Malcolm Wallace wrote:

Johannes Waldmann wrote:

...

For reference, in Java, ... there's nice syntactic sugar for looping over collections: Collection<E> c; for (E item : c) { ... }

In Haskell, this is called 'fmap'. :-)

OK, then show me an "instance Functor Set" so that I can use it :-) -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------

Malcolm Wallace wrote:

But if contexts-on-datatypes worked correctly,

data Set a = Ord a => ....

then even the "real" map from Data.Set:

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

could be an instance method of Functor.

I'd love that. But I don't quite understand: do you think this is/should be possible with: current Haskell? Haskell-Prime? Current ghc (what extensions)? -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------

On 2/28/06, Johannes Waldmann wrote:

Malcolm Wallace wrote:

...

But if contexts-on-datatypes worked correctly,

data Set a = Ord a => ....

then even the "real" map from Data.Set:

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

could be an instance method of Functor.

I'd love that. But I don't quite understand: do you think this is/should be possible with: current Haskell? Haskell-Prime? Current ghc (what extensions)?

as Oleg: {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module Map where import qualified Data.Set class MyMap f a b where myMap :: (a -> b) -> f a -> f b instance (Functor f) => MyMap f a b where myMap = fmap instance (Ord a, Ord b) => MyMap Data.Set.Set a b where myMap = Data.Set.map Jim

On 3/1/06, Johannes Waldmann wrote:

But my point was that I want to use "do notation" for Sets (in fact, for any kind of collection) so I'd need the original Functor and Monad.

I understand this for Monad. Why not just redefine Functor, Oleg-style?

I couldn't use ghc's Rebindable Syntax feature because the types for (>>=) would not match? http://www.haskell.org/ghc/docs/6.4/html/users_guide/syntax-extns.html#rebin...

Good news, everyone! http://www.haskell.org/ghc/dist/current/docs/users_guide/syntax-extns.html#r... That looks good to me! Jim

Marcin 'Qrczak' Kowalczyk writes:

...

But if contexts-on-datatypes worked correctly, data Set a = Ord a => .... then even the "real" map from Data.Set: map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b could be an instance method of Functor.

fmap ($0) . fmap const :: Functor f => f a -> f a

When applied to Set Int, how would it represent the intermediate set of functions? Or if it was disallowed, on what basis?

Clever example. The intermediate set is :: Set (Int->b->Int), which does not satisfy the construction constraint (Ord a) => Set a. But persuading the type system to reject this is tricky I agree. I'm not a type hacker, so I don't know how to go about it. I suppose if the complete set of class instances for the entire program were known, then you could have a negation predicate, asserting that the intermediate type (Int->b->Int) does not have an instance of Ord, and somehow record this in the type environment fmap ($0) . fmap const :: (Functor f, not Ord a) => f a -> f a But then, there are a whole host of classes that (->) is not an instance of, so this is pretty useless because the constraints will grow enormously for little benefit. In short, I suppose the reason contexts-on-datatypes are as they are currently, is because no-one yet knows how to solve your example. Regards, Malcolm

On 28/02/06, Johannes Waldmann wrote:

Cale Gibbard wrote:

...

This is exactly why lists are so common. If people ask why lists are so common in lazy functional languages, they ought also to ask why loops are so common in imperative languages.

A loop is a sequence of actions. In FP, I don't typically have actions, rather I collect values, so I'd need several collections types, among them: sequences, and among them: classical left-biased lists.

Sure you do, you have pure functions, there are lots of those. Further, you have things like sequence, which turns a list of monadic actions into a monadic action returning a list of results, and mapM, which is just mapping a function to construct those actions over a list before sequencing them. Numerical algorithms involving iteration can get quite a lot of flexibility out of lists, using them to represent the output and intermediate values of the algorithm at each iteration. These lists are lazy of course, so that you can just take as many iterations off as you need, and since it's so nicely explicit, it's comparatively easy to determine where you'd like to chop, and to apply higher-order methods of reducing error. See "Why Functional Programming Matters" for some brilliant examples. http://www.math.chalmers.se/~rjmh/Papers/whyfp.html

I admit that my typical Haskell program does use such lists all over the place, but mostly in monad comprehensions: do x <- ... ; guard ; let ... ; return ... and often it's a list only because there is no such syntactical convenience for, e. g. Sets. (I have to write lots of setToList/mkSet, which look plain ugly.)

Even if I really want sequences, I rarely rely on the left-biased representation. (E. g. in the above example, there's no visible pattern matching on the 'cons'.)

Then perhaps you're missing out :) It sounds like you might be using lists like a strict functional programmer would, but not really relying on the laziness aspect. When you start doing so, it becomes much more apparent why lists are so special, and, for the many of the places where they work, AVL trees, for example, just wouldn't do. (Not that there's anything against AVL trees, it's just that they're not any kind of a substitute for lists in these common lazy functional programming cases.)

For reference, in Java, List<> is an interface, not a type (it has instances like LinkedList<> and ArrayList<>).

And, there's nice syntactic sugar for looping over collections: Collection<E> c; for (E item : c) { ... } (it hides the pre-1.5 Iterator.hasNext/next stuff. I'd say this is an example of moving away from a left-biased representation, or at least freeing the programmer from having to think about it).

None of that is lazy, so it just isn't the same thing at all. The important point is that the elements and structure of the collection are being constructed one at a time as you iterate over it, and they are easily garbage collected as soon as you're done with them. That's what allows you to say "hey, these are actually loops which just haven't happened yet". Only a list can really easily provide that for linear iteration through a collection of values. Certain trees can come close, (with a logarithmic additional space hit) and trees are quite useful for directed searching, but they don't replace the high position that lists have, just as non-linear forms of recursion don't quite replace common linear recursion. (Look at some imperative programs and count the loops and linear recursions compared with the number of general recursive functions which are not linear recursive.) Lists in the list-monad/list-comprehension usage are nearly trees anyway, due to the means by which they are computed, but you can always think of them as simple lists, or even as single nondeterministic values (due to the monadic structure), which is pretty neat. You can prune the tree by guards or the empty list, and branch by using bind. In some sense, you're defining a long reified loop which is strung along the leaves of a nonlinear recursive call tree. You're not forced to look at it that way, though, which makes things easy to think about when you're actually programming. It's also what makes the list monad (and isomorphic nondeterminism monads) really powerful. - Cale

On Tue, Feb 28, 2006 at 08:52:00AM +0100, Johannes Waldmann wrote:

Cale Gibbard wrote:

...

This is exactly why lists are so common. If people ask why lists are so common in lazy functional languages, they ought also to ask why loops are so common in imperative languages.

A loop is a sequence of actions. In FP, I don't typically have actions, rather I collect values, so I'd need several collections types, among them: sequences, and among them: classical left-biased lists.

I think the point was that lists in haskell trancend just being a collection type or a data structure. They are a generally useful tool for composing functions. And like cale said, they often subsume loops and all sorts of other control constructs. I mean, even a for loop in haskell is done as mapM action [0..10] I'd say _most_ uses of lists are deforested away because they are used to express control and dataflow and arn't actually used as persistant structures. demoting them to just being a 'collection type' would be a disservice. That they can be used as a collection is a bonus, but not their main feature. the foldr/build trick for deforesting lists is really really cool! look at ghc core, it is amazing how all your lists just disapear and are turned into clever function compositions I would have never thought of :) John -- John Meacham - ⑆repetae.net⑆john⑈