José Pedro Magalhães | 1 Aug 08:36 2008
Picon

Re: [Hs-Generics] Re: Owning SYB

Hello all,

As Johan mentioned, here in Utrecht we are working on libraries for generic programming. We want to make it easier for people to use generic libraries, so we are packaging EMGM [1] and a library for generic programming for mutually recursive datatypes [2]. We intend to release these on Hackage soon (Summer vacations are delaying us a bit), along with useful generic applications (a zipper and a generic rewriting framework).

Maintaining SYB fits well in this idea, and if no other natural maintainers volunteer, I (with some support from the other people at Utrecht) am happy to take it upon me. I probably won't do heavy development on the library, but including patches, and providing support is fine. We're also planning to maintain EMGM here in Utrecht, although we didn't develop that ourselves.

Recently, (at least) Claus and Oleg have been posting interesting suggestions of improvements/modifications to SYB. Those should be further analyzed and discussed, and finally introduced (or not) in the library. The generic map for SYB, for instance, evolved from the "impossible to implement", through the "unsafe implementation", until the latest gmap2 as described by Oleg [3]. If further tests show this function behaves as expected, then it's clearly a good candidate for extending SYB. We should also rethink if other things previously deemed impossible remain so.

Maintaining SYB, alongside with the other generic libraries, will require things such as:
 * Releasing packages in Hackage, properly documented with Haddock;
 * Updating such packages as necessary for new releases of GHC;
 * Writing examples of how to use the libraries (from a user perspective);
 * Writing testsuites, which are important for checking backwards compatibility of any changes;
 * Having an updated webpage linking to the library sources, documentation, possibly a bug tracker, etc.
These are all things we plan to do for the libraries.

Additionally, we could think of improving syb-with-class [4] in parallel with regular SYB. This is something to ask to its maintainer.


Cheers,
Pedro

[1] http://books.google.com/books?id=OyY3ioMJRAsC&pg=PA199&sig=ACfU3U1nczeRAIjN9mc_vYnL1LnYAs70NA
[2] http://www.cs.uu.nl/research/techreps/UU-CS-2008-019.html
[3] http://www.haskell.org/pipermail/generics/2008-July/000362.html
[4] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/syb-with-class
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Aaron Denney | 1 Aug 11:00 2008
X-Face
Picon

Re: Unordered map

On 2008-07-29, Andrew Wagner <wagner.andrew <at> gmail.com> wrote:
> Well, it wouldn't need to literally implement Ord. It would just need
> to do the same operations as Data.Map does, except without the
> efficiency you get from Data.Map because you can assume an Ord
> instance. One way to do it is to simply internally store the data as
> an ordered [(a,k)], for example. Not efficient, but you get the same
> interface as Map.

Yes, but then you need to check tha you have the right one, which means
you need the context "Eq a".  If you're going to make users write an
equality function, making them write an ordering adds little effort, and
a reasonable amount of gain.  Usually.

--

-- 
Aaron Denney
-><-
Johannes Waldmann | 1 Aug 12:18 2008
Picon

Re: Unordered map


Aaron Denney wrote:

> If you're going to make users write an
> equality function, making them write an ordering adds little effort, and
> a reasonable amount of gain.  Usually.

Then why is there a distinction between e.g.
Map and SortedMap (and Set and SortedSet) in the Java libraries?

Yes yes I know Haskell is not Java etc. but they must have given
this some thought. (Of course them making everything an instance of
Eq and Hash is a design error but that's not the point here.)

The practical problem with Haskell's type class mechanism
is that all instances (of Eq, Ord) are global,
so if one library (Data.Map) requires them,
then you're stuck with these instances for all of your program.
Of course the same thing holds for Java's "implements Comparable<>"
but they have local types. Well, Haskell has newtype,
but that's (module-)global.

Best regards, J.W.

Aaron Denney | 1 Aug 13:13 2008
X-Face
Picon

Re: Unordered map

On 2008-08-01, Johannes Waldmann <waldmann <at> imn.htwk-leipzig.de> wrote:
> Aaron Denney wrote:
>
>> If you're going to make users write an
>> equality function, making them write an ordering adds little effort, and
>> a reasonable amount of gain.  Usually.
>
> Then why is there a distinction between e.g.
> Map and SortedMap (and Set and SortedSet) in the Java libraries?
>
> Yes yes I know Haskell is not Java etc. but they must have given
> this some thought. (Of course them making everything an instance of
> Eq and Hash is a design error but that's not the point here.)

You would have to ask the Java designers.

> The practical problem with Haskell's type class mechanism
> is that all instances (of Eq, Ord) are global,

This is a feature, not a bug.  It helps ensure that manipulations
on maps will always use compatible functions.  If, instead,
you constructed maps by passing in a comparison function, what
happens when you merge two maps?  Which function gets used?  Normally
you would be able to re-use the structure of each map in combining them.
But if the functions they used are different, than they have to be
resorted according to the kept function.  Or, you have an obscure,
difficult to track down bug, rather than an error at compile time.

> so if one library (Data.Map) requires them,
> then you're stuck with these instances for all of your program.
> Of course the same thing holds for Java's "implements Comparable<>"
> but they have local types. Well, Haskell has newtype,
> but that's (module-)global.

They don't have local types.  They have inner classes, and objects get
passed.

Newtypes do work.  The newtype deriving extension works even better.
If something has multiple ways of comparing, then the context in which
they are used should be tagged differently.  Haskell types are cheap,
both in the compiler, and when typing, because it's nowhere near as
verbose as Java.

--

-- 
Aaron Denney
-><-
Johannes Waldmann | 1 Aug 13:26 2008
Picon

Re: Unordered map


> They [Java] don't have local types.  
> They have inner classes, and objects get passed.

The net effect is that I can make an inner class
that implements some interface, and in the implementation
I can refer to things defined in some enclosing scope
(not just in the global scope). Sure, I can only refer
to static things, but in Haskell everything is static, no?

> Newtypes do work. 

I agree, to some extent. Using a newtype to simulate the above
is like lambda-lifting: you have to add the information on the local
things you want to use. The Java compiler does that for you.

Best regards, J.W.
Jan-Willem Maessen | 1 Aug 14:19 2008
Picon

Re: Unordered map


On Aug 1, 2008, at 6:18 AM, Johannes Waldmann wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Aaron Denney wrote:
>
>> If you're going to make users write an
>> equality function, making them write an ordering adds little  
>> effort, and
>> a reasonable amount of gain.  Usually.
>
> Then why is there a distinction between e.g.
> Map and SortedMap (and Set and SortedSet) in the Java libraries?
>
> Yes yes I know Haskell is not Java etc. but they must have given
> this some thought. (Of course them making everything an instance of
> Eq and Hash is a design error but that's not the point here.)

Au contraire, it's *exactly* the point!  Java uses the hash code to  
implement collections that only require equality and hashing, but no  
ordering.  Haskell, as a functional language, instead prefers equality  
and ordering---because trees admit efficient pure update, whereas hash  
tables generally do not.  Two different languages, two different  
approaches to implementing collections---one more imperative, the  
other more functional.

Of course, if one is simply looking for INefficient collections that  
require only (Eq a), this probably doesn't matter.  But in that case  
it's hard to do much better than [(a,b)] and lookup (it's possible to  
do better, using e.g. unboxed tuple arrays and seekrit mutation, but  
probably only worth it for stuff that's big enough that we should have  
been using a proper map anyway).

-Jan-Willem Maessen
Claus Reinke | 1 Aug 16:02 2008

Re: [Hs-Generics] Re: Owning SYB

Hi Pedro,

and thanks for volunteering! I include a summary of where I'm at, for
your information (and that of other interested readers;-)

> Recently, (at least) Claus and Oleg have been posting interesting
> suggestions of improvements/modifications to SYB. Those should be further
> analyzed and discussed, and finally introduced (or not) in the library. The
> generic map for SYB, for instance, evolved from the "impossible to
> implement", through the "unsafe implementation", until the latest gmap2 as
> described by Oleg [3]. If further tests show this function behaves as
> expected, then it's clearly a good candidate for extending SYB. We should
> also rethink if other things previously deemed impossible remain so.

Further discussion welcome, of course!-) And it isn't just about getting
fmap/traverse/.. from Data/Typeable, but also about reorganizing imports
of Data instances, and providing alternatives of everywhere/everything
that avoid traversals of irrelevant subterms.

A current snapshot of my code can be found here:

http://www.cs.kent.ac.uk/~cr3/tmp/syb/syb-utils-0.0.2008.7.31.tar.gz

It currently contains:

a) a suggested split for the Instances module, with alternatives to 
    Data.Generics that either export only Standard instances, or no
    instances at all. 

    On top of the existing Syb in base, these are somewhat tricky to use,
    because of the implicit re-exports of Data.Generics.Instances from 
    other libraries

    http://www.haskell.org/pipermail/generics/2008-July/000371.html

    and the long-standing GHC "session accumulates instances" bug

    http://hackage.haskell.org/trac/ghc/ticket/2182
    http://www.haskell.org/ghc/docs/latest/html/users_guide/bugs.html#bugs-ghc

    relevant modules:
            Data.Generics.Alt,
            Data.Generics.NoInstances,
            Data.Generics.Instances.Standard,
            Data.Generics.Instances.Dubious,
            examples\Examples.hs

    status: 
        I think this change should go into base (perhaps renaming
        Data.Generics.Alt to Data.Generics.Standard, and deprecating
        Data.Generics and Data.Generics.Instances), for all the reasons
        discussed here recently, and because that GHC bug makes it near
        impossible to provide this change as an addon to base. Existing 
        importers of Data.Generics or Data.Generics.Instances in core
        and extralibs should be redirected to one of the new modules.

b) variants of everywhere/everything/mkQ/.. that retain the type domain
    of generically extended queries, build substructure type maps of types
    to be traversed, and use a slight generalisation of the Uniplate PlateData
    trick to avoid traversals of irrelevant substructures (usually but not always
    including, and not limited to, Strings)

    relevant modules:
            Data.Generics.GPS,
            examples\GPSbenchmark.hs,
            examples\CompanyDatatypes.hs

    status:
        This could be provided as an addon package. Performance
        of generic queries and transformation on the usual Paradise
        benchmark improve as expected; there is some overhead,
        which is visible in an alternative benchmark where there are no irrelevant substructures.

        The current code also tries to replace the linear search for
        applicable specific-type-queries with Map lookup, but here
        the overhead seems to outweigh the benefits, so I'll probably
        disable this code in future.

        One issue that I still need to address are nested types: just
        as Data.Generics.PlateData, Data.Generics.GPS currently
        fails for these (no finite representation of substructure types);
        current plan is to recognize nested types and to fall back to
        unoptimized traversals.        

c) generic default instance methods for Control.Monad.Functor
    and Data.Traversable

    relevant modules:
            Data.Generics.Utils,
            examples\Examples.hs

    status:
            under discusssion. could become part of that add-on package,
            or move into base.

d) some Data/Typeable instances and utilities for GHC Api

    relevant modules:
            GHC.Syb.Instances,
            GHC.Syb.Instances0,
            GHC.Syb.Utils

    status:
            needs more testing, will probably be rendered obsolete when
            GHC Api starts providing those instances itself.

> Maintaining SYB, alongside with the other generic libraries, will require
> things such as:
> * Releasing packages in Hackage, properly documented with Haddock;
> * Updating such packages as necessary for new releases of GHC;
> * Writing examples of how to use the libraries (from a user perspective);
> * Writing testsuites, which are important for checking backwards
> compatibility of any changes;
> * Having an updated webpage linking to the library sources, documentation,
> possibly a bug tracker, etc.
> These are all things we plan to do for the libraries.
> 
> Additionally, we could think of improving syb-with-class [4] in parallel
> with regular SYB. This is something to ask to its maintainer.
> 
> 
> Cheers,
> Pedro
> 
> [1]
> http://books.google.com/books?id=OyY3ioMJRAsC&pg=PA199&sig=ACfU3U1nczeRAIjN9mc_vYnL1LnYAs70NA
> [2] http://www.cs.uu.nl/research/techreps/UU-CS-2008-019.html
> [3] http://www.haskell.org/pipermail/generics/2008-July/000362.html
> [4]
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/syb-with-class
>

