August 2010 - Haskell-Cafe

Re: [haskell-cafe] How to substitute FD like a -> b c by type families?
by Vladimir Matveev 24 Aug '10

24 Aug '10

Thanks, that was helpful :) here is the working code if someone interested: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=29406#a29406 2010/8/24 wren ng thornton <wren(a)freegeek.org>: > 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(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

Changing my Profile
by David Webster 24 Aug '10

24 Aug '10

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

5 4

Re: [Haskell-cafe] Fast Integer Input
by 200901104＠daiict.ac.in 24 Aug '10

24 Aug '10

> From: "Daniel Fischer" <daniel.is.fischer(a)web.de> > To: 200901104(a)daiict.ac.in > Sent: Monday, August 23, 2010 11:14:55 PM > Subject: Re: [Haskell-cafe] Fast Integer Input > On Monday 23 August 2010 17:06:02 you wrote: > > >>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? > > > > That, time limit, SPOJ? (If so, which one?) Yes. The time limit is 4 sec. The question has more parts than just this though. http://www.spoj.pl/problems/VGCD/. (Note: Spoiler at the bottom) > > You can calculate the binary logarithm to high accuracy without > parsing the > entire number. Just parse the first k digits and get the count of > digits, > from that the logarithm is quickly calculated. I will try this out. > > > >>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) Spoiler: The given numbers are Fibonacci. Wikipedia has said some interesting properties, which makes the question into finding where the number is in the Fibonacci sequence.

1 0

Re: [Haskell] Re: [Haskell-cafe] ANNOUNCE: enumerator, an alternative iteratee package
by John Millikin 24 Aug '10

24 Aug '10

On Sat, Aug 21, 2010 at 23:14, Paulo Tanimoto <ptanimoto(a)gmail.com> wrote: > One question: enumFile has type > > enumFile :: FilePath -> Enumerator SomeException ByteString IO b > > and iterParser has type > > iterParser :: Monad m => Parser a -> Iteratee ParseError ByteString m a > > How do we use both together? Something in these lines won't type-check > > E.run (E.enumFile "file" E.$$ (E.iterParser p)) > > because the error types are different. Forgot to mention that -- use the "mapError" function from enumerator-0.2.1 thusly: http://ianen.org/haskell/enumerator/api-docs/Data-Enumerator.html#v%3AmapEr… -------------------------------------------------------------------------------- parser :: Parser Foo toExc :: Show a => a -> E.SomeException toExc = E.SomeException . E.ErrorCall . show main :: IO () main = do run (enumFile "parsetest.txt" $$ mapError toExc $$ iterParser parser) >>= print -------------------------------------------------------------------------------- You don't have to map to SomeException -- any type will do. For example, in a complex pipeline with real error handling at the other end, you might want a custom error type so you'll know at what stage the error occurred.

3 3

How to substitute FD like a -> b c by type families?
by Vladimir Matveev 24 Aug '10

24 Aug '10

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

2 1

feasability of implementing an awk interpreter.
by Michael Litchard 24 Aug '10

24 Aug '10

I'd like the community to give me feedback on the difficulty level of implementing an awk interpreter. What language features would be required? Specifically I'm hoping that TH is not necessary because I'm nowhere near that skill level. An outline of a possible approach would be appreciated. I am using http://www.math.utah.edu/docs/info/gawk_toc.html as a guide to the language description.

9 11

Filename encoding error (was: Perform a research a la Unix 'find')
by Yves Parès 23 Aug '10

23 Aug '10

In fact the encoding problem is more general. When I simply do 'readFile "bar/fooé"', then I'm told: *** Exception: bar/fooé: openFile: does not exist (No such file or directory) How am I supposed to read files whose names contains non-ASCII characters? (I use GHC 6.12.3 under Ubuntu 10.04 32bits) ---------- Forwarded message ---------- From: Yves Parès <limestrael(a)gmail.com> Date: 2010/8/22 Subject: Re: [Haskell-cafe] Perform a research a la Unix 'find' To: Magnus Therning <magnus(a)therning.org> Cc: haskell-cafe(a)haskell.org I looked at both, and I have encoding issues with both. My locale is fr_FR.utf8 For instance, with HSH: I have a 'bar' directory, containing a file 'fooé' run $ "find bar" :: IO [String] returns me : ["bar", "bar/foo*\233*"] and run $ "find bar -name fooé" returns [] When I provoke an error by running: run $ "find fooé" it says : find: "foo*\351*": No file or directory So it is not the same encoding!

4 3

ANNOUNCE: ipatch, the interactive patch editor
by Joachim Breitner 23 Aug '10

23 Aug '10

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-p… 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 -- Joachim "nomeata" Breitner mail: mail(a)joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nomeata(a)joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nomeata(a)debian.org

4 8

ANNOUNCE: darcs 2.5 beta 4
by Reinier Lamers 23 Aug '10

23 Aug '10

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

1 0

Re: [Haskell-cafe] ANNOUNCE: enumerator, an alternative iteratee package
by John Lato 23 Aug '10

23 Aug '10

> > From: John Millikin <jmillikin(a)gmail.com> > > On Sat, Aug 21, 2010 at 15:35, Paulo Tanimoto <ptanimoto(a)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

2 2