Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread MightyByte
Interesting data point.  I think my initial thoughts can be summarized with
the suggestion that this thread would be better served by a little irony
and a new subject: Reuse Considered Harmful.

On Thu, Aug 30, 2012 at 1:26 AM, Bryan O'Sullivan b...@serpentine.comwrote:

 Since the release of the GHC 7.6 RC, I've been going through my packages
 and fixing up build problems so that people who upgrade to 7.6 will have a
 smooth ride.

 Sad to say, my experience of 7.6 is that it has felt like a particularly
 rough release for backwards incompatibility. I wanted to quantify the pain,
 so I did some research, and here's what I found.

 I maintain 25 open source Haskell packages. Of these, the majority have
 needed updates due to the GHC 7.6 release:

- base16-bytestring
- blaze-textual
- bloomfilter
- configurator
- criterion
- double-conversion
- filemanip
- HDBC-mysql
- mwc-random
- pcap
- pool
- riak-haskell-client
- snappy
- text
- text-format
- text-icu

 That's 16 out of 25 packages I've had to update. I've also either reported
 bugs on, or had to fix, several other people's packages along the way
 (maybe four?). So let's say I've run into problems with 20 out of the
 combined 29 packages of mine and my upstreams.

 The reasons for these problems fall into three bins:

- Prelude no longer exports catch, so a lot of import Prelude hiding
(catch) had to change.
- The FFI now requires constructors to be visible, so CInt has to be
imported as CInt(..).
- bytestring finally got bumped to 0.10, so many upper bounds had to
be relaxed (*cf* my suggestion that the upper-bounds-by-default policy
is destructive).

 It has been a lot of work to test 29 packages, and then modify, rebuild,
 and release 20 of them. It has consumed most of my limited free time for
 almost two weeks. Worse, this has felt like make-work, of no practical
 benefit to anyone beyond scrambling to restore the status quo ante.

 If over half of my packages needed fixing, I'm alarmed at the thought of
 the effects on the rest of Hackage.

 I'm torn over this. I understand and agree with the impetus to improve the
 platform by tidying things up, and yet just two seemingly innocuous changes
 (catch and FFI) have forced me to do a bunch of running to stand still.

 I don't have any suggestions about what to do; I know that it's hard to
 estimate the downstream effects of what look like small changes. And so I'm
 not exactly complaining. Call this an unhappy data point.

 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


[Haskell-cafe] Darcs fetches too little files

2012-08-30 Thread Ramana Kumar
On Aug 29, 2012 10:56 PM, Henk-Jan van Tuyl hjgt...@chello.nl wrote:

 On Wed, 29 Aug 2012 23:10:24 +0200, Stefan Monnier 
monn...@iro.umontreal.ca wrote:

 Albert Einstein said:
   Insanity: doing the same thing over and over again and expecting
 different results.
 I repeated the command today and it worked!


 So, did you expect the result to be different, or did you re-try just to
 confirm that it doesn't work?


 The day after I tried the command the first time, I thought the result
might be different; I have the experience that my browser crashes, and
starting it again results in an immediate crash. Logging off and on again
solves the problem. This might be because of a corrupted DLL or a corrupted
data area of a DLL.

 The command failure could have also been caused by a problem at the
server side.

 In conclusion: repeating the same thing could give different results.

This depends on what counts as the same. (There is a nice book called
The Subtlety of Sameness.) I'm surprised that as users of a language that
makes a big deal out of referential transparency none of you have said that
neither invoking the same command at a different time nor invoking a
browser after changing context (logging in again) is doing the same thing.



 Regards,
 Henk-Jan van Tuyl


 --
 http://Van.Tuyl.eu/
 http://members.chello.nl/hjgtuyl/tourdemonad.html
 Haskell programming
 --

 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Ivan Lazar Miljenovic
On 30 August 2012 15:26, Bryan O'Sullivan b...@serpentine.com wrote:
 The reasons for these problems fall into three bins:

 Prelude no longer exports catch, so a lot of import Prelude hiding (catch)
 had to change.

It looks like this might be fixed before the release:
http://hackage.haskell.org/trac/ghc/ticket/7167

-- 
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
http://IvanMiljenovic.wordpress.com

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Richard O'Keefe

On 30/08/2012, at 5:26 PM, Bryan O'Sullivan wrote:
 The reasons for these problems fall into three bins:
   • Prelude no longer exports catch, so a lot of import Prelude hiding 
 (catch) had to change.

This could have been avoided if

import module hiding (importables)

were interpreted simply as a requiring that the specified importables
not be imported *whether they could have been or not* rather than as
requiring that they exist to be sneered at.  It seems rather odd that
the removable of something that a module insists it doesn't want should
break that module.



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma

2012-08-30 Thread Joachim Breitner
Hi,

Am Mittwoch, den 29.08.2012, 17:16 +0100 schrieb Thomas Schilling:
 Syntactically, I'd prefer something that looks more like a function.
  With a pragma it's difficult to see what expression it actually
 affects.  For example, we already have the special functions lazy
 and inline. Since avoiding updates essentially turns lazy evaluation
 into call-by-name you could call it cbn. Perhaps that suggests a
 different use case, though, so nonstrict, unshared, or nonlazy
 might be more self-explanatory.

thanks for the feedback. I only made it a pragma because it seemed to be
simpler at first, but now the branch also supports GHC.Prim.noupdate
(better name to be found before it reaches any official GHC branch, if
that ever happens).

 I'd also like to point out that avoiding updates can dramatically
 improve the kind of speedups my tracing JIT can achieve. In
 particular, on some benchmarks, it can optimise idiomatic Haskell code
 to the same level as stream fusion. I can simulate that by avoiding
 *all* updates (i.e., use call-by-name), but that would break some
 programs badly. (Technically, that's all legal, but I'm pretty sure it
 breaks any tying-the-knot tricks.)

