G'day all.
Quoting David Menendez <[hidden email]>: > Are there any instances of Boolean that aren't isomorphic to Bool? Sure. Two obvious examples: - The lattice of subsets of a "universe" set, where "or" is union "and" is intersection and "not" is complement with respect to the universe. - Many-valued logic systems. - Intuitionistic logic systems. - The "truth values" of an arbitrary topos (i.e. the points of the subobject classifier). Look up "Heyting algebra" for examples. Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
G'day all.
I wrote: > - Intuitionistic logic systems. > > - The "truth values" of an arbitrary topos (i.e. the points of the > subobject classifier). Sorry, I misread the question. These are _not_ instances of Boolean (or at least the latter isn't an instance in general). Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Cale Gibbard
On Thu, 2009-01-15 at 18:10 -0500, Cale Gibbard wrote:
> My personal preference would be: > > class Monoid m where > zero :: m > (++) :: m -> m -> m > > (in the Prelude of course) > > - Cale I've tried doing this (and making more widespread use of typeclassed operations) by writing my own AltPrelude. Unfortunately there is still a lot of 'unrebindable' syntax (list comprehensions, 'error' forced to exist in Monad, if-then-else not using nearest Bool, etc) which makes this hard to achieve. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe signature.asc (204 bytes) Download Attachment |
In reply to this post by David Virebayre
david48 wrote:
> On the other hand, on page 320 there is a nice explanation of Monoid, > and on page 380, which isn't mentionned in the index, there might be > the first time one can understand why the writer monad works with > monoids instead of lists: to be able to use better suited data types > for appending. (I too usually use the monoid instance mainly for difference lists.) > All of this is still lacking the great why : why/how an abstraction so > generic can be useful. > I'm starting to believe that the only reason to make a datatype an > instance of Monoid is... why not ! since it's not hard to find an > associative operation and a neutral element. As Bertram Felgenhauer has already mentioned, a very powerful application of monoids are 2-3 finger trees Ralf Hinze and Ross Patterson. Finger trees: a simple general-purpose data structure. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html Basically, they allow you write to fast implementations for pretty much every abstract data type mentioned in Okasaki's book "Purely Functional Data Structures". For example, you can do sequences, priority queues, search trees and priority search queues. Moreover, any fancy and custom data structures like interval trees or something for stock trading are likely to be implementable in this framework as well. How can one tree be useful for so many different data structures? The answer: *monoids*! Namely, the finger tree works with elements that are related to a monoid, and all the different data structures mentioned above arise by different choices for this monoid. Let me explain this monoid magic, albeit not in this message which would become far too long, but at http://apfelmus.nfshost.com/monoid-fingertree.html Regards, apfelmus -- http://apfelmus.nfshost.com _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
A very nice writeup about the use of monoid with finger tree.
But please, use the names of the monoid operations that the rest of the Haskell libraries use. By using different names you are just confusing readers (even if you don't like the standard names). Also, you can replace Infinity by maxBound. -- Lennart On Tue, Jan 20, 2009 at 3:42 PM, Heinrich Apfelmus <[hidden email]> wrote: > david48 wrote: >> On the other hand, on page 320 there is a nice explanation of Monoid, >> and on page 380, which isn't mentionned in the index, there might be >> the first time one can understand why the writer monad works with >> monoids instead of lists: to be able to use better suited data types >> for appending. > > (I too usually use the monoid instance mainly for difference lists.) > >> All of this is still lacking the great why : why/how an abstraction so >> generic can be useful. >> I'm starting to believe that the only reason to make a datatype an >> instance of Monoid is... why not ! since it's not hard to find an >> associative operation and a neutral element. > > As Bertram Felgenhauer has already mentioned, a very powerful > application of monoids are 2-3 finger trees > > Ralf Hinze and Ross Patterson. > Finger trees: a simple general-purpose data structure. > http://www.soi.city.ac.uk/~ross/papers/FingerTree.html > > Basically, they allow you write to fast implementations for pretty much > every abstract data type mentioned in Okasaki's book "Purely Functional > Data Structures". For example, you can do sequences, priority queues, > search trees and priority search queues. Moreover, any fancy and custom > data structures like interval trees or something for stock trading are > likely to be implementable in this framework as well. > > How can one tree be useful for so many different data structures? The > answer: *monoids*! Namely, the finger tree works with elements that are > related to a monoid, and all the different data structures mentioned > above arise by different choices for this monoid. > > Let me explain this monoid magic, albeit not in this message which would > become far too long, but at > > http://apfelmus.nfshost.com/monoid-fingertree.html > > > Regards, > apfelmus > > -- > http://apfelmus.nfshost.com > > > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe > Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Heinrich Apfelmus
On Tue, Jan 20, 2009 at 3:42 PM, Heinrich Apfelmus
<[hidden email]> wrote: > Let me explain this monoid magic, albeit not in this message which would > become far too long, but at > > http://apfelmus.nfshost.com/monoid-fingertree.html > That is a very nice summary! I did my own investigation of fingertrees recently [1] and also came to the conclusion that the function names for Monoid really are the ugliest, impractical things for such a beautiful, simple concept. Ah, if only we could go back in time :-) [1]: http://www.dougalstanton.net/blog/index.php/2008/12/12/a-brief-look-at-fingertrees/ Cheers, D _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Lennart Augustsson
Lennart Augustsson wrote:
> A very nice writeup about the use of monoid with finger tree. Thanks :) > But please, use the names of the monoid operations that the rest of > the Haskell libraries use. > By using different names you are just confusing readers (even if you > don't like the standard names). True. Unfortunately, mappend is no option because it's way too long, I barely got away with writing out measure . There is ++ but it's already taken. Alternatively, I could opt for unicode âŠ• and at least match the paper. Thoughts? > Also, you can replace Infinity by maxBound. Good idea, thanks. Regards, apfelmus -- http://apfelmus.nfshost.com _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by John Goerzen-3
* John Goerzen <[hidden email]> [2009-01-15 10:15:36 -0600]:
> If you're learning Haskell, which communicates the idea more clearly: > > * Appendable > > or > > * Monoid > > I can immediately figure out what the first one means. I think that's deceptively misleading. Sure, list1 `mappend` list2 is concatenation, of which Appendable is suggestive; but what on earth does it mean to append a number to another number, or append a function to another function? By doing some research, you can find out the answer, but if you start off with a name that means nothing to you, I suspect you'll be less confused than if you start off with a name that seems like it makes sense, but actually doesn't. (Of course, the name of mappend itself doesn't exactly help...) > I guess the bottom line question is: who is Haskell for? Category > theorists, programmers, or both? I'd love it to be for both, but I've > got to admit that Brian has a point that it is trending to the first in > some areas. I don't really understand why Appendable is specifically a "programmer-friendly" name; it doesn't really have any existing meaning elsewhere in programming languages, for example. -- mithrandi, i Ainil en-Balandor, a faer Ambar _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe signature.asc (204 bytes) Download Attachment |
In reply to this post by Andrew Coppin
* Andrew Coppin <[hidden email]> [2009-01-16 22:20:35 +0000]:
> A problem I see a lot of [and other people have mentioned this] is that > a lot of documentation presents highly abstracted things, and gives *no > hint* of why on earth these might possibly be useful for something. I think this is definitely something that should be addressed by better documentation of some kind. Unfortunately, this is quite possibly the hardest kind of knowledge to put down into words: before you learn the concepts, you don't know them, so you can't write about them, but after you learn them, they seem so obvious that you don't know how to describe them. (At least, this is typically the problem I have; I can answer questions about something easily, maybe even walk someone through understanding it, but I can't draft a document that will describe things adequately to a newbie). This problem is worse in Haskell than other languages, simply because abstractions are used more frequently and pervasively in Haskell. In many other languages, these abstractions are perfectly applicable, but actually encoding them in the language is simply too unwieldy. Thus, while the abstraction may be present as a fuzzy concept at the back of the programmer's mind, or even as a "design pattern", the code people actually work with tends to be at a more concrete level, despite the more limited possibilities of code reuse at this level. This ties in with the complaint that Haskell variable / parameter names aren't descriptive enough. You frequently hear things like "why call it 'xs' instead of 'applicableItems'?"; often, the answer to this is simply that the value in question is something so general that you cannot describe it more specifically than "a list of something or other". Haskell code is being written at a higher level of abstraction than the newcomer is used to, and thus the highly abstract names are mistaken for vague or imprecise names. Now, it's all very well to explain the reasons behind this to the newcomer, but they're still left in a position where they can't find the tools they need to solve a particular problem. They're used to looking for the concrete tools they need to do some task or another, which aren't there; instead, there are all these abstract tools which can perform the concrete task at hand, but what is really needed is help finding the abstract tool for the concrete task at hand, or even abstracting the concrete task at hand, thus making the choice of abstract tool(s) an obvious one. Sure, you can pop into #haskell and hopefully find someone to walk you through the processes until you begin to understand the abstractions yourself, but I think we (I almost hesitate to include myself, given my own relatively miniscule Haskell knowledge) can do better than this in terms of helping people unfamiliar with these concepts. Also, more importantly, I'm referring specifically to teaching *programmers* the concepts; I have no problem with *naming* things based on category theory or abstract algebra or quantum mechanics, but I should not be required to learn half a dozen fields of mathematics or physics in order to *use* things. Writing about how Monads in Haskell relate to Monads in category theory is of interest to category theorists, but isn't something programmers should be reading. Hopefully nothing I've said here comes as a surprise to anyone, and I'd be surprised if there were many serious objections to any of it, but perhaps it does need to be highlighted more prominently as an important area to improve if Haskell is to grow as a programming language. -- mithrandi, i Ainil en-Balandor, a faer Ambar _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe signature.asc (204 bytes) Download Attachment |
In reply to this post by John Goerzen-3
On Thu, 15 Jan 2009, John Goerzen wrote: > One thing that does annoy me about Haskell- naming. Say you've > noticed a common pattern, a lot of data structures are similar to > the difference list I described above, in that they have an empty > state and the ability to append things onto the end. Now, for > various reasons, you want to give this pattern a name using on > Haskell's tools for expressing common idioms as general patterns > (type classes, in this case). What name do you give it? I'd be > inclined to call it something like "Appendable". But no, Haskell > calls this pattern a "Monoid". I risk to repeat someones point, since I have not read the entire thread ... What I don't like about the Monoid class is, that its members are named "mempty" and "mappend". It may be either (also respecting qualified import) Monoid(identity, op) or Appendable(empty, append) where only the first one seems reasonable, since the Sum monoid and its friends do not append anything. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by John Goerzen-3
John Goerzen schrieb:
> Though if all we're talking about is naming, I would still maintain that > newbie-friendly naming is a win. We can always say "HEY MATHEMETICIANS: > APPENDABLE MEANS MONOID" in the haddock docs ;-) We already have a problem with this: Haskell 98 uses intuitive names for the numeric type classes. It introduces new names, which do not match the names of common algebraic structures. Why is a type Num (numeric?), whenever it supports number literals, (+) and (*)? Why not just number literals? Why not also division? The numeric type hierarchy of Haskell must be learned anyway, but the user learns terms he cannot use outside the Haskell world. Ring and Field are harder to learn first, but known and precise terms. (And if you don't like to learn the names, just write functions without signatures and let GHCi find out the signatures with the appropriate class constraints.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Henning Thielemann
On Tue, 2009-01-20 at 23:41 +0100, Henning Thielemann wrote:
> On Thu, 15 Jan 2009, John Goerzen wrote: > > > One thing that does annoy me about Haskell- naming. Say you've > > noticed a common pattern, a lot of data structures are similar to > > the difference list I described above, in that they have an empty > > state and the ability to append things onto the end. Now, for > > various reasons, you want to give this pattern a name using on > > Haskell's tools for expressing common idioms as general patterns > > (type classes, in this case). What name do you give it? I'd be > > inclined to call it something like "Appendable". But no, Haskell > > calls this pattern a "Monoid". > > I risk to repeat someones point, since I have not read the entire thread > ... What I don't like about the Monoid class is, that its members are > named "mempty" and "mappend". It may be either (also respecting > qualified import) > Monoid(identity, op) +1 If we're going to change any names in the standard library at all, this is the change we should make. jcc _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Heinrich Apfelmus
Apfelmus, Heinrich schrieb:
> Obviously, those who know what a monoid is have already invested years > of time practicing mathematics while those that even attack the name > "monoid" clearly lack this practice. It's like peano virtuosoes compared > to beginning keyboard pressers. Aren't all Haskellers some kind of Peano virtuosos? :-) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by roconnor
[hidden email] schrieb:
> On Sun, 18 Jan 2009, Ross Paterson wrote: > >> Anyone can check out the darcs repos for the libraries, and post >> suggested improvements to the documentation to [hidden email] >> (though you have to subscribe). It doesn't even have to be a patch. >> >> Sure, it could be smoother, but there's hardly a flood of contributions. > > I noticed the Bool datatype isn't well documented. Since Bool is not a > common English word, I figured it could use some haddock to help clarify > it for newcomers. The type should be named "Truth". _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Andrew Coppin
On 20 Jan 2009, at 8:33 am, Andrew Coppin wrote: > [hidden email] wrote: >> I noticed the Bool datatype isn't well documented. Since Bool is >> not a common English word, I figured it could use some haddock to >> help clarify it for newcomers. > > My only problem with it is that it's called Bool, while every other > programming language on Earth calls it Boolean. > (Or at least, the languages that *have* a name for it...) Algol 68, C99, C++, C#, Standard ML, OCAML, F#, Clean all use 'bool', not 'Boolean'. Of course if you want to go for historical priority, that'd be Fortran's LOGICAL type... _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Duncan Coutts
Hello,
Just some minor suggestions and comments: The description might read better as two sentences: A class for monoids with various general-purpose instances. Monoids are types with an associative binary operation that has an identity. One thing that I think is a bit unclear from that description is the fact that it does not matter *what* the binary operation does, as long as the laws are followed. That is the whole point of the monoid class -- you use it when you only care about the laws, not the specific operation... For the laws, it would be nice to label each rule, something like * mappend mempty x = x -- Left Identity * mappend x empty = x -- Right Identity * mappend x (mappend y z) = mappend (mappend x y) z -- Associative * mconcat = foldr mappend mempty -- Not sure what to call this. Perhaps it an axiom? See the Applicative class for a formatting example: http://www.haskell.org/ghc/dist/current/docs/libraries/base/Control-Applicative.html As an expert, seeing the name is faster than reverse engineering the meaning of each law. I also suspect many people have never heard of the concept of an identity element (I am pretty sure I hadn't when I first started Haskell). So, I think it would be nice to tie together the concepts mentioned in the description with the actual laws so that the link is explicit. j. At Sun, 18 Jan 2009 13:57:07 +0000, Duncan Coutts wrote: > > On Sat, 2009-01-17 at 13:36 -0800, David Leimbach wrote: > > > > > > On Sat, Jan 17, 2009 at 9:16 AM, david48 <[hidden email]> > > wrote: > > On Sat, Jan 17, 2009 at 4:08 PM, David Leimbach > > <[hidden email]> wrote: > > > > > So you're saying it should be better documented in Haskell > > what a Monoid is. > > > Did you say you searched for "C++ class" why not "Haskell > > Monoid" then? > > > The first correct google hit that didn't think I meant > > Monads, takes you > > > straight to the GHC documentation for Data.Monoid. > > > > Read my first post on the thread, that's exactly what I did > > ( and then > > complained that the doc for Data.Monoid was close to useless ) > > > > > > Sorry missed it! This is an exceptionally long thread! :-) I agree > > Data.Monoid's docs don't give you much to work with. > > Do you think they look better now: > > http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Monoid.html > > Any other improvements you'd make? > > Duncan > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Thu, 2009-01-22 at 11:32 -0600, Jeremy Shaw wrote:
> Hello, > > Just some minor suggestions and comments: > > The description might read better as two sentences: > > A class for monoids with various general-purpose instances. Monoids > are types with an associative binary operation that has an > identity. > > One thing that I think is a bit unclear from that description is the > fact that it does not matter *what* the binary operation does, as long > as the laws are followed. That is the whole point of the monoid class > -- you use it when you only care about the laws, not the specific > operation... > > For the laws, it would be nice to label each rule, something like > > * mappend mempty x = x -- Left Identity > * mappend x empty = x -- Right Identity > * mappend x (mappend y z) = mappend (mappend x y) z -- Associative > * mconcat = foldr mappend mempty -- Not sure what to call this. Perhaps it an axiom? This is just a definition, both actually and nominally. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |