Comments from OCaml Hacker Brian Hurt

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
237 messages Options
1 ... 9101112
Reply | Threaded
Open this post in threaded view
|

Re: Re: Improved documentation for Bool

ajb@spamcop.net
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Improved documentation for Bool

ajb@spamcop.net
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
Reply | Threaded
Open this post in threaded view
|

Re: Comments from OCaml Hacker Brian Hurt

George Pollard
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
Reply | Threaded
Open this post in threaded view
|

Re: Comments from OCaml Hacker Brian Hurt

Heinrich Apfelmus
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Comments from OCaml Hacker Brian Hurt

Lennart Augustsson
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Comments from OCaml Hacker Brian Hurt

Dougal Stanton
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
Reply | Threaded
Open this post in threaded view
|

Re: Comments from OCaml Hacker Brian Hurt

Heinrich Apfelmus
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
Reply | Threaded
Open this post in threaded view
|

Re: Comments from OCaml Hacker Brian Hurt

Tristan Seligmann-3
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
Reply | Threaded
Open this post in threaded view
|

Re: Comments from OCaml Hacker Brian Hurt

Tristan Seligmann-3
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
Reply | Threaded
Open this post in threaded view
|

Re: Comments from OCaml Hacker Brian Hurt

Henning Thielemann
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
Reply | Threaded
Open this post in threaded view
|

Re: Comments from OCaml Hacker Brian Hurt

Henning Thielemann-4
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
Reply | Threaded
Open this post in threaded view
|

Re: Comments from OCaml Hacker Brian Hurt

Bugzilla from jonathanccast@fastmail.fm
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Comments from OCaml Hacker Brian Hurt

Henning Thielemann-4
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
Reply | Threaded
Open this post in threaded view
|

Re: Improved documentation for Bool (Was: Comments from OCaml Hacker Brian Hurt)

Henning Thielemann-4
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Improved documentation for Bool

Richard A. O'Keefe
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
Reply | Threaded
Open this post in threaded view
|

Re: Re[2]: Comments from OCaml Hacker Brian Hurt

Jeremy Shaw-3
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
Reply | Threaded
Open this post in threaded view
|

Re: Re[2]: Comments from OCaml Hacker Brian Hurt

Derek Elkins
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
1 ... 9101112