If you can make use of my code in Lambdachine I’d be very happy to help
fixing bus and to hear about your results (but from a first glance it
seems that you are not using that part of GHC in your project, right?).

Greetings,
Joachim

-- 
Dipl.-Math. Dipl.-Inform. Joachim Breitner
Wissenschaftlicher Mitarbeiter
http://pp.info.uni-karlsruhe.de/~breitner


signature.asc
Description: This is a digitally signed message part
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Erik Hesselink
On Thu, Aug 30, 2012 at 7:26 AM, Bryan O'Sullivan b...@serpentine.com wrote:
 The FFI now requires constructors to be visible, so CInt has to be
 imported as CInt(..).

I think there was already a warning about this one in GHC 7.4, so
there was more time to fix it. Not to say I don't feel your pain, but
if deprecating/warning and then removing in the next release isn't
good enough, nothing can ever be changed.

Erik

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Alexander Kjeldaas
This is very unfortunate, but this is crucially a tooling issue.  I am
going to wave my hands, but..

Ignore the mapreduce in the following video, but look at the use of clang
to do automatic refactoring of C++.  This is *incredibly* powerful in
dealing with updates to APIs.

http://www.llvm.org/devmtg/2011-11/videos/Carruth_ClangMapReduce-desktop.mp4

But without all that fancy tech, *just* having all of Hackage source code
in one repository and using perl/regexps, fixing these types of issues is
O(1) instead of O(n).

All of the issues you mention seems to be fixable by a few lines of perl
*if we had the repository*.

[a few hours later]

Actually, I went and downloaded all of hackage, put it into a git
repository and fixed these issues:

Fix catch
perl -ni -e 'print unless /import Prelude hiding \(catch\)/' $(git grep
'import Prelude hiding (catch)')

Fix CInt constructors (lots of other stuff from Foreign.C.Types not fixed
though)
perl -p -i -e 's/^import Foreign.C.Types(.*)CInt([^(])/import
Foreign.C.Types${1}CInt(..)${1}/g' $(git grep -l '^import.*CInt')

Fix bytestring versioning
perl -p -i -e 's/bytestring( +)=([0-9. ]+)([
]*)0.10/bytestring$1=$2${3}0.11/g' $(git grep 'bytestring.* *0\.')

Patch to hackage:
http://ge.tt/6Cb5ErM/v/0

I understand that this doesn't help anyone, but if there was a way fix,
upload, and get *consensus* on a few regexps like this, then doing API
changes wouldn't be such a headache.

Alexander

On 30 August 2012 07:26, Bryan O'Sullivan b...@serpentine.com wrote:

 Since the release of the GHC 7.6 RC, I've been going through my packages
 and fixing up build problems so that people who upgrade to 7.6 will have a
 smooth ride.

 Sad to say, my experience of 7.6 is that it has felt like a particularly
 rough release for backwards incompatibility. I wanted to quantify the pain,
 so I did some research, and here's what I found.

 I maintain 25 open source Haskell packages. Of these, the majority have
 needed updates due to the GHC 7.6 release:

- base16-bytestring
- blaze-textual
- bloomfilter
- configurator
- criterion
- double-conversion
- filemanip
- HDBC-mysql
- mwc-random
- pcap
- pool
- riak-haskell-client
- snappy
- text
- text-format
- text-icu

 That's 16 out of 25 packages I've had to update. I've also either reported
 bugs on, or had to fix, several other people's packages along the way
 (maybe four?). So let's say I've run into problems with 20 out of the
 combined 29 packages of mine and my upstreams.

 The reasons for these problems fall into three bins:

- Prelude no longer exports catch, so a lot of import Prelude hiding
(catch) had to change.
- The FFI now requires constructors to be visible, so CInt has to be
imported as CInt(..).
- bytestring finally got bumped to 0.10, so many upper bounds had to
be relaxed (*cf* my suggestion that the upper-bounds-by-default policy
is destructive).

 It has been a lot of work to test 29 packages, and then modify, rebuild,
 and release 20 of them. It has consumed most of my limited free time for
 almost two weeks. Worse, this has felt like make-work, of no practical
 benefit to anyone beyond scrambling to restore the status quo ante.

 If over half of my packages needed fixing, I'm alarmed at the thought of
 the effects on the rest of Hackage.

 I'm torn over this. I understand and agree with the impetus to improve the
 platform by tidying things up, and yet just two seemingly innocuous changes
 (catch and FFI) have forced me to do a bunch of running to stand still.

 I don't have any suggestions about what to do; I know that it's hard to
 estimate the downstream effects of what look like small changes. And so I'm
 not exactly complaining. Call this an unhappy data point.

 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Alexander Bernauer
Hi

I agree that automatic code migration can solve this issue in large
parts. The Python folks have done this to mitigate the transition from
version 2 to version 3 [1].

On Thu, Aug 30, 2012 at 03:03:05PM +0200, Alexander Kjeldaas wrote:
 perl -ni -e 'print unless /import Prelude hiding \(catch\)/' $(git grep
 'import Prelude hiding (catch)')
 
I don't think regular expressions are powerful enough. This example
does not match on hiding multiple names, for instance.

But writing proper 'HsModule - HsModule' functions should be doable.

And when each release comes with a bunch of such functions, packages
could be automatically migrated.

Greetings

Alex

[1] http://docs.python.org/library/2to3.html


signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Alexander Kjeldaas
On 30 August 2012 15:34, Alexander Bernauer alex-hask...@copton.net wrote:

 Hi

 I agree that automatic code migration can solve this issue in large
 parts. The Python folks have done this to mitigate the transition from
 version 2 to version 3 [1].

 On Thu, Aug 30, 2012 at 03:03:05PM +0200, Alexander Kjeldaas wrote:
  perl -ni -e 'print unless /import Prelude hiding \(catch\)/' $(git grep
  'import Prelude hiding (catch)')

 I don't think regular expressions are powerful enough. This example
 does not match on hiding multiple names, for instance.


This was just an example, the CInt regexp handles multiple names, so
regexps have no problems handling this.

And it's a simple git grep 'import.*Prelude.*catch' to see if this
actually is a problem or not.

My point is that this works, fixes 99% of the cases, and is 1000x less work
overall.

Alexander



 But writing proper 'HsModule - HsModule' functions should be doable.

 And when each release comes with a bunch of such functions, packages
 could be automatically migrated.

 Greetings

 Alex

 [1] http://docs.python.org/library/2to3.html

 -BEGIN PGP SIGNATURE-
 Version: GnuPG v1.4.10 (GNU/Linux)

 iEYEARECAAYFAlA/a/oACgkQevm6Dd/q44nJXQCffaxEJ/NZEftgoZ7viAWMuBO3
 +jkAnRTw+VCMQn1k9NibyKpkGMtwvrQw
 =ds3M
 -END PGP SIGNATURE-

 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Erik Hesselink
Note that this does not work if you want to support multiple versions
of GHC, and might not work in general, since

* The hiding of catch is needed for preludes that still have it, since
otherwise it will probably conflict with the one from
Control.Exception.
* Older versions do not have constructors for the FFI types, leading
to warnings (or errors, I'm not sure).
* Packages might not work with the new bytestring version, since the
API has breaking changes (although they're supposed to be minor).

For the first two, you need to add some CPP, for the last, you need
actual testing.

Erik

On Thu, Aug 30, 2012 at 3:03 PM, Alexander Kjeldaas
alexander.kjeld...@gmail.com wrote:
 This is very unfortunate, but this is crucially a tooling issue.  I am going
 to wave my hands, but..

 Ignore the mapreduce in the following video, but look at the use of clang to
 do automatic refactoring of C++.  This is *incredibly* powerful in dealing
 with updates to APIs.

 http://www.llvm.org/devmtg/2011-11/videos/Carruth_ClangMapReduce-desktop.mp4

 But without all that fancy tech, *just* having all of Hackage source code in
 one repository and using perl/regexps, fixing these types of issues is O(1)
 instead of O(n).

 All of the issues you mention seems to be fixable by a few lines of perl *if
 we had the repository*.

 [a few hours later]

 Actually, I went and downloaded all of hackage, put it into a git repository
 and fixed these issues:

 Fix catch
 perl -ni -e 'print unless /import Prelude hiding \(catch\)/' $(git grep
 'import Prelude hiding (catch)')

 Fix CInt constructors (lots of other stuff from Foreign.C.Types not fixed
 though)
 perl -p -i -e 's/^import Foreign.C.Types(.*)CInt([^(])/import
 Foreign.C.Types${1}CInt(..)${1}/g' $(git grep -l '^import.*CInt')

 Fix bytestring versioning
 perl -p -i -e 's/bytestring( +)=([0-9. ]+)([
 ]*)0.10/bytestring$1=$2${3}0.11/g' $(git grep 'bytestring.* *0\.')

 Patch to hackage:
 http://ge.tt/6Cb5ErM/v/0

 I understand that this doesn't help anyone, but if there was a way fix,
 upload, and get *consensus* on a few regexps like this, then doing API
 changes wouldn't be such a headache.

 Alexander

 On 30 August 2012 07:26, Bryan O'Sullivan b...@serpentine.com wrote:

 Since the release of the GHC 7.6 RC, I've been going through my packages
 and fixing up build problems so that people who upgrade to 7.6 will have a
 smooth ride.

 Sad to say, my experience of 7.6 is that it has felt like a particularly
 rough release for backwards incompatibility. I wanted to quantify the pain,
 so I did some research, and here's what I found.

 I maintain 25 open source Haskell packages. Of these, the majority have
 needed updates due to the GHC 7.6 release:

 base16-bytestring
 blaze-textual
 bloomfilter
 configurator
 criterion
 double-conversion
 filemanip
 HDBC-mysql
 mwc-random
 pcap
 pool
 riak-haskell-client
 snappy
 text
 text-format
 text-icu

 That's 16 out of 25 packages I've had to update. I've also either reported
 bugs on, or had to fix, several other people's packages along the way (maybe
 four?). So let's say I've run into problems with 20 out of the combined 29
 packages of mine and my upstreams.

 The reasons for these problems fall into three bins:

 Prelude no longer exports catch, so a lot of import Prelude hiding
 (catch) had to change.
 The FFI now requires constructors to be visible, so CInt has to be
 imported as CInt(..).
 bytestring finally got bumped to 0.10, so many upper bounds had to be
 relaxed (cf my suggestion that the upper-bounds-by-default policy is
 destructive).

 It has been a lot of work to test 29 packages, and then modify, rebuild,
 and release 20 of them. It has consumed most of my limited free time for
 almost two weeks. Worse, this has felt like make-work, of no practical
 benefit to anyone beyond scrambling to restore the status quo ante.

 If over half of my packages needed fixing, I'm alarmed at the thought of
 the effects on the rest of Hackage.

 I'm torn over this. I understand and agree with the impetus to improve the
 platform by tidying things up, and yet just two seemingly innocuous changes
 (catch and FFI) have forced me to do a bunch of running to stand still.

 I don't have any suggestions about what to do; I know that it's hard to
 estimate the downstream effects of what look like small changes. And so I'm
 not exactly complaining. Call this an unhappy data point.

 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe



 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] [Haskell] ANNOUNCE: Perdure

