Re: [Haskell-cafe] feasability of implementing an awk interpreter.
On Aug 21, 2010, at 5:14 AM, Michael Litchard wrote:
Thank you all for your encouragement. I need to think about the core
functionality, and do some reading.
But what _is_ the core functionality.
The Single Unix Specification can be browsed on-line.
There is no part of it labelled core; it's all required
or it isn't AWK. There are weird little gotchas like
File foo = '{ prin'
File bar = 't 2 }'
awk -f foo -f bar
is legal and is required to act the same as
awk '{ print 2 }'
mawk fails this, and I don't blame it, and I don't really _care_.
Is that core? Who knows?
Whatever the core functionality might be, YOU will have to define
what that core is. There's no standard, or even common, sublanguage.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unix emulation
On 23 August 2010 06:12, Erik de Castro Lopo mle...@mega-nerd.com wrote: I'm going to be a bit of a heretic here and suggest that you attack this problem from the other end. How you ask? Install Debian Testing/Unstable with Wine in a VM and cross compile to Windows. No - that's a completely azzback solution. MinGW / MSYS works fine, the problem is solely that the documentation of the install procedure has gone awry, with conflicting and seemingly out of date guides on the mingw.org website. The best solution would be to sign up to the mingw-user mailing list and ask what the currently preferred method is for installing. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] feasability of implementing an awk interpreter.
On Mon, Aug 23, 2010 at 8:07 AM, Richard O'Keefe o...@cs.otago.ac.nz wrote:
But what _is_ the core functionality.
The Single Unix Specification can be browsed on-line.
There is no part of it labelled core; it's all required
or it isn't AWK. There are weird little gotchas like
File foo = '{ prin'
File bar = 't 2 }'
awk -f foo -f bar
is legal and is required to act the same as
awk '{ print 2 }'
mawk fails this, and I don't blame it, and I don't really _care_.
Is that core? Who knows?
I say that that behaviour is not part of the language but of the runtime.
Whatever the core functionality might be, YOU will have to define
what that core is. There's no standard, or even common, sublanguage.
One approach to find the core of a language is to find which parts can
be implemented in terms of other parts. If part B can be expressed in
terms of part A then B doesn't belong in the core.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
Conal Elliott wrote: For anyone interested in iteratees (etc) and not yet on the iteratees mailing list. I'm asking about what iteratees *mean* (denote), independent of the various implementations. My original note (also at the end below): In my world view, iteratees are just a monad M with a single operation symbol :: M Char that reads the next symbol from an input stream. In other words, they're a very simple parser monad. The emphasis is not on parsing, but on the fact that one and the same monadic value can be run on different streams runHandle :: M a - Handle - IO a runString :: M a - String - a runByteString :: M a - ByteString - a The monad M may also include convenience like exceptions and liftIO . I have omitted the chunking [Char] because I don't like it; invariance with respect to the chunk sizes is something that should be left to the iteratee abstraction. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] ANNOUNCE: enumerator, an alternative iteratee package
On Sat, 21 Aug 2010 13:36:08 -0700, John Millikin jmilli...@gmail.com wrote: On Sat, Aug 21, 2010 at 12:44, Magnus Therning mag...@therning.org wrote: As an aside, has anyone written the code necessary to convert a parser, such as e.g. attoparsec, into an enumerator-iteratee[1]? This sort of conversion is trivial. For an example, I've uploaded the attoparsec-enumerator package at http://hackage.haskell.org/package/attoparsec-enumerator -- iterParser is about 20 lines, excluding the module header and imports. A.Done extra a - E.yield a (E.Chunks [extra]) Maybe it would be better to check if extra is empty to produce an empty list of chunks? -- Nicolas Pouillard http://nicolaspouillard.fr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Unix emulation
I'd agree with Stephen. I've used MinGW / msys for years and would never consider doing any open source development (especially involving C) without it. In the past, installing it has only taken a few minutes. That still looks to be the case for MinGW but it now appears that msys has been split into a confusing and long list of packages. I think that it needs a standard installer as well (in fact the combined MinGW/msys package needs one standard installer as I think it is rare these days to use one without the other.) Kevin On Aug 23, 8:53 am, Stephen Tetley stephen.tet...@gmail.com wrote: On 23 August 2010 06:12, Erik de Castro Lopo mle...@mega-nerd.com wrote: I'm going to be a bit of a heretic here and suggest that you attack this problem from the other end. How you ask? Install Debian Testing/Unstable with Wine in a VM and cross compile to Windows. No - that's a completely azzback solution. MinGW / MSYS works fine, the problem is solely that the documentation of the install procedure has gone awry, with conflicting and seemingly out of date guides on the mingw.org website. The best solution would be to sign up to the mingw-user mailing list and ask what the currently preferred method is for installing. ___ Haskell-Cafe mailing list haskell-c...@haskell.orghttp://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] ICFP '10: Final call for participation
= Final Call for Participation The 15th ACM SIGPLAN International Conference on Functional Programming (ICFP 2010) http://www.icfpconference.org/icfp2010/ Baltimore, Maryland September 25 – October 2 = ICFP 2010 provides a forum for researchers and developers to hear about the latest work on the design, implementations, principles, and uses of functional programming. The conference covers the entire spectrum of work, from practice to theory, including its peripheries. ** Not that the early registration deadline and discount hotel rates expire next week. ** * Program: http://www.icfpconference.org/icfp2010/program.html * Invited speakers: - Mike Gordon ML: Metalanguage or Object Language? - Matthias Felleisen TeachScheme!: A Checkpoint - Guy Blelloch Functional Parallel Algorithms Schedule including related events: * September 25: Workshop on Mechanizing Metatheory (WMM) Workshop on Mathematically Structured Functional Programming (MSFP) Workshop on High-Level Parallel Programming and Applications (HLPP) * September 26: Workshop on ML Workshop on Generic Programming (WGP) * September 27-29: ICFP 2010 * September 30: Haskell Symposium Erlang Workshop * October 1: Commercial Users of Functional Programming – Day 1 (CUFP Tutorials) Haskell Implementors' Workshop * October 2: Commercial Users of Functional Programming – Day 2 (CUFP Talks) This year there will also be a special series of Birds-of-a-Feather sessions associated with CUFP. More information can be found at: http://cufp.org/bofs-2010 Registration information: * Registration link: https://regmaster3.com/2010conf/ICFP10/register.php Local arrangements (including travel and accommodation): * http://www.icfpconference.org/icfp2010/local.html * Conference reservation/rate deadline: September 1st Conference organizers: * General Chair: Paul Hudak, Yale University * Program Chair: Stephanie Weirich, University of Pennsylvania * Local Arrangements Chair: Michael Hicks, University of Maryland * Workshop Co-Chairs: Derek Dreyer, Max Planck Institute for Software Systems Christopher Stone, Harvey Mudd College * Programming Contest Chair: Johannes Waldmann, Hochschule für Technik, Wirtschaft und Kultur, Leipzig * Video Chair: Scott Smith, Johns Hopkins University * Publicity Chair: Wouter Swierstra, Vector Fabrics = ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Trouble with winGHCi
Hi David Maybe WinGHCi (the gui) it is failing to start GHCi (the interpreter)? Though then going to a black screen of death is very bad. On my system I can run WinGHCi from HP2010.2.0.0 - but it runs an old version of GHCi. This makes me suspect it is using the /path/ environment variable to find GHCi. What happens when you open a command prompt and type / ghci / ? You should get something like this: C:\Documents and Settings\me ghci GHCi, version 6.12.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Loading package ffi-1.0 ... linking ... done. Prelude Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple Sudoku solver using Control.Monad.Logic
On Aug 22, 2010, at 11:09 PM, Vladimir Matveev wrote: are there any materials except LogicT.pdf from link on the logict hackage entry? I'd like to read something on this interesting topic The functional pearl A program to solve Sudoku by Richard Bird http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/ sudoku.pdf is an interesting read. If you get your hands on a copy of The Fun of Programming, which has been edited in honour of Richard Birds 60th birthday, you can have a look at Chapter 9, Combinators for logic programming by Mike Spivey and Silvija Seres I did not find this chapter online. Issue 15 of the Monad.Reader contains Adventures in Three Monads by Edward Z. Yang http://themonadreader.files.wordpress.com/2010/01/issue15.pdf which gives an introduction to the Logic monad (and two others). In my doctoral thesis I give a brief introduction to nondeterminism monads in general and how to implement some specific instances: On Functional-Logic Programming and its Application to Testing by Sebastian Fischer Section 5.1, Nondeterminism monads http://www-ps.informatik.uni-kiel.de/~sebf/thesis.pdf There are various nondeterminism monads on Hackage. If you restrict your algorithm to only use the MonadPlus interface you can experiment with all of them simply by changing a type signature. The list monad (not on Hackage because defined in the Prelude) implements backtracking via depth-first search. The Hackage package control-monad-omega [1] by Luke Palmer uses list diagonalisation to overcome limitations of the list monad. It is described to implement breadth-first search which, in my opinion, it doesn't exactly. My package level-monad [2] provides monads for iterative deepening depth-first search and breadth-first search. The latter enumerates results of the search space in breadth-first (that is level) order. The former does something similar with better space usage. The different implementations of nondeterminism monads often differ significantly in how much memory they use. The list monad uses little memory but often diverges when the search space is infinite. Breadth- first search is a complete strategy (it does not diverge infinite search spaces and, thus, eventually finds every result) but has excessive memory requirements. Oleg Kiselyov has invented a complete strategy with moderate memory requirements which I have packaged as stream-monad [3]. I recommend using the list or logic monad if the search space is finite and the stream monad or iterative deepening dfs if the search space is infinite. Cheers, Sebastian [1]: http://hackage.haskell.org/package/control-monad-omega [2]: http://hackage.haskell.org/package/level-monad [3]: http://hackage.haskell.org/package/stream-monad -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Re: ANNOUNCE: enumerator, an alternative iteratee package
On 21/08/2010 04:30, John Millikin wrote: This also changes the binary enumHandle to use non-blocking IO, as recommended by Magnus Therning. I'm embarrassed to admit I still don't understand the improvement, exactly, but three people so far have told me it's a good idea. The issue is that hGet always waits for a complete buffer-full of data before returning. The hWaitForInput/hGetNonBlocking combination fixes that problem, but you have to be careful to make sure that the Handle is in binary mode, otherwise hWaitForInput will not behave the way you expect (it will decode the input byte stream, and wait for a full character). For more information, see http://hackage.haskell.org/trac/ghc/ticket/3808 A better fix is to use hGetBufSome, but (a) it is only available in GHC 6.14 which isn't released yet, and (b) there isn't a bytestring wrapper for it yet. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple Sudoku solver using Control.Monad.Logic
Many thanks. This is very useful :) 2010/8/23 Sebastian Fischer s...@informatik.uni-kiel.de: On Aug 22, 2010, at 11:09 PM, Vladimir Matveev wrote: are there any materials except LogicT.pdf from link on the logict hackage entry? I'd like to read something on this interesting topic The functional pearl A program to solve Sudoku by Richard Bird http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/sudoku.pdf is an interesting read. If you get your hands on a copy of The Fun of Programming, which has been edited in honour of Richard Birds 60th birthday, you can have a look at Chapter 9, Combinators for logic programming by Mike Spivey and Silvija Seres I did not find this chapter online. Issue 15 of the Monad.Reader contains Adventures in Three Monads by Edward Z. Yang http://themonadreader.files.wordpress.com/2010/01/issue15.pdf which gives an introduction to the Logic monad (and two others). In my doctoral thesis I give a brief introduction to nondeterminism monads in general and how to implement some specific instances: On Functional-Logic Programming and its Application to Testing by Sebastian Fischer Section 5.1, Nondeterminism monads http://www-ps.informatik.uni-kiel.de/~sebf/thesis.pdf There are various nondeterminism monads on Hackage. If you restrict your algorithm to only use the MonadPlus interface you can experiment with all of them simply by changing a type signature. The list monad (not on Hackage because defined in the Prelude) implements backtracking via depth-first search. The Hackage package control-monad-omega [1] by Luke Palmer uses list diagonalisation to overcome limitations of the list monad. It is described to implement breadth-first search which, in my opinion, it doesn't exactly. My package level-monad [2] provides monads for iterative deepening depth-first search and breadth-first search. The latter enumerates results of the search space in breadth-first (that is level) order. The former does something similar with better space usage. The different implementations of nondeterminism monads often differ significantly in how much memory they use. The list monad uses little memory but often diverges when the search space is infinite. Breadth-first search is a complete strategy (it does not diverge infinite search spaces and, thus, eventually finds every result) but has excessive memory requirements. Oleg Kiselyov has invented a complete strategy with moderate memory requirements which I have packaged as stream-monad [3]. I recommend using the list or logic monad if the search space is finite and the stream monad or iterative deepening dfs if the search space is infinite. Cheers, Sebastian [1]: http://hackage.haskell.org/package/control-monad-omega [2]: http://hackage.haskell.org/package/level-monad [3]: http://hackage.haskell.org/package/stream-monad -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Re: ANNOUNCE: enumerator, an alternative iteratee package
Hello, Simon! On Mon, Aug 23, 2010 at 8:00 AM, Simon Marlow marlo...@gmail.com wrote: The issue is that hGet always waits for a complete buffer-full of data before returning. The hWaitForInput/hGetNonBlocking combination fixes that problem, but you have to be careful to make sure that the Handle is in binary mode, otherwise hWaitForInput will not behave the way you expect (it will decode the input byte stream, and wait for a full character). For more information, see http://hackage.haskell.org/trac/ghc/ticket/3808 A better fix is to use hGetBufSome, but (a) it is only available in GHC 6.14 which isn't released yet, and (b) there isn't a bytestring wrapper for it yet. So there really is a problem in the documentation of hGetBuf. I assume it got fixed in HEAD together with hGetBufSome. Cheers! =) -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
On Mon, Aug 23, 2010 at 1:06 AM, Heinrich Apfelmus apfel...@quantentunnel.de wrote: Conal Elliott wrote: For anyone interested in iteratees (etc) and not yet on the iteratees mailing list. I'm asking about what iteratees *mean* (denote), independent of the various implementations. My original note (also at the end below): In my world view, iteratees are just a monad M with a single operation symbol :: M Char that reads the next symbol from an input stream. So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) = MaybeT (State [Char]) a symbol [] = Nothing symbol (c:cs) = Just (c, cs) I'm not experienced with iteratees. Does this miss something? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: enumerator, an alternative iteratee package
From: John Millikin jmilli...@gmail.com On Sat, Aug 21, 2010 at 15:35, Paulo Tanimoto ptanim...@gmail.com wrote: Apologies if I'm asking you to repeat yourself, but I couldn't find the explanation. Â What was the reason why you went with IterateeM instead of IterateeMCPS? Â Simplicity? Iteratees are difficult enough to understand already -- requiring prospective users to learn and understand CPS would just be another roadblock. The CPS implementation is also slower -- I performed some basic benchmarking of IterateeM.hs and IterateeMCPS.hs, and CPS is only faster without optimizations. At -O, they are equal, and at -O2, IterateeM is faster. Apologies if this discussion has already moved on; I'm just catching up on weekend email but wanted to respond to this directly. It's not necessary to understand CPS to use CPS-based iteratees. The CPS implementation generally simplifies the types and removes the necessity for special combinators like ($$) and (==), so I strongly suspect newcomers will find it easier to use than other variants (although unfortunately I can no longer say this from personal experience). It incorporates the best features of Oleg's two implementations in IterateeM.hs. The only drawback is the added thought overhead of CPS, but users need not be aware of this for the most part. For those who do want to have a thorough understanding of the implementation, I think that the CPS variant is usually more understandable than alternatives. The take family and stream converters (maps, convStream) are all simplified compared to alternative definitions. This isn't always true; enumPair is a counterexample. But I think it's helpful in many common cases, and enumPair is tricky in any implementation. It might be true that many programmers will find CPS difficult in the abstract (I certainly do), but when it occurs in a specific implementation the concepts are usually much more tractable. At least for iteratees, there's a very direct correspondence between the CPS-style and IterateeM-style, which greatly eases understanding. Also, while the IterateeM implementations may be faster for certain operations than CPS, they are also slower for others, sometimes significantly so. My tests (all with -O2, and various other compiler options tried) prior to switching to the CPS implementation showed that it is competitive with, if not being, the fastest implementation in all cases. Most importantly, I didn't find any comparatively slow operations, which wasn't true for either of the IterateeM implementations. I think that a CPS implementation of iteratees is the best of all current alternatives for ease of use, and possibly the best-performing implementation depending on exactly what operations are being performed. Even if it's not the absolute fastest, it should be close enough that the other benefits outweigh a performance gain. Cheers, John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Re: ANNOUNCE: enumerator, an alternative iteratee package
On 23/08/2010 12:10, Felipe Lessa wrote: Hello, Simon! On Mon, Aug 23, 2010 at 8:00 AM, Simon Marlowmarlo...@gmail.com wrote: The issue is that hGet always waits for a complete buffer-full of data before returning. The hWaitForInput/hGetNonBlocking combination fixes that problem, but you have to be careful to make sure that the Handle is in binary mode, otherwise hWaitForInput will not behave the way you expect (it will decode the input byte stream, and wait for a full character). For more information, see http://hackage.haskell.org/trac/ghc/ticket/3808 A better fix is to use hGetBufSome, but (a) it is only available in GHC 6.14 which isn't released yet, and (b) there isn't a bytestring wrapper for it yet. So there really is a problem in the documentation of hGetBuf. I assume it got fixed in HEAD together with hGetBufSome. Which documentation are you referring to? This looks ok to me: http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/System-IO.html#v%3AhGetBuf Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Re: ANNOUNCE: enumerator, an alternative iteratee package
On Mon, Aug 23, 2010 at 8:29 AM, Simon Marlow marlo...@gmail.com wrote: Which documentation are you referring to? This looks ok to me: http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/System-IO.html#v%3AhGetBuf Indeed, while there isn't a big fat warning, it does say that it reads 'count' bytes. However, both RawIO.read and BufferedIO.fillReadBuffer are a bit misleading. The former says that it doesn't block when there isn't data available, the latter doesn't say anything. http://hackage.haskell.org/packages/archive/base/4.2.0.1/doc/html/src/GHC-IO-Device.html#RawIO http://hackage.haskell.org/packages/archive/base/4.2.0.1/doc/html/src/GHC-IO-BufferedIO.html#BufferedIO Cheers! =) -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Re: ANNOUNCE: enumerator, an alternative iteratee package
On 23/08/2010 12:38, Felipe Lessa wrote: On Mon, Aug 23, 2010 at 8:29 AM, Simon Marlowmarlo...@gmail.com wrote: Which documentation are you referring to? This looks ok to me: http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/System-IO.html#v%3AhGetBuf Indeed, while there isn't a big fat warning, it does say that it reads 'count' bytes. However, both RawIO.read and BufferedIO.fillReadBuffer are a bit misleading. The former says that it doesn't block when there isn't data available, the latter doesn't say anything. http://hackage.haskell.org/packages/archive/base/4.2.0.1/doc/html/src/GHC-IO-Device.html#RawIO http://hackage.haskell.org/packages/archive/base/4.2.0.1/doc/html/src/GHC-IO-BufferedIO.html#BufferedIO Hmm, RawIO.read looks ok: -- | Read up to the specified number of bytes, returning the number -- of bytes actually read. This function should only block if there -- is no data available. If there is not enough data available, -- then the function should just return the available data. A return -- value of zero indicates that the end of the data stream (e.g. end -- of file) has been reached. that seems pretty clear to me. No? I'll expand the documentation for fillReadBuffer. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Re: ANNOUNCE: enumerator, an alternative iteratee package
On Mon, Aug 23, 2010 at 8:51 AM, Simon Marlow marlo...@gmail.com wrote: Hmm, RawIO.read looks ok: -- | Read up to the specified number of bytes, returning the number -- of bytes actually read. This function should only block if there -- is no data available. If there is not enough data available, -- then the function should just return the available data. A return -- value of zero indicates that the end of the data stream (e.g. end -- of file) has been reached. that seems pretty clear to me. No? It says that it should only block if there is no data available. I assumed that fillReadBuffer has the same semantics. If both do not block if there is data, then hGetBuf would not wait for the buffer to be filled, if I am reading its source correctly [1]. Either they do block until the buffer is filled, or I'm misreading hGetBuf/bufRead. =) [1] http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/GHC-IO-Handle-Text.html#line-820 Cheers! =) -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[haskell-cafe] How to substitute FD like a - b c by type families?
I'm trying to implement the Advanced Example : Type-Level Quicksort from HaskellWiki using type families instead of functional dependencies. My code is at [1]. I substituted all 'many to one' functional dependencies like xs ys - zs by explicit type families, but I don't know how to replace 'many to many' dependencies by type families only, so I've used associated types. But for some unknown to me reason the typechecker hangs if I try to get listQuickSort type signature in ghci. So I have 2 questions: what is the correct replacement of FDs in this case and where is an error in my code? I assume that the correct replacement exists (though it may not be very pretty) because type families and functional dependencies are equivalent in expressiveness [2]. Regards, Vladimir [1] http://hpaste.org/fastcgi/hpaste.fcgi/view?id=29380#a29380 [2] http://www.mail-archive.com/haskell-cafe@haskell.org/msg54024.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Re: ANNOUNCE: enumerator, an alternative iteratee package
On 23/08/2010 12:57, Felipe Lessa wrote: On Mon, Aug 23, 2010 at 8:51 AM, Simon Marlowmarlo...@gmail.com wrote: Hmm, RawIO.read looks ok: -- | Read up to the specified number of bytes, returning the number -- of bytes actually read. This function should only block if there -- is no data available. If there is not enough data available, -- then the function should just return the available data. A return -- value of zero indicates that the end of the data stream (e.g. end -- of file) has been reached. that seems pretty clear to me. No? It says that it should only block if there is no data available. I assumed that fillReadBuffer has the same semantics. If both do not block if there is data, then hGetBuf would not wait for the buffer to be filled, if I am reading its source correctly [1]. Either they do block until the buffer is filled, or I'm misreading hGetBuf/bufRead. =) I think it's the latter. bufRead loops until it has read the full amount of data requested, or EOF is reached. Cheers, Simon [1] http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/GHC-IO-Handle-Text.html#line-820 Cheers! =) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compiling UHC
Hi Henk-Jan, On Mon, Aug 23, 2010 at 00:15, Henk-Jan van Tuyl hjgt...@chello.nl wrote: L.S., I am trying to compile the current release of UHC (1.0.1); I started with the installation of the most recent version of uulib and uuagc. When running make uhc I received the following message: EH\Util\CompileRun.hs:46:7: Could not find module `UU.DData.Scc': Use -v to see a list of the files searched for. This module is not in the most recent version of uulib, so I installed uulib-0.9.10, but then I received the message: EH\Util\CompileRun.hs:46:7: Could not find module `UU.DData.Scc': It is a member of the hidden package `uulib-0.9.10'. Use -v to see a list of the files searched for. What can I do to get UHC compiled? Yes, I think you really have to use uulib-0.9.10 for the latest released version. Another alternative would be to checkout the HEAD. But if you don't want that, then uninstall uulib-0.9.12 (ghc-pkg unregister uulib-0.9.12) first; GHC should then use uulib-0.9.10 automatically. Cheers, Pedro (I am using Haskell Platform 2010.2.0.0) Regards, Henk-Jan van Tuyl -- http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html -- ___ 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] Re: Unix emulation
On Mon, Aug 23, 2010 at 12:36:18AM -0700, Kevin Jardine wrote: In the past, installing it has only taken a few minutes. That still looks to be the case for MinGW but it now appears that msys has been split into a confusing and long list of packages. I think that it needs a standard installer as well (in fact the combined MinGW/msys package needs one standard installer as I think it is rare these days to use one without the other.) When I need a msys+mingw environment, I tend to turn to msysgit's netinstall package. The only downside to it that I've noticed is that you seem to get a git source tree for free when installing, as well as a spurious sdl-config binary. http://code.google.com/p/msysgit/ -- Lars Viklund | z...@acc.umu.se ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
Luke Palmer wrote: Heinrich Apfelmus wrote: Conal Elliott wrote: For anyone interested in iteratees (etc) and not yet on the iteratees mailing list. I'm asking about what iteratees *mean* (denote), independent of the various implementations. In my world view, iteratees are just a monad M with a single operation symbol :: M Char that reads the next symbol from an input stream. So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) = MaybeT (State [Char]) a symbol [] = Nothing symbol (c:cs) = Just (c, cs) I'm not experienced with iteratees. Does this miss something? From a purely denotational point of view, that's a reasonable semantics. However, and that's the main point, with this particular semantics, it is impossible to implement runHandle :: M a - Handle - IO a without using unsafeInterleaveIO . Typical implementations of iteratees do make that possible, by being able to suspend the iteratee after feeding it a character. There are also enumerators and enumeratees. I think that purpose of enumerator = run an iteratee on multiple sources (i.e. first part of the input from a Handle , second part from a String ) purpose of enumeratee = iteratee as a stream transformer, i.e. as a map [x] - [y] I am not sure whether this elaborate reinvention of the standard lists functions is worth the trouble. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Re: ANNOUNCE: enumerator, an alternative iteratee package
On Mon, Aug 23, 2010 at 9:00 AM, Simon Marlow marlo...@gmail.com wrote: I think it's the latter. bufRead loops until it has read the full amount of data requested, or EOF is reached. Hmmm... sorry about the noise then =). Cheers, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
On Mon, 23 Aug 2010 14:38:29 +0200, Heinrich Apfelmus apfel...@quantentunnel.de wrote: Luke Palmer wrote: Heinrich Apfelmus wrote: Conal Elliott wrote: For anyone interested in iteratees (etc) and not yet on the iteratees mailing list. I'm asking about what iteratees *mean* (denote), independent of the various implementations. In my world view, iteratees are just a monad M with a single operation symbol :: M Char that reads the next symbol from an input stream. So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) = MaybeT (State [Char]) a symbol [] = Nothing symbol (c:cs) = Just (c, cs) I'm not experienced with iteratees. Does this miss something? From a purely denotational point of view, that's a reasonable semantics. However, and that's the main point, with this particular semantics, it is impossible to implement runHandle :: M a - Handle - IO a without using unsafeInterleaveIO . Typical implementations of iteratees do make that possible, by being able to suspend the iteratee after feeding it a character. There are also enumerators and enumeratees. I think that purpose of enumerator = run an iteratee on multiple sources (i.e. first part of the input from a Handle , second part from a String ) I would say more simply that an enumerator is a data-producer (or source). Although it is a producer defined as a consummer (or sink) feeder. An iteratee is thus the consummer. It is defined as an action asking either for more food or producing a value and a food left over -- ignoring errors and over-simplifing Stream as Maybe data Step a b = Continue (Maybe a - IO (Step a b)) | Yield b (Maybe a) type Iteratee a b = IO (Step a b) -- the most important case is when getting Continue as input: -- type Enumerator a b = (Maybe a - IO (Step a b)) - IO (Step a b) type Enumerator a b = Step a b - IO (Step a b) Note that I'm far from an expert on Iteratee but I start to get some intuitions out of it. -- Nicolas Pouillard http://nicolaspouillard.fr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Higher-order algorithms
Most of the well-known algorithms are first-order, in the sense that their input and output are plain data. Some are second-order in a trivial way, for example sorting, hashtables or the map and fold functions: they are parameterized by a function, but they don't really do anything interesting with it except invoke it on pieces of other input data. Some are also second-order but somewhat more interesting: * Fingertrees parameterized by monoids * Splitting a fingertree on a monotonous predicate * Prefix sum algorithms, again usually parameterized by a monoid or a predicate etc. Finally, some are truly higher-order in the sense that is most interesting to me: * The Y combinator * Difference lists Do there exist other nontrivial higher-order algorithms and datastructures? Is the field of higher-order algorithms indeed as unexplored as it seems? I mean that not only higher-order facilities are used, but the essence of the algorithm is some non-trivial higher-order manipulation. For example, parser combinators are not so interesting: they are a bunch of relatively orthogonal (by their purpose) combinators, each of which is by itself quite trivial, plus not-quite-higher-order backtracking at the core. For example, for the Y combinator and difference lists are interesting: the Y combinator builds a function from a function in a highly non-trivial way; difference lists are a data structure built entirely from functions and manipulated using higher-order mechanisms. -- Eugene Kirpichov Senior Software Engineer, Grid Dynamics http://www.griddynamics.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Higher-order algorithms
2010/8/23 Eugene Kirpichov ekirpic...@gmail.com: [snip] Do there exist other nontrivial higher-order algorithms and datastructures? Is the field of higher-order algorithms indeed as unexplored as it seems? [snip] Hi, I'm thinking to some HOAS (higher order abstract syntax) representation. Cheers, Thu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Higher-order algorithms
2010/8/23 Eugene Kirpichov ekirpic...@gmail.com: For example, parser combinators are not so interesting: they are a bunch of relatively orthogonal (by their purpose) combinators, each of which is by itself quite trivial, plus not-quite-higher-order backtracking at the core. This is only if you're not quite considering generalizing parser combinators to non-backtracking algorithms. The CYK algorithm [1] does not backtrack, it merges partial parsing results. When I thought about it I figured that parser combinators became even more restricted that they in arrow parsers. [1] http://en.wikipedia.org/wiki/CYK_algorithm PS CYK is interesting because it provides parallel parsing opportunities, it can parse many parts of text in parallel and then merge bags of successful parsings into another successful parsings. As CYK does not care about start of sequence it was used to parse grammars on hypergraphs: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.6425 PPS I didn't thought fully about CYK parser combinators yet. But I think that CYK could be an example of something unusual in the accustomed field of parsing. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fast Integer Input
I need a function which has fast conversion from Bytestring to Integer. I am currently using this: import qualified Data.ByteString.Lazy.Char8 as BS readInteger :: BS.ByteString - Integer readInteger x = case BS.readInteger x of Just (i,_) - i Are there faster implementations? This function takes 1.8 seconds to convert 2000 integers of length 10^13000. I need it to be smaller that 0.5 sec. Is it possible? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fast Integer Input
2010/8/23 200901...@daiict.ac.in: This function takes 1.8 seconds to convert 2000 integers of length 10^13000. I need it to be smaller that 0.5 sec. Is it possible? 2000 integers of magnitude 10^13000 equals to about 26 MBytes of data (2000 numbers each 13000 digits long). Rounding 1.8 seconds to two seconds we conclude that you proceed with speed about 13MBytes per second. Assuming you have CPU clock frequency near 2.6GHz, you performing about 200 clock cycles per input digit. 10^13000 roughly equal to 2^39000. Or (2^32)^1219 - 1219 32-bit words of representation. So you're doing some last nextN = (n*10)+currentDigit conversion operations in less that one clock cycle per word. Either I err'd in my math, or you're performing better than most of us could expect. Maybe you are off in your 10^13000 by an order of magnitude. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fast Integer Input
Does the length of those numbers happen to be fixed? It they are all exactly 13000 decimals then it should be possible to create a more optimised parser. Well actually they can have any number of digits less than 13000. But the only post processing of the numbers is calculating the binary logarithm of the number. Does that help? It would also help if you could post a working example of your code and some test data somewhere so people can run it and test if for themselves. I have a slow Internet connection. So I will attach the script I used to generate the cases instead.(Note: It will take a few minutes to complete)# -*- coding: utf-8 -*- import random fibs = [0]*60001 fibs[1] = 1 for i in xrange(2, 60001): fibs[i] = fibs[i-1] + fibs[i-2] for _ in xrange(2000): i = random.randint(58000, 6) print fibs[i] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: enumerator, an alternative iteratee package
On Mon, Aug 23, 2010 at 6:16 AM, John Lato jwl...@gmail.com wrote: It's not necessary to understand CPS to use CPS-based iteratees. The CPS implementation generally simplifies the types and removes the necessity for special combinators like ($$) and (==), so I strongly suspect newcomers will find it easier to use than other variants (although unfortunately I can no longer say this from personal experience). It incorporates the best features of Oleg's two implementations in IterateeM.hs. The only drawback is the added thought overhead of CPS, but users need not be aware of this for the most part. I agree with you, John. Personally, I find the CPS version easier to use, that's why I asked. But since people have different styles, I guess it's not a bad thing that the two packages use a different implementation. When I was reimplementing Iteratees I also didn't find any noticeable slowdown with CPS, but my benchmarks were very simple -- unlike yours. You are comparing the darcs branch to the version on Hackage, right? Paulo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] empty .prof file
Hi, I'd like to profile a GLUT application. After a run of the application with the +RTS -p flag, the .prof file is actually created but is always empty. Does someone have a clue of what's going on? Would it be related to my application calling GLUT's leaveMainLoop to exit? Thanks, Thu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fast Integer Input
Serguey Zefirov wrote: 2010/8/23 200901...@daiict.ac.in: This function takes 1.8 seconds to convert 2000 integers of length 10^13000. I need it to be smaller that 0.5 sec. Is it possible? 2000 integers of magnitude 10^13000 equals to about 26 MBytes of data (2000 numbers each 13000 digits long). Rounding 1.8 seconds to two seconds we conclude that you proceed with speed about 13MBytes per second. Assuming you have CPU clock frequency near 2.6GHz, you performing about 200 clock cycles per input digit. 10^13000 roughly equal to 2^39000. Or (2^32)^1219 - 1219 32-bit words of representation. So you're doing some last nextN = (n*10)+currentDigit conversion operations in less that one clock cycle per word. You can do better than calculating (n*10 + d) repeatedly, using a divide and conquer scheme, which is in fact implemented in ByteString's readInteger: ((a*10 + b) * 100 + (c*10 + d)) * 1 + ... This helps because now we're multiplying numbers of roughly equal size, which using FFT and related methods, as gmp uses, can be sped up immensely, beating the quadratic complexity that you get with the naive approach. The timings seem about right. HTH, Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: empty .prof file
2010/8/23 Vo Minh Thu not...@gmail.com: Hi, I'd like to profile a GLUT application. After a run of the application with the +RTS -p flag, the .prof file is actually created but is always empty. Does someone have a clue of what's going on? Would it be related to my application calling GLUT's leaveMainLoop to exit? Yes, the problem is the default behavior of leaveMainLoop. Setting actionOnWindowClose $= MainLoopReturns does the trick. Cheers, Thu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Second Call for Copy: Monad.Reader Issue 17
Whether you're an established academic or have only just started learning Haskell, if you have something to say, please consider writing an article for The Monad.Reader! The submission deadline for Issue 17 is **Friday, October 1, 2010** That's little more than a month away! Get started on your article now! =) The Monad.Reader The Monad.Reader is a electronic magazine about all things Haskell. It is less formal than journal, but somehow more enduring than a wiki- page. There have been a wide variety of articles: exciting code fragments, intriguing puzzles, book reviews, tutorials, and even half-baked research ideas. Submission Details ~~ Get in touch with me if you intend to submit something -- the sooner you let me know what you're up to, the better. Please submit articles for the next issue to me by e-mail (byorgey at cis.upenn.edu). Articles should be written according to the guidelines available from http://themonadreader.wordpress.com/contributing/ Please submit your article in PDF, together with any source files you used. The sources will be released together with the magazine under a BSD license. If you would like to submit an article, but have trouble with LaTeX please let me know and we'll work something out. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fast Integer Input
2010/8/23 Bertram Felgenhauer bertram.felgenha...@googlemail.com: Serguey Zefirov wrote: The timings seem about right. Thank you for letting me know about divide-and-conquer variant. But I am still amuzed that producing 1200 words of data from 13Kbytes of text took those little 200 cycles of CPU. This is quite interesting and I think I should investigate that later. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Higher-order algorithms
(Accidentally sent off-list, resending) On Mon, Aug 23, 2010 at 15:03, Eugene Kirpichov ekirpic...@gmail.com wrote: * Difference lists I mean that not only higher-order facilities are used, but the essence of the algorithm is some non-trivial higher-order manipulation. If I'm not mistaken, we can defunctionalize difference lists like this: data DList a = Chunk [a] | Concat (DList a) (DList a) fromList = Chunk () = Concat singleton = Chunk . (:[]) empty = Chunk [] toList dl = dl `fold` [] where infixr `fold` fold :: DList a - [a] - [a] fold (Concat l r) ys = l `fold` r `fold` ys fold (Chunk xs) ys = xs ++ ys (This implementation has only been lightly tested) And of course, we knew this was possible, since we can compile DLists to first-order machines. I agree that the functional, higher-order presentation is clear and elegant. But is it essential? Also, I'm curious about how this performs relative to the functional version. --Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Crypto-API is stabilizing
All, Crypto-API - a unified interface to which I hope hash and cipher algorithms will adhere - has recently gotten a reasonable amount of polish work. I continue to welcome all comments! A blog on its current interface is online [1] as are darcs repositories of the crypto-api package [2]. Recent changes includes added block cipher modes, platform-independent RNG, tests, a simplistic benchmark framework, and minor tweaks of the classes. I've made experimental hash, block cipher and stream cipher instances. Almost no optimizations have been made as of yet! Thanks to everyone for their past comments! I have made numerous changes based on input received. If you feel I didn't respond properly to your suggestion then please ping me again - this is purely a spare time effort and things do fall through the cracks. Cheers, Thomas [1] http://tommd.wordpress.com/2010/08/23/a-haskell-api-for-cryptographic-algorithms/ [2] http://community.haskell.org/~tommd/crypto/ (If you're wondering why you're BCCed its probably because you worked on a crypto-related Haskell package) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Changing my Profile
Is there any way to change my profile or signup options so that I don't get CC'ed on every posting to Haskell-Cafe? David ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Changing my Profile
I don't know about doing it at the server side. I've been trying to setup the right filters and quick links in my GMail to filter out emails I'm not interested. I'd like to recieve *all* emails, but be able to filter out the ones I'm not interested in so I never see them again. I tried an Uninteresting (for my taste) tag and then searching by -label:uninteresting. This kinda works, but it's unpredictable. It will filter out some conversations, but it seems not to filter out others labelled Uninteresting. If I open the offending conversation and unlabel it, then label it Uninteresting again, and then go back to my search results, and refresh, it goes from the list. But having to do it manually kind of defies the point. I don't want to have to deal with messages I'm not competent to understand nor/or interested to bother to read. Any suggestions would be appreciated. On 23 August 2010 19:35, David Webster dwwebste...@gmail.com wrote: Is there any way to change my profile or signup options so that I don't get CC'ed on every posting to Haskell-Cafe? David ___ 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] ANNOUNCE: enumerator, an alternative iteratee package
On Mon, Aug 23, 2010 at 4:24 PM, Paulo Tanimoto ptanim...@gmail.com wrote: On Mon, Aug 23, 2010 at 6:16 AM, John Lato jwl...@gmail.com wrote: It's not necessary to understand CPS to use CPS-based iteratees. The CPS implementation generally simplifies the types and removes the necessity for special combinators like ($$) and (==), so I strongly suspect newcomers will find it easier to use than other variants (although unfortunately I can no longer say this from personal experience). It incorporates the best features of Oleg's two implementations in IterateeM.hs. The only drawback is the added thought overhead of CPS, but users need not be aware of this for the most part. I agree with you, John. Personally, I find the CPS version easier to use, that's why I asked. But since people have different styles, I guess it's not a bad thing that the two packages use a different implementation. When I was reimplementing Iteratees I also didn't find any noticeable slowdown with CPS, but my benchmarks were very simple -- unlike yours. You are comparing the darcs branch to the version on Hackage, right? I'm actually referring to benchmarks from about 10-8 months ago. I did have them on the website, but it looks like I took them down. I haven't run any comparisons recently, except for a few to determine where INLINEs are beneficial. I'll make a current set and post them when they're ready. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: darcs 2.5 beta 4
The darcs team would like to announce the immediate availability of darcs 2.5 beta 4 (also known as darcs 2.4.98.4 due to Cabal restrictions). Important changes since darcs 2.4.4 are: * trackdown can now do binary search with the --bisect option * darcs always stores patch metadata encoded with UTF-8 * diff now supports the --index option * amend-record now supports the --ask-deps option * apply now supports the --match option * amend-record has a new --keep-date option * inventory-changing commands (like record and pull) now operate in constant time with respect to the number of patches in the repository * the push, pull, send and fetch commands no longer set the default repository by default * the --edit-description option is now on by default for the send command Changes since the last beta release are: * Fix issue 1898: warn users about changes to command line flag defaults * Fix issue 1913: sort changes in treeDiff (fixes failure in record) * Fix issue 1815: make the tarball with the right permissions If you have installed the Haskell Platform or cabal-install, you can install this beta release by doing: $ cabal update $ cabal install darcs-beta Alternatively, you can download the tarball from http://darcs.net/releases/darcs-2.4.98.4.tar.gz and build it by hand as explained in the README file. Kind Regards, the darcs release manager, Reinier Lamers 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] ANNOUNCE: ipatch, the interactive patch editor
On Tue, Aug 3, 2010 at 3:52 PM, Joachim Breitner m...@joachim-breitner.de wrote: Dear Haskell and Darcs community, I have written a tool to interactively edit patches, which under the hood uses the Darcs API. A more catchy introduction, including a screencast, can be found on https://www.joachim-breitner.de/blog/archives/425-ipatch,-the-interactive-patch-editor.html which ends (and this is where you come in) with „So this is an invitation to join me and make ipatch a great tool. This invitation goes especially to the Darcs developers: Please have a look how the code uses the Darcs API and help to improve the collaboration here. I think we can use the darcs-users mailing list until there is need for a dedicated mailing list.“ The code is on http://darcs.nomeata.de/ipatch/. Enjoy! Joachim Do you have any documentation on what this utility does? I don't quite understand what I would use it for. What limitations does it have on the patch formats I can use with it? Thanks, Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Function signatures and type class constraints
Hi,
I'm wondering why I have to repeat the class constraints at every function.
If I got the data type
data (Eq a, Show a, Data a, Eq b, Show b, Data b, Eq c, Show c, Data c) =
Foo a b c = Foo a b c
and then a function from Foo to String I have to supply the signature
bar :: (Eq a, Show a, Data a, Eq b, Show b, Data b, Eq c, Show c, Data c) =
Foo a b c - String
even though it should be clear that a, b and c *must* fulfill the
constraints already so I should be able to just supply the signature
bar :: Foo a b c - String
Another related problem I got is that even though I can create the type
type B = (Eq a, Show a, Data a, Eq b, Show b, Data b, Eq c, Show c, Data c)
= Foo a b c
I cannot use it like
bar :: B - String
so my type class constraints got a tendency become huge!
It is possible to work around this somehow? I'm in a situation at the
moment where I got a data type with four fields each with three
constraints (Show, Eq, Data), so I have to repeat 12 constraints at
every function signature... :(
Finally is there some way to bundle type class constraints, something like
data {Eq, Show, Data} {a, b, c} = Foo a b c = Foo a b c -- make believe
syntax
so I don't have to repeat every constraint and variable all the time?
-- Oscar
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: ipatch, the interactive patch editor
Hi, Am Montag, den 23.08.2010, 15:10 -0500 schrieb Antoine Latter: On Tue, Aug 3, 2010 at 3:52 PM, Joachim Breitner m...@joachim-breitner.de wrote: Dear Haskell and Darcs community, I have written a tool to interactively edit patches, which under the hood uses the Darcs API. A more catchy introduction, including a screencast, can be found on https://www.joachim-breitner.de/blog/archives/425-ipatch,-the-interactive-patch-editor.html which ends (and this is where you come in) with „So this is an invitation to join me and make ipatch a great tool. This invitation goes especially to the Darcs developers: Please have a look how the code uses the Darcs API and help to improve the collaboration here. I think we can use the darcs-users mailing list until there is need for a dedicated mailing list.“ The code is on http://darcs.nomeata.de/ipatch/. Do you have any documentation on what this utility does? I don't quite understand what I would use it for. What limitations does it have on the patch formats I can use with it? The help output of the commands might be enlighting: === $ ipatch ipatch version 0.1 Usage: ipatch COMMAND ... Commands: help Display help about ipatch and ipatch commands. Changing files apply Apply a diff file interactively. Changing patches split Split a diff file interactively. Use 'ipatch COMMAND --help' for help on a single command. Use 'ipatch --version' to see the ipatch version number. === $ ipatch split --help Usage: darcs split [OPTION]... PATCHFILE Split a diff file interactively. Options: --disable disable this command -h --helpshows brief description of command and its arguments Advanced options: [..] The `ipatch split file.patch' lets the user select different parts (hunks) of the given patch file. After making a choice for each hunk, the user has to provide a file name where the selected changes are stored. This procedure is repeated until each change in the original file has been selected for one output file. No files are modified by this command. The output patch files are all written at the of the process. === $ ./dist/build/ipatch/ipatch apply --help Usage: darcs apply [OPTION]... PATCHFILE Apply a diff file interactively. Options: --disable disable this command -h --helpshows brief description of command and its arguments Advanced options: [..] The `ipatch apply file.patch' command works similar to a `patch file.patch' command. It will, however, prompt the user about each part of the patch, whether it should be applied or not. Using the integrated hunk editor, the user has full control over the chosen changes. No files are touched until the end, when the user is asked for a final confirmation. === I’m not particular sure if apply is helpful. Maybe mostly to review a patch hunk-for-hunk before applying and doing minor fix-ups (using the hunk editor) directly there. The main feature is the split command. My motivation comes from maintaining Debian package where dpkg-buildpackage generates one large patch from your changes to the upstream sources which I might want to store separately, maybe because it contains independent changes. For this, I plan some integration into quilt, e.g. add a mode that splits the next patch in the series and puts the generated patches into the series file. I don’t think it is of much use if you are already using a VCS to maintain your changes. Although having a split command in git rebase -i that uses ipatch to split a change could be nice. The limitations on the patch files are that they have to be parseable by diffstat (to obtain the list of changed files) and that they need to apply cleanly to the current directory using patch. Unclean patches, already applied patches or patches that require different -p options are not supported yet, but will eventually. Greetings, Joachim -- Joachim nomeata Breitner mail: m...@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nome...@joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nome...@debian.org 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] ANNOUNCE: ipatch, the interactive patch editor
On Mon, Aug 23, 2010 at 1:32 PM, Joachim Breitner m...@joachim-breitner.dewrote: $ ipatch split --help Usage: darcs split [OPTION]... PATCHFILE Darcs? $ ./dist/build/ipatch/ipatch apply --help Usage: darcs apply [OPTION]... PATCHFILE Darcs? I assume those are typos left over from borrowing code? Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: ipatch, the interactive patch editor
Hi, Am Montag, den 23.08.2010, 13:43 -0700 schrieb Jason Dagit: On Mon, Aug 23, 2010 at 1:32 PM, Joachim Breitner m...@joachim-breitner.de wrote: $ ipatch split --help Usage: darcs split [OPTION]... PATCHFILE Darcs? $ ./dist/build/ipatch/ipatch apply --help Usage: darcs apply [OPTION]... PATCHFILE Darcs? I assume those are typos left over from borrowing code? actually I’m not borrowing the code, I’m using the Darcs API, including the Help and Command infrastructure, which is not fully generalized yet. I need to have a look at the Darcs code and think of the best way of making it more configurable, without changing it too much or making it harder for Darcs itself. The function in question is getCommandHelpCore in Darcs.Commands. Maybe the name of the executable could be placed in the 'Command' record, then it would be available everywhere where needed. If someone from the Darcs team wants to help here, that would of course be appreciated. Greetings, Joachim -- Joachim nomeata Breitner mail: m...@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nome...@joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nome...@debian.org 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] ANNOUNCE: ipatch, the interactive patch editor
This would benifit darcs, as the help-text would be correct even if I've renamed the executable. For example darcs-beta vs. darcs. On Aug 23, 2010 3:49 PM, Joachim Breitner m...@joachim-breitner.de wrote: Hi, Am Montag, den 23.08.2010, 13:43 -0700 schrieb Jason Dagit: On Mon, Aug 23, 2010 at 1:32 PM, Joachim Breitner m...@joachim-breitner.de wrote: $ ipatch split --help Usage: darcs split [OPTION]... PATCHFILE Darcs? $ ./dist/build/ipatch/ipatch apply --help Usage: darcs apply [OPTION]... PATCHFILE Darcs? I assume those are typos left over from borrowing code? actually I’m not borrowing the code, I’m using the Darcs API, including the Help and Command infrastructure, which is not fully generalized yet. I need to have a look at the Darcs code and think of the best way of making it more configurable, without changing it too much or making it harder for Darcs itself. The function in question is getCommandHelpCore in Darcs.Commands. Maybe the name of the executable could be placed in the 'Command' record, then it would be available everywhere where needed. If someone from the Darcs team wants to help here, that would of course be appreciated. Greetings, Joachim -- Joachim nomeata Breitner mail: m...@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nome...@joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nome...@debian.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Function signatures and type class constraints
On Monday 23 August 2010 22:30:03, Oscar Finnsson wrote:
Hi,
I'm wondering why I have to repeat the class constraints at every
function.
If I got the data type
data (Eq a, Show a, Data a, Eq b, Show b, Data b, Eq c, Show c, Data
c) = Foo a b c = Foo a b c
Type class constraints on datatypes are considered a wart. They don't do
what people expect, in particular they don't make the constraints available
at the use site.
It works if you move the constraints across the '=':
{-# LANGUAGE ExistentialQuantification #-}
data Foo a b c = (Eq a, Show a, ...) = Foo a b c
or with GADT syntax:
{-# LANGUAGE GADTs #-}
data Foo x y z where
Foo :: (Eq a, Show a, ...) = a - b - c - Foo a b c
Both make the constraints available at the use site,
bar :: Foo a b c - String
bar (Foo a b c)
= Foo ++ show a ++ ++ show b ++ ++ show c ++ , Yay!
and then a function from Foo to String I have to supply the signature
bar :: (Eq a, Show a, Data a, Eq b, Show b, Data b, Eq c, Show c, Data
c) = Foo a b c - String
even though it should be clear that a, b and c *must* fulfill the
constraints already so I should be able to just supply the signature
One would think so. It's a wart.
bar :: Foo a b c - String
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Changing my Profile
On the bottom of this page, enter your e-mail address: http://www.haskell.org/mailman/listinfo/haskell-cafe http://www.haskell.org/mailman/listinfo/haskell-cafeThis is also provided in the footer of these list e-mails. On Mon, Aug 23, 2010 at 1:35 PM, David Webster dwwebste...@gmail.comwrote: Is there any way to change my profile or signup options so that I don't get CC'ed on every posting to Haskell-Cafe? David ___ 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] Re: Filename encoding error (was: Perform a research a la Unix 'find')
I've been banging my head on the same issues. To summarise: GHC 6.12 strings are unicode; unix file paths are slightly restricted byte strings; the former is used to represent the latter, leading to great confusion; the best way to fix it is unclear. Here's a workaround I wrote this morning: -- | A platform string is a string value from or for the operating system, -- such as a file path or command-line argument (or environment variable's -- name or value ?). On some platforms (such as unix) these are not real -- unicode strings but have some encoding such as UTF-8. This alias does -- no type enforcement but aids code clarity. type PlatformString = String -- | Convert a possibly encoded platform string to a real unicode string. -- We decode the UTF-8 encoding recommended for unix systems -- (cf http://www.dwheeler.com/essays/fixing-unix-linux-filenames.html) -- and leave anything else unchanged. fromPlatformString :: PlatformString - String fromPlatformString s = if UTF8.isUTF8Encoded s then UTF8.decodeString s else s -- | Convert a unicode string to a possibly encoded platform string. -- On unix we encode with the recommended UTF-8 -- (cf http://www.dwheeler.com/essays/fixing-unix-linux-filenames.html) -- and elsewhere we leave it unchanged. toPlatformString :: String - PlatformString toPlatformString = case os of unix - UTF8.encodeString linux - UTF8.encodeString darwin - UTF8.encodeString _ - id ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] feasability of implementing an awk interpreter.
On Aug 23, 2010, at 7:00 PM, Roel van Dijk wrote:
On Mon, Aug 23, 2010 at 8:07 AM, Richard O'Keefe o...@cs.otago.ac.nz wrote:
But what _is_ the core functionality.
The Single Unix Specification can be browsed on-line.
There is no part of it labelled core; it's all required
or it isn't AWK.
[If -f progfile is specified, the application shall ensure that the
files named by each of the progfile option-arguments are text files
and their concatenation, in the same order as they appear in the
arguments, is an awk program.
] is what I was referring to.
Is that core? Who knows?
I say that that behaviour is not part of the language but of the runtime.
Actually, it's a *compile*-time thing.
Whatever the core functionality might be, YOU will have to define
what that core is. There's no standard, or even common, sublanguage.
One approach to find the core of a language is to find which parts can
be implemented in terms of other parts. If part B can be expressed in
terms of part A then B doesn't belong in the core.
Agreed. But it's not clear that AWK *has* a non-trivial core in that
sense. OK, so you can define != in terms of == and ,=,= in terms
of , and you can define + and unary - in terms of infix -. And you
can define (a,b,c,...) as (a SUBSEP b SUBSEP c SUBSEP ...). But you
can't, for example, define
print number
in terms of
print (number )
because number printing and number to string printing use different
format variables (OFMT and CONVFMT respectively), and you can't
define the two of them in terms of sprintf() because there is no
way for an AWK program to _test_ whether a value is a number or a
string or an uninitialized value (which has defined properties) or
an uncommitted numeric string.
What you would have to do would be to define an *extended* 'core'
containing
case(E; U, x.I, x.F, x.UI, x.UF, x.S)
U - what to do for uninitialized value
x.I - what to do for an integral value
x.F - what to do for a non-integral number
x.UI - what to do for a uncommitted maybe-integer-maybe-string
x.UF - what to do for an uncommitted maybe-float-maybe-string
x.S - what to do for a string
That is, the core you need contains operations that are NOT in the
source language.
Here's one of my favourite quotations from the Single Unix Specification
V3 description of AWK:
For example, with historical implementations the following program:
{
a = +2
b = 2
if (NR % 2)
c = a + b
if (a == b)
print numeric comparison
else
print string comparison
}
would perform a numeric comparison (and output numeric comparison)
for each odd-numbered line, but perform a string comparison (and
output string comparison) for each even-numbered line. IEEE Std 1003.1-2001
ensures that comparisons will be numeric if necessary.
I just tried four AWK implementations.
GNU AWK and Mike's AWK both wrote
string comparison
string comparison
string comparison
string comparison
as required by the standard. But two others (one provided by a major
UNIX vendor, and the other provided by one of the inventors of AWK)
did indeed write
numeric comparison
string comparison
numeric comparison
string comparison
Now let's make an apparently tiny change to the program.
Let's replace
a = +2
by
a = ENVIRON[FOO]
and do
setenv FOO +2
in the shell. Now all four implementations print
numeric comparison
four times.
Getting this right is not just a tiny tweak to the system,
it's a fundamental issue that affects the way you represent
AWK 'values' in your interpreter.
Then there are the undefined things.
Consider
BEGIN {
echo = echo
n = getline echo
print n | echo
close(echo)
...
}
The third line opens an input stream reading from a file called
echo. The fourth line opens an output stream writing to a
pipe running the echo command.
What does the fifth line close?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] ANNOUNCE: enumerator, an alternative iteratee package
After fielding some more questions regarding error handling, it turns out that my earlier mail was in error (hah) -- error handling is much more complicated than I thought. When I gave each iteratee its own error type, I was expecting that each pipeline would have only one or two sources of errors -- for example. a parser, or a file reader. However, in reality, it's likely that every single element in a pipeline can produce an error. For example, in a JSON/XML/etc reformatter (enumFile, parseEvents, formatEvents, iterFile), errors could be SomeException, ParseError, or FormatError. Futhermore, while it's easy to change an iteratee's error type with just (e1 - e2), changing an enumerator or enumeratee *also* requires (e2 - e1). In other words, to avoid loss of error information, the two types have to be basically the same thing anyway. I would like to avoid hard-coding the error type to SomeException, because it forces libraries to use unsafe/unportable language features (dynamic typing and casting). However, given the apparent practical requirement that all iteratees have the same error type, it seems like there's no other choice. So, my questions: 1. Has anybody here successfully created / used / heard of an iteratee implementation with independent error types? 2. Do alternative Haskell implementations (JHC, UHC, Hugs, etc) support DeriveDataTypeable? If not, is there any more portable way to define exceptions? 3. Has anybody actually written any libraries which use the existing enumerator error handling API? I don't mind rewriting my own uploads, since this whole mess is my own damn fault, but I don't want to inconvenience anybody else. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] ANNOUNCE: enumerator, an alternative iteratee package
It's not released yet, but persistent 0.2 is going to be using enumerator. I personally don't mind SomeException as a hard-coded error type, but go ahead and do whatever you think is best for the API. Michael On Tue, Aug 24, 2010 at 5:47 AM, John Millikin jmilli...@gmail.com wrote: After fielding some more questions regarding error handling, it turns out that my earlier mail was in error (hah) -- error handling is much more complicated than I thought. When I gave each iteratee its own error type, I was expecting that each pipeline would have only one or two sources of errors -- for example. a parser, or a file reader. However, in reality, it's likely that every single element in a pipeline can produce an error. For example, in a JSON/XML/etc reformatter (enumFile, parseEvents, formatEvents, iterFile), errors could be SomeException, ParseError, or FormatError. Futhermore, while it's easy to change an iteratee's error type with just (e1 - e2), changing an enumerator or enumeratee *also* requires (e2 - e1). In other words, to avoid loss of error information, the two types have to be basically the same thing anyway. I would like to avoid hard-coding the error type to SomeException, because it forces libraries to use unsafe/unportable language features (dynamic typing and casting). However, given the apparent practical requirement that all iteratees have the same error type, it seems like there's no other choice. So, my questions: 1. Has anybody here successfully created / used / heard of an iteratee implementation with independent error types? 2. Do alternative Haskell implementations (JHC, UHC, Hugs, etc) support DeriveDataTypeable? If not, is there any more portable way to define exceptions? 3. Has anybody actually written any libraries which use the existing enumerator error handling API? I don't mind rewriting my own uploads, since this whole mess is my own damn fault, but I don't want to inconvenience anybody else. ___ 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] Fwd: Semantics of iteratees, enumerators, enumeratees?
Conal Elliott wrote: For anyone interested in iteratees (etc) and not yet on the iteratees mailing list. I'm asking about what iteratees *mean* (denote), independent of the various implementations. My original note (also at the end below): With the encouragement help of Conrad Parker, I've been looking at iteratees, enumerators, enumeratees. I can find plenty written about them, but only about benefits and implementation. In sifting through chunks, error/control messages, and continuations, I find myself longing for a precise semantic basis. I keep wondering: what simpler precise semantic notions do these mechanisms implement? Has anyone worked out a denotational semantics for iteratees, enumerators, enumeratees -- something that simplifies away the performance advantages complexities? I've worked out something tentative, but perhaps I'm covering old ground. I believe the denotation of an iteratee is the transition function for an automaton (or rather a transducer). I hesitate to speculate on the specific kind of automaton without thinking about it, so maybe finite, maybe deterministic, but then again maybe not. The core idea of iteratees vs conventional parsing strikes me as the same as the build/foldr vs unfoldr/destroy dichotomy. That is, ultimately we have a non-recursive producer, a non-recursive consumer, and a recursive driver. In build/foldr the producer is flat and we factor the recursion into the consumer; whereas in unfoldr/destroy we factor the recursion into the producer and the consumer is flat. Thus, I think iteratees are just the (non-recursive) transition function. The recursion for applying the transition function is done elsewhere, namely in the data/driver. Whereas in conventional parsing, the parser contains both the transition function and the recursion for driving the automaton until it hits an accepting/error state, and the data is just a flat stream. This is why conventional parsers don't have a Partial/More constructor: they don't expose the intermediate states of the automaton. Since iteratees only take a single step before returning, they do expose those intermediate states and so they need to have a constructor for them. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [haskell-cafe] How to substitute FD like a - b c by type families?
Vladimir Matveev wrote: I'm trying to implement the Advanced Example : Type-Level Quicksort from HaskellWiki using type families instead of functional dependencies. My code is at [1]. I substituted all 'many to one' functional dependencies like xs ys - zs by explicit type families, but I don't know how to replace 'many to many' dependencies by type families only, so I've used associated types. But for some unknown to me reason the typechecker hangs if I try to get listQuickSort type signature in ghci. So I have 2 questions: what is the correct replacement of FDs in this case and where is an error in my code? I assume that the correct replacement exists (though it may not be very pretty) because type families and functional dependencies are equivalent in expressiveness [2]. I'm no guru on TF/ATs, but it seems to me that the simplest translation from fundeps would be to use multiple different type families for getting each of the result types. Thus, class Foo a b c ... x y z | a b c ... - ... x y z is first interpreted as: class Foo a b c ... x y z | ... , a b c ... - x , a b c ... - y , a b c ... - z which then becomes: ... type family FooX a b c ... type family FooY a b c ... type family FooZ a b c ... This is equivalent to converting a function of type (A,B,C,...)-(...,X,Y,Z) into multiple functions for determining each member of the output tuple separately. Your version using ATs to shove all the results into the Pick and Split classes is equivalent to constructing the output tuple directly. Apparently that doesn't work out for some reason. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
I have omitted the chunking [Char] because I don't like it; invariance with respect to the chunk sizes is something that should be left to the iteratee abstraction. I have this same reservation about iteratees. And related one for enumerators and enumeratees. Assuming my sense of their intended meanings is on track, they allow lots of well-typed but bogus values. Defining and adhering to a precise denotational model would eliminate all of these abstraction leaks, as Luke Palmer alludes to in http://lukepalmer.wordpress.com/2008/07/18/semantic-design/ . - Conal On Mon, Aug 23, 2010 at 4:06 PM, Heinrich Apfelmus apfel...@quantentunnel.de wrote: Conal Elliott wrote: For anyone interested in iteratees (etc) and not yet on the iteratees mailing list. I'm asking about what iteratees *mean* (denote), independent of the various implementations. My original note (also at the end below): In my world view, iteratees are just a monad M with a single operation symbol :: M Char that reads the next symbol from an input stream. In other words, they're a very simple parser monad. The emphasis is not on parsing, but on the fact that one and the same monadic value can be run on different streams runHandle :: M a - Handle - IO a runString :: M a - String - a runByteString :: M a - ByteString - a The monad M may also include convenience like exceptions and liftIO . I have omitted the chunking [Char] because I don't like it; invariance with respect to the chunk sizes is something that should be left to the iteratee abstraction. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ 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] Higher-order algorithms
Eugene Kirpichov wrote: Do there exist other nontrivial higher-order algorithms and datastructures? Is the field of higher-order algorithms indeed as unexplored as it seems? Many algorithms in natural language processing can be captured by higher-order algorithms parameterized by the choice of semiring (or module space). For example, consider the inference problem for hidden Markov models (which are often used for things like determining the part of speech tags for some sentence in natural language). To figure out the total probability that the HMM is in some state at some time, you use the Forward algorithm.[1] To figure out the probability of the most likely state sequence that has a specific state at some time, you use the Viterbi algorithm. To figure out not only the probability of the most likely state sequence but also what that tag sequence actually is, you can modify Viterbi to store back pointers. All of these are the same algorithm, just with different (augmented) semirings. In order to prevent underflow for very small probabilities, we usually run these algorithms with probabilities in the log-domain. Those variants are also the same algorithm, just taking the image of the semiring under the logarithm functor: Forward : FW ([0,1], +, 0, *, 1) Log Forward : FW ([-Inf,0], +, -Inf, +, 0) where -- Ignoring infinities... x + y | x = y= x + log (1 + exp (y-x)) | otherwise = y + log (1 + exp (x-y)) Viterbi : FW ([0,1], max, 0, *, 1) Log Viterbi : FW ([-Inf,0], max, -Inf, +, 0) ViterbiBP Q : FW (Maybe([0,1],Maybe Q), argmax, Nothing, *, Just(1,Nothing)) where -- Q = the type of the states in your HMM mx * my = do (px,x) - mx (py,y) - my return (px*py, y `mappend` x) Log (ViterbiBP Q) : FW ( Maybe([-Inf,0],Maybe Q) , argmax, Nothing , +, Just(0,Nothing)) where mx + my = do (px,x) - mx (py,y) - my return (px+py, y `mappend` x) Using augmented semirings we can simplify the backpointer version significantly in order to incorporate the optimizations usually encountered in practice. That is, the Maybes are required to make it a semiring, but we can optimize both of them away in practice, yielding an augmented semiring over (Prob,Q) or (Log Prob, Q). We get the same sort of thing for variants of the Backward algorithm used in the Forward--Backward algorithm. Of course, there's nothing special about HMMs here. We can extend the Forward--Backward algorithm to operate over tree structures instead of just list structures. That version is called the Inside--Outside algorithm. And semirings show up all over the place in other algorithms too. Of course, in hindsight this makes perfect sense: the powerset of the free semiring over S is the set of all (automata theoretic) languages over S. So semirings capture languages exactly; in the same way that commutative monoids capture multisets, and monoids capture sequences. This insight also extends to cover things like weighted-logic programming languages, since we can use any semiring we like, not just the Boolean probability semiring. Automata theoretic languages are everywhere. [1] Or you combine the Forward and Backward algorithms, depending on what exactly you want. Same goes for the others. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) I've been tinkering with this model as well. However, it doesn't really correspond to the iteratee interfaces I've seen, since those interfaces allow an iteratee to notice size and number of chunks. I suspect this ability is an accidental abstraction leak, which raises the question of how to patch the leak. What about enumerators? The definition given in Oleg's presentation ( http://okmij.org/ftp/Streams.html#iteratee, slide 21) is type Enumerator a = Iteratee a - Iteratee a Since we have a semantics for Iteratee, we could take this Enumerator definition as is, and we'd have a semantics, i.e., [[Enumerator a]] = [[Iteratee a]] - [[Iteratee a]] I don't trust this choice, however. It could be that, like the Iteratee representation, the Enumerator representation (as a function) is more an *implementation* than a semantics. That is, like Iteratee, * there might be a simpler and more natural semantic model; and * the representation may be junky, i.e., having many representations that we wouldn't want to be denotable. Is there a simpler model of Enumerator? My intuition is that it's simply a stream: [[Enumerator a]] = String Oddly, 'a' doesn't show up on the RHS. Maybe the representation ought to be type Enumerator = forall a. Iteratee a - Iteratee a so [[Enumerator]] = String Are there any enumerator definitions that couldn't use this more restrictive representation type? Glancing through the slides, the only Enumerator types I see are indeed polymorphic over a (the iteratee's result type.) Again, there's a terrible abstraction leak here, i.e., many ways to write down enumerators that type-check but are not meaningful within the model. Can this leak be fixed? Comments? - Conal On Mon, Aug 23, 2010 at 8:13 PM, Luke Palmer lrpal...@gmail.com wrote: On Mon, Aug 23, 2010 at 1:06 AM, Heinrich Apfelmus apfel...@quantentunnel.de wrote: Conal Elliott wrote: For anyone interested in iteratees (etc) and not yet on the iteratees mailing list. I'm asking about what iteratees *mean* (denote), independent of the various implementations. My original note (also at the end below): In my world view, iteratees are just a monad M with a single operation symbol :: M Char that reads the next symbol from an input stream. So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) = MaybeT (State [Char]) a symbol [] = Nothing symbol (c:cs) = Just (c, cs) I'm not experienced with iteratees. Does this miss something? Luke ___ 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] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
I'm not a semanticist, so I apologize right now if I say something stupid or incorrect. On Mon, Aug 23, 2010 at 9:57 PM, Conal Elliott co...@conal.net wrote: So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) I've been tinkering with this model as well. However, it doesn't really correspond to the iteratee interfaces I've seen, since those interfaces allow an iteratee to notice size and number of chunks. I suspect this ability is an accidental abstraction leak, which raises the question of how to patch the leak. From a purely practical viewpoint I feel that treating the chunking as an abstraction leak might be missing the point. If you said, you wanted the semantics to acknowledge the chunking but be invariant under the size or number of the chunks then I would be happier. I use iteratees when I need to be explicit about chunking and when I don't want the resources to leak outside of the stream processing. If you took those properties away, I wouldn't want to use it anymore because then it would just be an inelegant way to do things. I won't comment further in this email because I think I lack the formal training to follow the rest of your discussion. And that is unfortunate for me. Thanks, Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
On 24 August 2010 14:14, Jason Dagit da...@codersbase.com wrote: I'm not a semanticist, so I apologize right now if I say something stupid or incorrect. On Mon, Aug 23, 2010 at 9:57 PM, Conal Elliott co...@conal.net wrote: So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) I've been tinkering with this model as well. However, it doesn't really correspond to the iteratee interfaces I've seen, since those interfaces allow an iteratee to notice size and number of chunks. I suspect this ability is an accidental abstraction leak, which raises the question of how to patch the leak. From a purely practical viewpoint I feel that treating the chunking as an abstraction leak might be missing the point. If you said, you wanted the semantics to acknowledge the chunking but be invariant under the size or number of the chunks then I would be happier. I think that's the point, ie. to specify what the invariants should be. For example (to paraphrase, very poorly, something Conal wrote on the whiteboard behind me): run [concat [chunk]] == run [chunk] ie. the (a, [Char]) you maybe get from running an iteratee over any partitioning of chunks should be the same, ie. the same as from running it over the concatenation of all chunks, which is the whole input [Char]. I use iteratees when I need to be explicit about chunking and when I don't want the resources to leak outside of the stream processing. If you took those properties away, I wouldn't want to use it anymore because then it would just be an inelegant way to do things. Then I suppose the model for Enumerators is different than that for Iteratees; part of the point of an Enumerator is to control the size of the chunks, so that needs to be part of the model. An Iteratee, on the other hand, should not have to know the size of its chunks. So you don't want to be able to know the length of a chunk (ie. a part of the stream), but you do want to be able to, say, fold over it, and to be able to stop the computation at any time (these being the main point of iteratees ...). Conrad. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] ANNOUNCE: enumerator, an alternative iteratee package
On 24/08/10 03:47, John Millikin wrote: [...] I would like to avoid hard-coding the error type to SomeException, because it forces libraries to use unsafe/unportable language features (dynamic typing and casting). However, given the apparent practical requirement that all iteratees have the same error type, it seems like there's no other choice. I haven't worked enough with iteratees to have an informed opinion on this, but I wonder what the pros and cons are of having an error state in the iteratees at all. In other words, why would this data Step a m b = Continue (Stream a - Iteratee a m b) | Yield b (Stream a) | Error E.SomeException be preferred over this data Step a m b = Continue (Stream a - Iteratee a m b) | Yield b (Stream a) (Maybe with the restriction that m is a MonadError.) /M -- Magnus Therning(OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe signature.asc Description: OpenPGP digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
On Mon, Aug 23, 2010 at 10:37 PM, Conrad Parker con...@metadecks.orgwrote: On 24 August 2010 14:14, Jason Dagit da...@codersbase.com wrote: I'm not a semanticist, so I apologize right now if I say something stupid or incorrect. On Mon, Aug 23, 2010 at 9:57 PM, Conal Elliott co...@conal.net wrote: So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) I've been tinkering with this model as well. However, it doesn't really correspond to the iteratee interfaces I've seen, since those interfaces allow an iteratee to notice size and number of chunks. I suspect this ability is an accidental abstraction leak, which raises the question of how to patch the leak. From a purely practical viewpoint I feel that treating the chunking as an abstraction leak might be missing the point. If you said, you wanted the semantics to acknowledge the chunking but be invariant under the size or number of the chunks then I would be happier. I think that's the point, ie. to specify what the invariants should be. For example (to paraphrase, very poorly, something Conal wrote on the whiteboard behind me): run [concat [chunk]] == run [chunk] ie. the (a, [Char]) you maybe get from running an iteratee over any partitioning of chunks should be the same, ie. the same as from running it over the concatenation of all chunks, which is the whole input [Char]. I find this notation foreign. I get [Char], that's the Haskell String type, but what is [chunk]? I doubt you mean a list of one element. I use iteratees when I need to be explicit about chunking and when I don't want the resources to leak outside of the stream processing. If you took those properties away, I wouldn't want to use it anymore because then it would just be an inelegant way to do things. Then I suppose the model for Enumerators is different than that for Iteratees; part of the point of an Enumerator is to control the size of the chunks, so that needs to be part of the model. An Iteratee, on the other hand, should not have to know the size of its chunks. So you don't want to be able to know the length of a chunk (ie. a part of the stream), but you do want to be able to, say, fold over it, and to be able to stop the computation at any time (these being the main point of iteratees ...). I think I agree with that. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hackage on Linux
I used to use archlinux packages however it became a pain for the following reasons - packages on archlinux don't auto update when cabal does. This becomes really annoying when package X gets updated on cabal but not on arch and causes conflicts with other packages - in some situations doing a general update with arch (through clyde or packer) breaks ghc (last time it happened packer tried to uninstall/update arch packages which failed because those packages had dependencies. The files got removed but since unregister failed ghc thought they still existed) Apart from base/required packages, unless your linux distro has proper metapackages its in my opinion just better off using cabal install (and only use arch packages for binaries) On 23/08/2010 2:21 AM, Brandon S Allbery KF8NH allb...@ece.cmu.edu wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 08/22/2010 07:19 AM, Jonas Almström Duregård wrote: Now, you say it's preferable to use the na... No, the Windows and OSX installers are just that. They provide no facilities for finding packages, identifying the package a given file came from, or dependency tracking. OSX's installer doesn't even have uninstall support; it records the installed files, but provides no mechanism for undoing configuration changes such as removing package-installed kernel modules. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla -... iEYEARECAAYFAkxxTmoACgkQIn7hlCsL25VNsQCfZKJIz+KONa4yWAI97QYyttGU ITMAnjoAhcj3kMrWxnsSxWb5jraFBu1r =ERlI -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hackage on Linux
On 24 August 2010 15:50, Mathew de Detrich dete...@gmail.com wrote: I used to use archlinux packages however it became a pain for the following reasons - packages on archlinux don't auto update when cabal does. This becomes really annoying when package X gets updated on cabal but not on arch and causes conflicts with other packages Huh? Are you referring to doing a cabal update? If so, how is this causing conflicts? Are you mixing and matching distro packages with packages installed by hand? I thought Don kept the external Haskell repository up to date with the packages on Hackage... - in some situations doing a general update with arch (through clyde or packer) breaks ghc (last time it happened packer tried to uninstall/update arch packages which failed because those packages had dependencies. The files got removed but since unregister failed ghc thought they still existed) Is this the problem with bad packages or the package manager playing up? Apart from base/required packages, unless your linux distro has proper metapackages its in my opinion just better off using cabal install (and only use arch packages for binaries) What do you mean by metapackages? -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
On 24 August 2010 14:47, Jason Dagit da...@codersbase.com wrote: On Mon, Aug 23, 2010 at 10:37 PM, Conrad Parker con...@metadecks.org wrote: On 24 August 2010 14:14, Jason Dagit da...@codersbase.com wrote: I'm not a semanticist, so I apologize right now if I say something stupid or incorrect. On Mon, Aug 23, 2010 at 9:57 PM, Conal Elliott co...@conal.net wrote: So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) I've been tinkering with this model as well. However, it doesn't really correspond to the iteratee interfaces I've seen, since those interfaces allow an iteratee to notice size and number of chunks. I suspect this ability is an accidental abstraction leak, which raises the question of how to patch the leak. From a purely practical viewpoint I feel that treating the chunking as an abstraction leak might be missing the point. If you said, you wanted the semantics to acknowledge the chunking but be invariant under the size or number of the chunks then I would be happier. I think that's the point, ie. to specify what the invariants should be. For example (to paraphrase, very poorly, something Conal wrote on the whiteboard behind me): run [concat [chunk]] == run [chunk] ie. the (a, [Char]) you maybe get from running an iteratee over any partitioning of chunks should be the same, ie. the same as from running it over the concatenation of all chunks, which is the whole input [Char]. I find this notation foreign. I get [Char], that's the Haskell String type, but what is [chunk]? I doubt you mean a list of one element. sorry, that was just my way of writing the list of chunks or perhaps the stream of chunks that represents the input. Conrad. I use iteratees when I need to be explicit about chunking and when I don't want the resources to leak outside of the stream processing. If you took those properties away, I wouldn't want to use it anymore because then it would just be an inelegant way to do things. Then I suppose the model for Enumerators is different than that for Iteratees; part of the point of an Enumerator is to control the size of the chunks, so that needs to be part of the model. An Iteratee, on the other hand, should not have to know the size of its chunks. So you don't want to be able to know the length of a chunk (ie. a part of the stream), but you do want to be able to, say, fold over it, and to be able to stop the computation at any time (these being the main point of iteratees ...). I think I agree with that. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