--------------------------------------------------------------------------------

> _______________________________________________
> Generics mailing list
> Generics <at> haskell.org
> http://www.haskell.org/mailman/listinfo/generics
>
Claus Reinke | 1 Aug 16:08 2008

Re: [Hs-Generics] Re: Owning SYB

oops, keybinding malfunction - that message went out unfinished.
Seems to have most parts, though, so I leave it at that.

One other thing I meant to ask was about procedure,
given that Syb is currently in base and hence under the
library modification process. How is this going to combine
with an active maintainer and some parts on hackage?

Claus

----- Original Message ----- 
From: "Claus Reinke" <claus.reinke <at> talk21.com>
To: "José Pedro Magalhães" <jpm <at> cs.uu.nl>; <generics <at> haskell.org>; <libraries <at> haskell.org>
Sent: Friday, August 01, 2008 3:02 PM
Subject: Re: [Hs-Generics] Re: Owning SYB

> Hi Pedro,
>
> and thanks for volunteering! I include a summary of where I'm at, for
> your information (and that of other interested readers;-)
>
>> Recently, (at least) Claus and Oleg have been posting interesting
>> suggestions of improvements/modifications to SYB. Those should be further
>> analyzed and discussed, and finally introduced (or not) in the library. The
>> generic map for SYB, for instance, evolved from the "impossible to
>> implement", through the "unsafe implementation", until the latest gmap2 as
>> described by Oleg [3]. If further tests show this function behaves as
>> expected, then it's clearly a good candidate for extending SYB. We should
>> also rethink if other things previously deemed impossible remain so.
>
> Further discussion welcome, of course!-) And it isn't just about getting
> fmap/traverse/.. from Data/Typeable, but also about reorganizing imports
> of Data instances, and providing alternatives of everywhere/everything
> that avoid traversals of irrelevant subterms.
>
> A current snapshot of my code can be found here:
>
> http://www.cs.kent.ac.uk/~cr3/tmp/syb/syb-utils-0.0.2008.7.31.tar.gz
>
> It currently contains:
>
> a) a suggested split for the Instances module, with alternatives to Data.Generics that either 
> export only Standard instances, or no
>    instances at all.
>    On top of the existing Syb in base, these are somewhat tricky to use,
>    because of the implicit re-exports of Data.Generics.Instances from other libraries
>
>    http://www.haskell.org/pipermail/generics/2008-July/000371.html
>
>    and the long-standing GHC "session accumulates instances" bug
>
>    http://hackage.haskell.org/trac/ghc/ticket/2182
>    http://www.haskell.org/ghc/docs/latest/html/users_guide/bugs.html#bugs-ghc
>
>    relevant modules:
>            Data.Generics.Alt,
>            Data.Generics.NoInstances,
>            Data.Generics.Instances.Standard,
>            Data.Generics.Instances.Dubious,
>            examples\Examples.hs
>    status: I think this change should go into base (perhaps renaming
>        Data.Generics.Alt to Data.Generics.Standard, and deprecating
>        Data.Generics and Data.Generics.Instances), for all the reasons
>        discussed here recently, and because that GHC bug makes it near
>        impossible to provide this change as an addon to base. Existing importers of Data.Generics 
> or Data.Generics.Instances in core
>        and extralibs should be redirected to one of the new modules.
>
> b) variants of everywhere/everything/mkQ/.. that retain the type domain
>    of generically extended queries, build substructure type maps of types
>    to be traversed, and use a slight generalisation of the Uniplate PlateData
>    trick to avoid traversals of irrelevant substructures (usually but not always
>    including, and not limited to, Strings)
>
>    relevant modules:
>            Data.Generics.GPS,
>            examples\GPSbenchmark.hs,
>            examples\CompanyDatatypes.hs
>
>    status:
>        This could be provided as an addon package. Performance
>        of generic queries and transformation on the usual Paradise
>        benchmark improve as expected; there is some overhead,
>        which is visible in an alternative benchmark where there are no irrelevant substructures.
>
>        The current code also tries to replace the linear search for
>        applicable specific-type-queries with Map lookup, but here
>        the overhead seems to outweigh the benefits, so I'll probably
>        disable this code in future.
>
>        One issue that I still need to address are nested types: just
>        as Data.Generics.PlateData, Data.Generics.GPS currently
>        fails for these (no finite representation of substructure types);
>        current plan is to recognize nested types and to fall back to
>        unoptimized traversals.
> c) generic default instance methods for Control.Monad.Functor
>    and Data.Traversable
>
>    relevant modules:
>            Data.Generics.Utils,
>            examples\Examples.hs
>
>    status:
>            under discusssion. could become part of that add-on package,
>            or move into base.
>
> d) some Data/Typeable instances and utilities for GHC Api
>
>    relevant modules:
>            GHC.Syb.Instances,
>            GHC.Syb.Instances0,
>            GHC.Syb.Utils
>
>    status:
>            needs more testing, will probably be rendered obsolete when
>            GHC Api starts providing those instances itself.
>
>> Maintaining SYB, alongside with the other generic libraries, will require
>> things such as:
>> * Releasing packages in Hackage, properly documented with Haddock;
>> * Updating such packages as necessary for new releases of GHC;
>> * Writing examples of how to use the libraries (from a user perspective);
>> * Writing testsuites, which are important for checking backwards
>> compatibility of any changes;
>> * Having an updated webpage linking to the library sources, documentation,
>> possibly a bug tracker, etc.
>> These are all things we plan to do for the libraries.
>>
>> Additionally, we could think of improving syb-with-class [4] in parallel
>> with regular SYB. This is something to ask to its maintainer.
>>
>>
>> Cheers,
>> Pedro
>>
>> [1]
>> http://books.google.com/books?id=OyY3ioMJRAsC&pg=PA199&sig=ACfU3U1nczeRAIjN9mc_vYnL1LnYAs70NA
>> [2] http://www.cs.uu.nl/research/techreps/UU-CS-2008-019.html
>> [3] http://www.haskell.org/pipermail/generics/2008-July/000362.html
>> [4]
>> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/syb-with-class
>>
>
>
> --------------------------------------------------------------------------------
>
>
>> _______________________________________________
>> Generics mailing list
>> Generics <at> haskell.org
>> http://www.haskell.org/mailman/listinfo/generics
>>
> _______________________________________________
> Generics mailing list
> Generics <at> haskell.org
> http://www.haskell.org/mailman/listinfo/generics 
Alfonso Acosta | 1 Aug 16:13 2008
Picon

runCommand/waitForProcess don't respect text printing order when stdout is redirected

Hi all,

I'm running ghc 6.8.2 in OSX and Linux.

The following program behaves as expected when run on a terminal.

==
module Main where

import System.Process

main = sequence $ replicate 3 command
 where command = do putStrLn "foo"
                    waitForProcess =<< runCommand "echo echo"
                    putStrLn "bar"
==

$ ghc --make Main.hs -o main
$./main
foo
echo
bar
foo
echo
bar
foo
echo
bar

However, when stdout is redirected to a file, the order is no longer respected:

$ ./main > output
$ cat output
echo
echo
echo
foo
bar
foo
bar
foo
bar

Am I missing something or should I file a bug report?

Thanks in advance,

Fons
ross | 1 Aug 16:16 2008
Picon

Re: proposal #2461: add Traversable generalizations?of?mapAccumL?and mapAccumR

Quoting Nicolas Pouillard <nicolas.pouillard <at> gmail.com>:
> I've also understood "<**≥ = flip <*>" when reading the docs :(

Clearly the docs need improving.  Does anyone have any comments on the
proposal itself?

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.

Gmane