2012-08-30 Thread Felipe Almeida Lessa
[moving discussion to haskell-cafe]

Congratulations and thanks for your new open source contribution!  I
hope you feel at home =).

Your library looks really interesting but I'm completely overwhelmed
by its size.  Its Cabal description is huge and there's no example of
how to use the library (it actually took me some time to understand
what the library tries to accomplish).  I took a quick look at the
modules but there are so many that I couldn't really make sense of
anything in a short time.

So, could you perhaps write a full example of how to use the library?
It looks like a nice library but I need a starting point =).

Cheers!

-- 
Felipe.

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread wren ng thornton

On 8/30/12 10:26 AM, Erik Hesselink wrote:

Note that this does not work if you want to support multiple versions
of GHC, and might not work in general, since

* The hiding of catch is needed for preludes that still have it, since
otherwise it will probably conflict with the one from
Control.Exception.
* Older versions do not have constructors for the FFI types, leading
to warnings (or errors, I'm not sure).


In 6.12, they're warnings. And those warnings only show up with -Wall 
enabled. Though there does not appear to be an appropriate -fno-warn-foo 
to disable only these warnings while leaving the rest of -Wall intact. 
(If anyone knows of such a flag in 6.12, I'd be much obliged.)




* Packages might not work with the new bytestring version, since the
API has breaking changes (although they're supposed to be minor).

For the first two, you need to add some CPP, for the last, you need
actual testing.


Actually, that can be more problematic than you suspect. In particular, 
hsc2hs does not play nicely with Cabal's MIN_VERSION_foo(1,2,3) macros. 
So if you're using hsc2hs, which is common for certain FFI uses, then 
you have to put up with the warnings or rely on the __GLASGOW_HASKELL__ 
macro in lieu of the MIN_VERSION_foo(1,2,3) macros. It's doable, but 
it's uglier and more hackish than it ought to be.


--
Live well,
~wren

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


[Haskell-cafe] happstack simpleHTTP state monad

2012-08-30 Thread Corentin Dupont
Hi all,
I'm trying to make a web server that manages its own state. The user can
issue commands that modifies the state.
I did like below but unfortunatly the state is not keep after a command is
issued...
What is the right way to do it? Is there any example sites with an internal
state with happstack?

*data Game = (the state of my game)
type NomicServer = ServerPartT (StateT Game IO)

launchWebServer :: Game - IO ()
launchWebServer initialState = do
   putStrLn Starting web server...\nTo connect, drive your browser to \
http://localhost:8000/Login\;
   d - getDataDir
   simpleHTTP' unpackStateT nullConf $ server d


server :: FilePath - ServerPartT (StateT Game IO) Response
server d sh = mconcat [fileServe [] d, do
   decodeBody (defaultBodyPolicy /tmp/
4096 4096 4096)
   html - implSite http://localhost:8000/;
 nomicSite
   return $ toResponse html]

unpackStateT:: Game - UnWebT (StateT Game IO) Response - UnWebT IO
Response
unpackStateT g w = evalStateT w g

--handler for web routes
nomicSite :: Site PlayerCommand (NomicServer Html)
nomicSite = setDefault (Noop 0) Site {
  handleSite = \f url - unRouteT (routedNomicCommands url) f
, formatPathSegments = \u - (toPathSegments u, [])
, parsePathSegments  = parseSegments fromPathSegments
}*

Thanks a lot,
Corentin
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


[Haskell-cafe] paths in .cabal/config

2012-08-30 Thread Semen Trygubenko
Dear Haskell-Cafe,

I am wondering if there is a way to use variables in paths
that appear in .cabal/config file?

I have written a custom config file that I would like to
share. However, my config file contains full paths s.a.

world-file: /home/semen/.cabal/world

etc. Is there any way I could make it less personal, e.g.

world-file: /home/${HOME}/.cabal/world

Many thanks,
Sem

-- 
Семен Тригубенко


signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Michael Sloan
A good way to specify such refactorings is as a Haskell module.  For example:


module PreludePre_7_6 where

import Prelude hiding ( catch )


Or, an example of avoiding the Eq / Show / Num debacle:

module PreludePre_7_4 (module Prelude, Num) where

import Prelude hiding ( Num )
import qualified Prelude as P

instance template (Eq a, Show a) = Num a where
  instance P.Num a


(Uses my instance template proposal - though with different keywords -
https://github.com/mgsloan/instance-templates )


Let's say we wanted to rename catch to unsafeCatch

module PreludePreUnsafeCatch (module Prelude, catch) where

import Prelude hiding (unsafeCatch)

catch = unsafeCatch


Then, an automated refactoring system is simply a sourcecode-based
module inliner.  Quite a bit of effort, certainly, but it's much
better than coming up with a whole new notation for refactorings.

-Michael

On Thu, Aug 30, 2012 at 6:34 AM, Alexander Bernauer
alex-hask...@copton.net wrote:
 Hi

 I agree that automatic code migration can solve this issue in large
 parts. The Python folks have done this to mitigate the transition from
 version 2 to version 3 [1].

 On Thu, Aug 30, 2012 at 03:03:05PM +0200, Alexander Kjeldaas wrote:
 perl -ni -e 'print unless /import Prelude hiding \(catch\)/' $(git grep
 'import Prelude hiding (catch)')

 I don't think regular expressions are powerful enough. This example
 does not match on hiding multiple names, for instance.

 But writing proper 'HsModule - HsModule' functions should be doable.

 And when each release comes with a bunch of such functions, packages
 could be automatically migrated.

 Greetings

 Alex

 [1] http://docs.python.org/library/2to3.html

 -BEGIN PGP SIGNATURE-
 Version: GnuPG v1.4.10 (GNU/Linux)

 iEYEARECAAYFAlA/a/oACgkQevm6Dd/q44nJXQCffaxEJ/NZEftgoZ7viAWMuBO3
 +jkAnRTw+VCMQn1k9NibyKpkGMtwvrQw
 =ds3M
 -END PGP SIGNATURE-

 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Michael Sloan
Whoops, I messed up that first example:

module PreludePre_7_6 (module Prelude, catch) where

import Prelude
import qualified System.IO.Error as E

catch = E.catch

On Thu, Aug 30, 2012 at 12:16 PM, Michael Sloan mgsl...@gmail.com wrote:
 A good way to specify such refactorings is as a Haskell module.  For example:


 module PreludePre_7_6 where

 import Prelude hiding ( catch )


 Or, an example of avoiding the Eq / Show / Num debacle:

 module PreludePre_7_4 (module Prelude, Num) where

 import Prelude hiding ( Num )
 import qualified Prelude as P

 instance template (Eq a, Show a) = Num a where
   instance P.Num a


 (Uses my instance template proposal - though with different keywords -
 https://github.com/mgsloan/instance-templates )


 Let's say we wanted to rename catch to unsafeCatch

 module PreludePreUnsafeCatch (module Prelude, catch) where

 import Prelude hiding (unsafeCatch)

 catch = unsafeCatch


 Then, an automated refactoring system is simply a sourcecode-based
 module inliner.  Quite a bit of effort, certainly, but it's much
 better than coming up with a whole new notation for refactorings.

 -Michael

 On Thu, Aug 30, 2012 at 6:34 AM, Alexander Bernauer
 alex-hask...@copton.net wrote:
 Hi

 I agree that automatic code migration can solve this issue in large
 parts. The Python folks have done this to mitigate the transition from
 version 2 to version 3 [1].

 On Thu, Aug 30, 2012 at 03:03:05PM +0200, Alexander Kjeldaas wrote:
 perl -ni -e 'print unless /import Prelude hiding \(catch\)/' $(git grep
 'import Prelude hiding (catch)')

 I don't think regular expressions are powerful enough. This example
 does not match on hiding multiple names, for instance.

 But writing proper 'HsModule - HsModule' functions should be doable.

 And when each release comes with a bunch of such functions, packages
 could be automatically migrated.

 Greetings

 Alex

 [1] http://docs.python.org/library/2to3.html

 -BEGIN PGP SIGNATURE-
 Version: GnuPG v1.4.10 (GNU/Linux)

 iEYEARECAAYFAlA/a/oACgkQevm6Dd/q44nJXQCffaxEJ/NZEftgoZ7viAWMuBO3
 +jkAnRTw+VCMQn1k9NibyKpkGMtwvrQw
 =ds3M
 -END PGP SIGNATURE-

 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Erik Hesselink
On Thu, Aug 30, 2012 at 7:24 PM, wren ng thornton w...@freegeek.org wrote:
 On 8/30/12 10:26 AM, Erik Hesselink wrote:
 * Packages might not work with the new bytestring version, since the
 API has breaking changes (although they're supposed to be minor).

 For the first two, you need to add some CPP, for the last, you need
 actual testing.

 Actually, that can be more problematic than you suspect. In particular,
 hsc2hs does not play nicely with Cabal's MIN_VERSION_foo(1,2,3) macros. So
 if you're using hsc2hs, which is common for certain FFI uses, then you have
 to put up with the warnings or rely on the __GLASGOW_HASKELL__ macro in lieu
 of the MIN_VERSION_foo(1,2,3) macros. It's doable, but it's uglier and more
 hackish than it ought to be.

Ah yes, I found this out a while ago on one of my packages. As a tip
for those doing this: the value of __GLASGOW_HASKELL__ is xyy, with x
the first version component, and y the second. So, say, 7.4.2 has a
value of 704, not 742.

Erik

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] happstack simpleHTTP state monad

2012-08-30 Thread Erik Hesselink
The way you wrote it, you run the state transformer once for each
request. So the state will be available within a single request, but
not between requests. If you want to persist state between requests,
you can use one the the mutable variables available (TVar or MVar are
good choices; IORefs also work, but you have to take care about
concurrency, using e.g. atomicModifyIORef). Create them before calling
simpleHTTP, then pass them in to use them in your handler. You can put
them in a ReaderT to avoid passing them, if you want.

Another choice is to use something like a database or the file system
for persistent state. Databases usually handle most concurrency
problems for you, while file systems don't.

Regards,

Erik

On Thu, Aug 30, 2012 at 7:29 PM, Corentin Dupont
corentin.dup...@gmail.com wrote:
 Hi all,
 I'm trying to make a web server that manages its own state. The user can
 issue commands that modifies the state.
 I did like below but unfortunatly the state is not keep after a command is
 issued...
 What is the right way to do it? Is there any example sites with an internal
 state with happstack?

 data Game = (the state of my game)
 type NomicServer = ServerPartT (StateT Game IO)

 launchWebServer :: Game - IO ()
 launchWebServer initialState = do
putStrLn Starting web server...\nTo connect, drive your browser to
 \http://localhost:8000/Login\;
d - getDataDir
simpleHTTP' unpackStateT nullConf $ server d


 server :: FilePath - ServerPartT (StateT Game IO) Response
 server d sh = mconcat [fileServe [] d, do
decodeBody (defaultBodyPolicy /tmp/
 4096 4096 4096)
html - implSite http://localhost:8000/;
  nomicSite
return $ toResponse html]

 unpackStateT:: Game - UnWebT (StateT Game IO) Response - UnWebT IO
 Response
 unpackStateT g w = evalStateT w g

 --handler for web routes
 nomicSite :: Site PlayerCommand (NomicServer Html)
 nomicSite = setDefault (Noop 0) Site {
   handleSite = \f url - unRouteT (routedNomicCommands url) f
 , formatPathSegments = \u - (toPathSegments u, [])
 , parsePathSegments  = parseSegments fromPathSegments
 }

 Thanks a lot,
 Corentin
 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


[Haskell-cafe] why do I need class context in declaring data constructor?

2012-08-30 Thread Paul Liu
I had a toy program that encodes simply typed lambda in types. It used
to work fine with GHC prior to 7.2. But now it no longer compiles.
Here is a minimal fragment that demonstrates this problem.

 {-# LANGUAGE GADTs,
 MultiParamTypeClasses,
 FlexibleInstances,
 FlexibleContexts #-}

 data Abs env t v where
   Abs :: g (a, env) h v - Abs env (g (a, env) h v) (a - v)

 class Eval g env t v where
   eval :: env - g env t v - v

 instance Eval g (a, env) h v =
  Eval Abs env (g (a, env) h v) (a - v) where
   eval env (Abs e) = \x - eval (x, env) e

The type Abs has 3 parameters: its environment, sub term (encoded in
types), and type. The constructor Abs has 1 parameter: its sub term.
The code loads fine in GHC 7.0.3.

Here is the error reported by GHC 7.2.2 (and later):

test.lhs:14:30:
Could not deduce (Eval g1 (a1, env) h1 v1)
  arising from a use of `eval'
from the context (Eval g (a, env) h v)
  bound by the instance declaration at test.lhs:(12,12)-(13,49)
or from (g (a, env) h v ~ g1 (a1, env) h1 v1,
 (a - v) ~ (a1 - v1))
  bound by a pattern with constructor
 Abs :: forall env (g :: * - * - * - *) a h v.
g (a, env) h v - Abs env (g (a, env) h v) (a - v),
   in an equation for `eval'
  at test.lhs:14:15-19
Possible fix:
  add (Eval g1 (a1, env) h1 v1) to the context of
the data constructor `Abs'
or the instance declaration
  or add an instance declaration for (Eval g1 (a1, env) h1 v1)
In the expression: eval (x, env) e
In the expression: \ x - eval (x, env) e
In an equation for `eval':
eval env (Abs e) = \ x - eval (x, env) e

However, if I move the class context to the data constructor of
definition, then it compiles fine in GHC 7.2.2 (and later):

 data Abs env t v where
   Abs :: Eval g (a, env) h v = g (a, env) h v - Abs env (g (a, env) h v) (a 
 - v)

But this is very troublesome because for every new class instance I
want to make Abs of, I have to make a new class context to the data
constructor. It totally defeats the purpose of making class instances
to extend usage of data types.

Did I missed a language extension when moving code from GHC 7.0.3 to
GHC 7.2.2? What can I do to fix it for newer GHCs?

-- 
Regards,
Paul Liu

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Build regressions due to GHC 7.6

2012-08-30 Thread Jay Sulzberger



On Thu, 30 Aug 2012, Alexander Kjeldaas alexander.kjeld...@gmail.com wrote:


This is very unfortunate, but this is crucially a tooling issue.  I am
going to wave my hands, but..

Ignore the mapreduce in the following video, but look at the use of clang
to do automatic refactoring of C++.  This is *incredibly* powerful in
dealing with updates to APIs.

http://www.llvm.org/devmtg/2011-11/videos/Carruth_ClangMapReduce-desktop.mp4

But without all that fancy tech, *just* having all of Hackage source code
in one repository and using perl/regexps, fixing these types of issues is
O(1) instead of O(n).

All of the issues you mention seems to be fixable by a few lines of perl
*if we had the repository*.


Better to do this with sexps.

ad repositories: Part of the general problem of managing a
repository is close to the problem of inferring a good type for
(the value of) an expression.  The style of constraints is
similar.  Now the design problem is:

1. Arrange a general system for the specification of the
   constraints.

2. Design a systematic way of giving both advice and direct
   commands to the system.  This subsystem would be used to set
   up the default policy.

3. Choose a constraint solver.

Maybe worth looking at:

  http://en.wikipedia.org/wiki/Nix_package_manager
  [page was last modified on 17 July 2012 at 20:20]

oo--JS.




[a few hours later]

Actually, I went and downloaded all of hackage, put it into a git
repository and fixed these issues:

Fix catch
perl -ni -e 'print unless /import Prelude hiding \(catch\)/' $(git grep
'import Prelude hiding (catch)')

Fix CInt constructors (lots of other stuff from Foreign.C.Types not fixed
though)
perl -p -i -e 's/^import Foreign.C.Types(.*)CInt([^(])/import
Foreign.C.Types${1}CInt(..)${1}/g' $(git grep -l '^import.*CInt')

Fix bytestring versioning
perl -p -i -e 's/bytestring( +)=([0-9. ]+)([
]*)0.10/bytestring$1=$2${3}0.11/g' $(git grep 'bytestring.* *0\.')

Patch to hackage:
http://ge.tt/6Cb5ErM/v/0

I understand that this doesn't help anyone, but if there was a way fix,
upload, and get *consensus* on a few regexps like this, then doing API
changes wouldn't be such a headache.

Alexander

On 30 August 2012 07:26, Bryan O'Sullivan b...@serpentine.com wrote:


Since the release of the GHC 7.6 RC, I've been going through my packages
and fixing up build problems so that people who upgrade to 7.6 will have a
smooth ride.

Sad to say, my experience of 7.6 is that it has felt like a particularly
rough release for backwards incompatibility. I wanted to quantify the pain,
so I did some research, and here's what I found.

I maintain 25 open source Haskell packages. Of these, the majority have
needed updates due to the GHC 7.6 release:

   - base16-bytestring
   - blaze-textual
   - bloomfilter
   - configurator
   - criterion
   - double-conversion
   - filemanip
   - HDBC-mysql
   - mwc-random
   - pcap
   - pool
   - riak-haskell-client
   - snappy
   - text
   - text-format
   - text-icu

That's 16 out of 25 packages I've had to update. I've also either reported
bugs on, or had to fix, several other people's packages along the way
(maybe four?). So let's say I've run into problems with 20 out of the
combined 29 packages of mine and my upstreams.

The reasons for these problems fall into three bins:

   - Prelude no longer exports catch, so a lot of import Prelude hiding
   (catch) had to change.
   - The FFI now requires constructors to be visible, so CInt has to be
   imported as CInt(..).
   - bytestring finally got bumped to 0.10, so many upper bounds had to
   be relaxed (*cf* my suggestion that the upper-bounds-by-default policy
   is destructive).

It has been a lot of work to test 29 packages, and then modify, rebuild,
and release 20 of them. It has consumed most of my limited free time for
almost two weeks. Worse, this has felt like make-work, of no practical
benefit to anyone beyond scrambling to restore the status quo ante.

If over half of my packages needed fixing, I'm alarmed at the thought of
the effects on the rest of Hackage.

I'm torn over this. I understand and agree with the impetus to improve the
platform by tidying things up, and yet just two seemingly innocuous changes
(catch and FFI) have forced me to do a bunch of running to stand still.

I don't have any suggestions about what to do; I know that it's hard to
estimate the downstream effects of what look like small changes. And so I'm
not exactly complaining. Call this an unhappy data point.

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe






___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] happstack simpleHTTP state monad

2012-08-30 Thread Corentin Dupont
Hi Erik,
yes you're right, I'm experimenting with an IORef now (a TVar would be a
better idea).
I also tried the idea expressed here, to keep the state:
https://groups.google.com/forum/?fromgroups=#!msg/happs/_JSpaJKub0k/oa0K01IBlh0J
But without success so far. The server is returning me the state in the
Response type but I cannot manage to reinject it for the next call :)

Best,
Corentin

On Thu, Aug 30, 2012 at 9:47 PM, Erik Hesselink hessel...@gmail.com wrote:

 The way you wrote it, you run the state transformer once for each
 request. So the state will be available within a single request, but
 not between requests. If you want to persist state between requests,
 you can use one the the mutable variables available (TVar or MVar are
 good choices; IORefs also work, but you have to take care about
 concurrency, using e.g. atomicModifyIORef). Create them before calling
 simpleHTTP, then pass them in to use them in your handler. You can put
 them in a ReaderT to avoid passing them, if you want.

 Another choice is to use something like a database or the file system
 for persistent state. Databases usually handle most concurrency
 problems for you, while file systems don't.

 Regards,

 Erik

 On Thu, Aug 30, 2012 at 7:29 PM, Corentin Dupont
 corentin.dup...@gmail.com wrote:
  Hi all,
  I'm trying to make a web server that manages its own state. The user can
  issue commands that modifies the state.
  I did like below but unfortunatly the state is not keep after a command
 is
  issued...
  What is the right way to do it? Is there any example sites with an
 internal
  state with happstack?
 
  data Game = (the state of my game)
  type NomicServer = ServerPartT (StateT Game IO)
 
  launchWebServer :: Game - IO ()
  launchWebServer initialState = do
 putStrLn Starting web server...\nTo connect, drive your browser to
  \http://localhost:8000/Login\;
 d - getDataDir
 simpleHTTP' unpackStateT nullConf $ server d
 
 
  server :: FilePath - ServerPartT (StateT Game IO) Response
  server d sh = mconcat [fileServe [] d, do
 decodeBody (defaultBodyPolicy /tmp/
  4096 4096 4096)
 html - implSite 
 http://localhost:8000/;
   nomicSite
 return $ toResponse html]
 
  unpackStateT:: Game - UnWebT (StateT Game IO) Response - UnWebT IO
  Response
  unpackStateT g w = evalStateT w g
 
  --handler for web routes
  nomicSite :: Site PlayerCommand (NomicServer Html)
  nomicSite = setDefault (Noop 0) Site {
handleSite = \f url - unRouteT (routedNomicCommands url) f
  , formatPathSegments = \u - (toPathSegments u, [])
  , parsePathSegments  = parseSegments fromPathSegments
  }
 
  Thanks a lot,
  Corentin
  ___
  Haskell-Cafe mailing list
  Haskell-Cafe@haskell.org
  http://www.haskell.org/mailman/listinfo/haskell-cafe
 

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma

2012-08-30 Thread Thomas Schilling
On 30 August 2012 09:34, Joachim Breitner breit...@kit.edu wrote:

 but from a first glance it seems that you are not using that part of GHC
 in your project, right?


No, I don't think I can make use of your work directly. Lambdachine uses
GHC up until the CorePrep phase (the last phase before conversion to STG, I
think). I'll probably need a dynamic tagging mechanism to keep track of
what's potentially shared. Not sure what the overhead of that will be.

/ Thomas
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] createProcess running non-existent programs

2012-08-30 Thread Niklas Hambüchen
Well, overhead or not, it would be nice to at least have *some* solution.

Currently, it just doesn't work.

I am sure that as soon the functionality is there, somebody will step in
to fake it fast.

On 15/08/12 06:25, Donn Cave wrote:
 Quoth Alexander Kjeldaas alexander.kjeld...@gmail.com,
 
 See access(2)
 
 ... a classic code smell in UNIX programming, for the same reasons.
 
 We can solve this problem in an efficient way that works well, and equally
 well, on any POSIX platform that supports F_CLOEXEC on pipes, and I can't
 think of anything that doesn't.  The appended code is the basic gist of it.
 This was not invented by the Python world, but as suggested it's one of
 the things that we'd get from a review of their subprocess module.
 
   Donn
 
 spawn file cmd env = do
   (e0, e1) - pipe
   fcntlSetFlag e1 F_CLOEXEC
   t - fork (fex e0 e1)
   close e1
   rx - readFd e0 256
   if null rx
  then return t
  else ioerr (chrToErrType rx) file
   where
  fex e0 e1 = do
close e0
catch  (execve file cmd env)
   (\ e - writeFd e1 (errToChr e : ioeGetErrorString e))
  ioerr (e, s) file = ioError (mkIOError e s Nothing (Just file))
 
 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe
 

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


[Haskell-cafe] Function names in Haskell lib not first-class on web!

2012-08-30 Thread damodar kulkarni
Hi Cafe,
It seems, the function names in Haskell libs are not first-class objects,
AT LEAST when it comes to searching for them of the net!
I was trying to search for the following Haskell functions in the mailing
list archives. Here is a summary of the responses I have had from various
servers upon searching various valid and normally used Haskell function
identifiers from well-known libraries.

Responses from the http://www.mail-archive.com
 =http://www.mail-archive.com/search?l=haskell-cafe%40haskell.orgq=%3E%3E%3D,
It seems the script searched for the string *gt*; *gt*;
* - 
*http://www.mail-archive.com/search?l=haskell-cafe%40haskell.orgq=*+-%3E+*There
are 0 results.
and so on...

Responses from the http://search.gmane.org
=http://search.gmane.org/search.php?group=gmane.comp.lang.haskell.cafequery=%3E%3E%3D
Here, too, it seems the script searched for the string *gt*; *gt*;
* - 
*http://search.gmane.org/?query=*+-%3E+*author=group=gmane.comp.lang.haskell.cafesort=relevanceDEFAULTOP=andxFILTERS=Gcomp.lang.haskell.cafe---A
Here it seems the script searched for the string *gt*;
and so on...

*Note: google badly fails to search these functions identifiers.*

My current solution to this problem is: download compressed text archives
and do a simple grep on it on my machine.

But the archives up to year 2000 only are found at
http://www.haskell.org/pipermail/haskell-cafe/.
So, as an aside: Where do I find the earlier messages for downloading?

Thanks,
Damodar
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Function names in Haskell lib not first-class on web!

2012-08-30 Thread Kristopher Micinski
On Thu, Aug 30, 2012 at 11:21 PM, damodar kulkarni
kdamodar2...@gmail.com wrote:
 Hi Cafe,
 It seems, the function names in Haskell libs are not first-class objects, AT
 LEAST when it comes to searching for them of the net!
 I was trying to search for the following Haskell functions in the mailing
 list archives. Here is a summary of the responses I have had from various
 servers upon searching various valid and normally used Haskell function
 identifiers from well-known libraries.

 Responses from the http://www.mail-archive.com
  =, It seems the script searched for the string gt; gt;
 * - *There are 0 results.
 and so on...

 Responses from the http://search.gmane.org
=  Here, too, it seems the script searched for the string gt; gt;
 * - *  Here it seems the script searched for the string gt;
 and so on...

 Note: google badly fails to search these functions identifiers.

 My current solution to this problem is: download compressed text archives
 and do a simple grep on it on my machine.

 But the archives up to year 2000 only are found at
 http://www.haskell.org/pipermail/haskell-cafe/.
 So, as an aside: Where do I find the earlier messages for downloading?

 Thanks,
 Damodar


You know about Hoogle, right?

kris

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


[Haskell-cafe] Sliding Window functional data structure

2012-08-30 Thread Richard O'Keefe
Consider the following interface

type Ord k = Sliding_Window k v

entries :: Sliding_Window k v - [(k,v)]
The cost is expected to be linear in the length of
the result.  The pairs are listed in increasing
order of k.

add :: Ord k = k - v - Sliding_Window k v - Sliding_Window k v
precondition: all ( k) [k' | (k',_) - entries q]
The cost should be at most O((log . length . entries) q).
post: entries (add k v q) = entries q ++ [(k,v)]

since :: Ord k = k - Sliding_Window k v - [(k,v)]
answers [(k',v) | (k',v) - entries q, k'  k]
The cost should be at most O((log . length . entries) q
 + length result)

purge :: Ord k = k - Sliding_Window k v - Sliding_Window k v
answers q' such that entries q' = [(k',v) | (k',v) - entries q,
   k'  k]
The cost should be at most O((log . length . entries) q
 + length [k' | (k',v) - entries q,
k' = k])

Ignoring costs, this can obviously be done trivially using
a list of pairs.  Paying some attention to costs, it can also
be done using some sort of balanced search tree.  The data
structure is close to a priority queue, but subtly different.

I believe I can see how to do this in an imperative language
using a Dijkstra-style array of pairs:  add is amortised O(1)
using the well known doubling strategy, thanks to the strictly
increasing key requirement; since is a binary search followed
by a segment copy; purge is a binary search followed by nilling
out the now unwanted elements.  By adapting the back-to-back
pair of lists implementation of queues, we can obviously do
add in O(1) and purge in O(1+#deleted items) time in a pure
functional language.

Thing is, there's a baffling array of data structures to examine
(AVL, RB, 2-3, 2-3-4, 1-2-brother, finger ... trees) and I wondered
if anyone had any idea what would be particularly good for this
rather asymmetric problem.



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe