April 2007 - Haskell-Cafe

QuickCheck's co-arbitrary
by Joel Reymont 04 Apr '07

04 Apr '07

Folks, I understand that arbitrary defines the possible values. How do I generally come up with co-arbitrary, though? Would someone kindly explain the choice of co-arbitrary in the following cases, specially the very last bit with "variant 1 . coarbitrary a"? instance Arbitrary Char where arbitrary = elements ([' ', '\n', '\0'] ++ ['a'..'h']) coarbitrary c = variant (fromEnum c `rem` 4) instance Arbitrary Ordering where arbitrary = elements [LT, EQ, GT] coarbitrary LT = variant 0 coarbitrary EQ = variant 1 coarbitrary GT = variant 2 instance Arbitrary a => Arbitrary (Maybe a) where arbitrary = frequency [ (1, return Nothing) , (3, liftM Just arbitrary) ] coarbitrary Nothing = variant 0 coarbitrary (Just a) = variant 1 . coarbitrary a Thanks, Joel -- http://wagerlabs.com/

2 1

Which pretty printer?
by Joel Reymont 04 Apr '07

04 Apr '07

Should I prefer Daan Leijen's pretty printer [1] to the Hughes-SPJ one that comes with GHC? Has anyone looked at both and is able to tell the difference? I need to pretty-print a Pascal-like language as well as C#. Thanks, Joel [1] http://www.cs.uu.nl/~daan/download/pprint/pprint.html -- http://wagerlabs.com/

1 1

Josephus problem and style
by Anthony Chaumas-Pellet 04 Apr '07

04 Apr '07

Hello, I've written a function to compute the general Josephus problem, giving both the number of the survivor and the order in which the others are killed. However, I am not overly fond of my actual Haskell implementation, so I would like some comments on elegance. My current function is as follow:: josephus k n = josephus' k 1 [1..n] [] where josephus' k i (x:xs) sorted | xs == [] = (x, reverse sorted) | i `mod` k == 0 = josephus' k (i+1) xs ([x] ++ sorted) | otherwise = josephus' k (i+1) (xs ++ [x]) sorted The biggest difficulty I had is representing the circle (a continuous unit, unlike the list). The only solution I've found is to explicitly concatenate lists during each iteration, using an index to check whether the current element should be kept. It seems to me that manupilating lists so often makes the resulting function unclear, and hides the basic principle behind the Josephus sequence. So, I'm looking for a better way to write this function, but enlightenment eludes me. I've taken up Haskell in earnest a couple weeks ago, after a fairly long stay in Lisp land (perhaps it shows). My previous "Eureka!" moment in Haskell was matrix multiplication, along the lines of: matProd a b = [[sum (zipWith (*) x y) | y <- transpose b]| x <- a] Thanks! Anthony Chaumas-Pellet

7 8

Memory leak in streaming parser
by Oren Ben-Kiki 04 Apr '07

04 Apr '07

I refactored the code and uploaded a new version to Hackage (YamlReference-0.2). It is cleaner now and much more efficient. It is still "leaking" memory though. The profiler hints at "bindReply" as the culprit retaining State and Reply objects, but it isn't clear to me why the code would do that. Trying to `seq` things again either kills streaming or has no effect. Perhaps my basic approach is wrong... Any advice would be appreciated, Oren Ben-Kiki

1 0

SmallCheck and parser testing
by Joel Reymont 03 Apr '07

03 Apr '07

Folks, I'm trying to figure out how to test a Parsec-based parser with Smallcheck [1]. My test AST is below and the goal is to return StyleValue <Int here> if the parser is fed an integer, or return Solid when parsing "Solid", etc. data Style = StyleValue Expr | Solid | Dashed | Dotted | Dashed2 | Dashed3 deriving Show I figure that the following is needed somehow: instance Serial Style where series = cons1 StyleValue . depth 0 \/ cons0 Solid \/ cons0 Dashed \/ cons0 Dashed2 \/ cons0 Dashed3 \/ cons0 Dotted My parser is 'style', so I would be passing it as p below run p input = case (parse p "" input) of Left err -> do { putStr "parse error at " ; print err } Right x -> x How do I go from here to making sure my parser is valid? I thought of the following property (thanks sjanssen) prop_parse p s = show (run p s) == s but I don't know how to proceed from here. Thanks, Joel [1] http://www.cs.york.ac.uk/fp/darcs/smallcheck/ -- http://wagerlabs.com/

3 2

A question about functional dependencies and existential quantification
by oleg＠pobox.com 03 Apr '07

03 Apr '07

Jean-Marie Gaillourdet wrote > I am trying to do something like the following: > > {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} > > module TestCase where > > > > data Any root = forall pos sel . T root pos sel => ANY pos > > > > class T root pos sel | pos -> root, root -> sel where > > f :: pos -> sel -> Bool > > > > instance T root (Any root) sel where > > f (ANY p) s = f p s The code as posted seems to have a problem. The problem is noted by GHC 6.4 and hugs but is accepted by GHC 6.6. Such a change in GHC seems strange. The problem is not related to existentials, so we just drop them > {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} > module TestCase where > > data Any root = ANY > > class T root pos sel | pos -> root, root -> sel where > f :: pos -> sel -> Bool > instance T root (Any root) sel > > test x = f ANY x Hugs and GHC 6.4 both complain about the instance of T: Hush (September 2006 version) says ERROR "/tmp/j.hs":9 - Instance is more general than a dependency allows and GHC 6.4.2 says Illegal instance declaration for `T root (Any root) sel' (the instance types do not agree with the functional dependencies of the class) In the instance declaration for `T root (Any root) sel' I concur. The class declares T as being a ternary relation such that the following holds forall r p p' s s'. T(r,p,s) && T(r,p',s') -> s = s' Now, the instance `T root (Any root) sel' is satisfied when root=Int, sel = Bool and when root=Int, sel = Int. Does it not? That falsifies the above proposition. In other words, the instance T is not functional with respect to the first and the third arguments. That is not surprising. What is surprising is why GHC 6.6 accepts such an instance?

9 11

Re: [Haskell-cafe] Why the Prelude must die
by Vivian McPhail 03 Apr '07

03 Apr '07

I agree with Sven, but... What I want to push is a 'mathematically sound' numeric prelude. A proper numerical prelude should have bona fide mathematical obects like groups, rings, and fields underlying common numerical classes. It would be edifying to the student who discovered that the particular data type he is using is an inhabitant of a known class and can thus take advantage of known properties, presupplied as class methods. Reasoning and communication about programs, data types, and functions would be enhanced. [Conjecture 1 (2007). Haskell Mathematical Prelude and Mathematicians] If Haskell had a mathematically sound prelude then more mathematicians would use Haskell. Cheers, Vivian > > Message: 1 > Date: Sat, 24 Mar 2007 17:56:11 +0100 > From: Sven Panne <sven.panne(a)aedion.de> > Subject: Re: [Haskell-cafe] Why the Prelude must die > To: haskell-cafe(a)haskell.org > Cc: libraries(a)haskell.org > Message-ID: <200703241756.11121.sven.panne(a)aedion.de> > Content-Type: text/plain; charset="iso-8859-1" > > On Saturday 24 March 2007 03:48, Stefan O'Rear wrote: > > 1. Namespace pollution > > > > The Prelude uses many simple and obvious names. Most > programs don't > > use the whole Prelude, so names that aren't needed take up > namespace > > with no benefit. [...] > > Even though I think that the current Prelude is far from > perfect, one should not forget that is a very solid > foundation of a "common language": If one sees e.g. '(.)' or > 'map', it is immediately clear to everybody what this means, > without having to scan through (perhaps long) import lists. > Of course one could hide some parts of the Prelude etc., but > I think in the long run this only leads to confusion. > Redefining common things, heavy use of tons of self-defined > operators etc. all make maintenance much harder. > > Try reading Lisp code with heavy use of macros or C++ code > with tons of overloadings. This is more like Sudoku solving > than anything else, because there is no "common language" > between the author and the reader anymore. > > And taking away the prelude is a little bit like taking away > 'int', 'double', 'for', 'while' etc. from the C programmer... > > > 11. Committeeism > > > > Because the Prelude has such a wide audience, a strong committee > > effect exists on any change to it. This is the worst kind of > > committeeism, and impedes real progress while polluting the Prelude > > with little-used features such as fail in Monad (as opposed to > > MonadZero) and until. > > Depending on your viewpoint, you can see this as a plus. > Everybody agrees that finalizers are evil, but propose the > removal of that method from java.lang.Object to the Java people. :-) > > My proposal would be to incrementally improve the Prelude, > modularize it a bit more, fix the Num hierarchy, but > basically leave it as it is. > > Cheers, > S. > >

13 14

ANN: HSH 1.2.0
by John Goerzen 03 Apr '07

03 Apr '07

Hi, I'm pleased to announce HSH 1.2.0. Since version 1.0.0 was announced a few days ago, there have been some improvements: * run is now a function with a polymorphic return type. Depending on the value expected, it can return to you a String representing all output, an exit code, a list of lines of output, etc. runS is now removed. * A number of new helper functions in ShellEquivs. Fixes to readlink and readlinkabs there. * New helper functions runIO (to force an IO () context) and runSL (returns a single line of output, \n stripped) * There are now 82 unit tests. Get it at: http://software.complete.org/hsh -- John Goerzen Author, Foundations of Python Network Programming http://www.amazon.com/exec/obidos/tg/detail/-/1590593715

10 29

was Re: ANN: HSH 1.2.0
by Thomas Hartman 03 Apr '07

03 Apr '07

I'm still trying to figure out how to do this on ubuntu. If this winds up being a garden path I'll try on debian next, but at least I'm learning a lot about getting haskell stuff built. Anyway, since I'm on a virtualized linux box, I decided to get a fresh start, unmounted my original OS profile and installed a fresh dapper 6. I then changed /etc/apt/sources.list to be okay for grabbing .debs from feisty. (No longer doing the build from source thing.) apt-get install ghc6, ok from feisty. (Is there another repo that gets all the extra libs at one go?) sudo apt-cache search -o APT::Cache-Limit=25165824 ghc6 | grep -i missing libghc6-hdbc-missingh-dev - Integration of HDBC with MissingH, GHC version libghc6-missingh-dev - Library of utility functions for Haskell, GHC6 package thartman@linodehaskell:~/haskellinstalls/hsh>sudo apt-cache search -o hoorah, my apt cache search command seems ok. sudo apt-cache search -o APT::Cache-Limit=25165824 ghc6 | grep -i hsh thartman@linodehaskell:~/haskellinstalls/hsh> too bad, still no hsh in ubuntu repo. darcs get http://darcs.complete.org/hsh/ (Or should I have used something else?) runghc Setup.hs configure same problems as before. But starting afresh seems to have detangled the issues I was having with packaging confusion. At least now I can apt-get install missingh And some other dependency following is made easier. Finally configure for hsh works. But then thartman@linodehaskell:~/haskellinstalls/hsh>sudo runghc Setup.lhs install Setup.lhs: Warning: The field "hs-source-dir" is deprecated, please use hs-source-dirs. Installing: /usr/local/lib/HSH-1.2.1/ghc-6.6 & /usr/local/bin HSH-1.2.1... Setup.lhs: Error: Could not find module: HSH with any suffix: ["hi"] So, I seem to be stuck at this point. 2007/4/2, Thomas Hartman <tphyahoo(a)gmail.com>: > Well, I guess I spoke to soon. After building ghc6 from feisty as > described above, I tried building missingh and have basically what I > started with. > > Is there something I can tweak to get the above straightened out using > those nice deb packages, or do I have to do all the dependency chasing > involved with building from source? Or is there another way? > > If this is too debian oriented please yell at me and I will ask about > this on a deb/ubuntu forum. > > thanks... > > Note, should have mentioned, after doing as my above post describes, I > installed all the newly generated deb packages with > > dpkg -i *.deb > > **************** > > thartman@linodewhyou:~/haskellInstalls/missingh>runghc Setup.hs configure > Configuring MissingH-0.18.3... > configure: /usr/lib/ghc-6.6/bin/ghc-pkg > configure: Dependency unix-any: using unix-1.0 > Setup.hs: cannot satisfy dependency network-any > > thartman@linodewhyou:~/haskellInstalls/missingh>which runghc > /usr/lib/ghc-6.6/bin/runghc > > # note, definitely the thing I installed today: > thartman@linodewhyou:~/haskellInstalls/missingh>ls -l `which runghc` > -rwxr-xr-x 1 root root 300716 Apr 2 09:17 /usr/lib/ghc-6.6/bin/runghc > thartman@linodewhyou:~/haskellInstalls/missingh> > > # and I installed it from deb ghc6, dpkg recognizes it > > thartman@linodewhyou:~/haskellInstalls/missingh>dpkg -S > /usr/lib/ghc-6.6/bin/runghc > ghc6: /usr/lib/ghc-6.6/bin/runghc > > # it does seem like ghc6 comes with a network package > thartman@linodewhyou:~/learning/haskell>apt-cache showpkg ghc6 | grep -i network > 6.4.1-2ubuntu2 - libghc6-readline-dev libghc6-stm-dev libghc6-hgl-dev > libghc6-x11-dev libghc6-fgl-dev libghc6-mtl-dev libghc6-hunit-dev > libghc6-quickcheck-dev libghc6-network-dev libghc6-haskell-src-dev > libghc6-parsec-dev libghc6-cabal-dev libghc6-unix-dev > libghc6-template-haskell-dev libghc6-haskell98-dev libghc6-base-dev > libghc6-rts-dev ghc haskell-compiler > > # I get lost here. Do I have libghc6-network-dev, or don't I? > > thartman@linodewhyou:~/haskellInstalls/missingh>sudo apt-get install > libghc6-network-dev > Reading package lists... Done > Building dependency tree... Done > Note, selecting ghc6 instead of libghc6-network-dev > ghc6 is already the newest version. > You might want to run `apt-get -f install' to correct these: > The following packages have unmet dependencies: > hat-ghc6: Depends: ghc6 (< 6.4.1+) but 6.6-3 is to be installed > libghc6-cabal-dev: Depends: ghc6 (< 6.4.2) but 6.6-3 is to be installed > E: Unmet dependencies. Try 'apt-get -f install' with no packages (or > specify a solution). > > > > > > > 2007/4/2, Thomas Hartman <tphyahoo(a)gmail.com>: > > > As you have built ghc6.6 from sources I think that you also need to build > > > all haskell libs from sources. So, do > > > > I did this, and got the feeling this would probably work, but is a > > real sad world of dependency chasing with no (clear) end in sight. > > > > So I investigated your second suggestion > > > > > Another way is to take ghc6 and all haskell libs from fiesty. > > > > which to me seems much preferrable. > > > > http://old.pupeno.com/blog/unstable-packages-on-ubuntu/ > > > > Was indispensible in helping me figure out how to do this. > > > > To give some details on this (which is really more apt packaging know > > how than haskell but whatever), I did something like > > > > 1) change /etc/apt/sources.list to add > > > > deb-src http://archive.ubuntu.com/ubuntu/ feisty main restricted > > universe multiverse > > > > note, only add deb-src line here, not deb line, see article above for why. > > > > sudo aptitude install fakeroot (needed utility) > > fakeroot apt-get source --build ghc6 > > -- complains, some dependencies are missing > > > > sudo aptitude install ..... > > install packages with above command, not from source. it's my first > > time using the aptitude command, I wonder if this does the same thing > > as apt-get install, which is what I usually do. Whatever the case... > > > > fakeroot apt-get source --build ghc6 > > > > works :) > > > > 2007/3/21, Max Vasin <max.vasin(a)gmail.com>: > > > >>>>> "Thomas" == Thomas Hartman <tphyahoo(a)gmail.com> writes: > > > > > > Thomas> Furthermore (as the above messages suggest and locate confirms), I > > > Thomas> seem to have mtl already > > > > > > Thomas> I took a wild guess and tried specifying this with ghc -i > > > > > > Thomas> like > > > > > > Thomas> sudo runghc -i/usr/lib/ghc6-mtl-dev Setup.lhs configure > > > Thomas> and sudo runghc -i/usr/lib/ Setup.lhs configure > > > > > > Thomas> but no dice. > > > > > > Thomas> *************** > > > > > > Thomas> thartman@linodewhyou:~/haskellInstalls/hsh$ locate libghc6-mtl-dev > > > Thomas> /home/thartman/libghc6-mtl-dev_1.0-3_i386.deb > > > Thomas> /usr/lib/libghc6-mtl-dev > > > Thomas> /usr/lib/libghc6-mtl-dev/register.sh > > > Thomas> /usr/lib/libghc6-mtl-dev/unregister.sh > > > Thomas> /usr/share/doc/libghc6-mtl-dev > > > Thomas> /usr/share/doc/libghc6-mtl-dev/changelog.Debian.gz > > > Thomas> /usr/share/doc/libghc6-mtl-dev/copyright > > > Thomas> /var/lib/dpkg/info/libghc6-mtl-dev.list > > > Thomas> /var/lib/dpkg/info/libghc6-mtl-dev.md5sums > > > Thomas> /var/lib/dpkg/info/libghc6-mtl-dev.postinst > > > Thomas> /var/lib/dpkg/info/libghc6-mtl-dev.prerm > > > > > > As you have built ghc6.6 from sources I think that you also need to build > > > all haskell libs from sources. So, do > > > > > > $ apt-get source libghc6-mtl-dev > > > $ cd <haskell-mtl-or-whatever-dir-is-named> > > > $ runhaskell Setup.lhs configure > > > $ runhaskell Setup.lhs build > > > $ sudo runhaskell Setup.lhs install > > > > > > Another way is to take ghc6 and all haskell libs from fiesty. > > > > > > -- > > > WBR, > > > Max Vasin. > > > > > > _______________________________________________ > > > Haskell-Cafe mailing list > > > Haskell-Cafe(a)haskell.org > > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > >

1 3

Matlab/BLAS/LAPack and Re: [Haskell-cafe] Mathematics in Haskell Re: Why the Prelude must Die
by Alexander McPhail 03 Apr '07

03 Apr '07

Since I brought this up (search haskell' list) I should probably volunteer to help. If people agree I can coordinate an effort to build a mathematically sound hierarchy. Unfortunately my mathematical knowledge is less than ideal for this purpose (I am actively remedying this at university). However, if there is an administrative burden I volunteer to shoulder it. On a related note I have written a binding to Matlab data files and arrays if anyone is interested, and I am embarking on a project to bind to CBLAS and CLAPack. Vivian > > Jacques Carette wrote: > > > >> perhaps i was mistaken in thinking that there is a group of > >> math-interested haskellers out there discussing, developing, and > >> documenting the area? or perhaps that group needs introductory > >> tutorials presenting its work? > > My guess is that there are a number of people "waiting in > the wings", > > waiting for a critical mass of features to show up before really > > diving in. See http://www.cas.mcmaster.ca/plmms07/ > > for my reasons for being both interested and wary). > > > > Probably the simplest test case is the difficulties that people are > > (still) encountering doing matrix/vector algebra in Haskell. One > > either quickly encounters efficiency issues (although PArr might > > help), or typing issues (though many tricks are known, but not > > necessarily simple). Blitz++ and the STL contributed > heavily to C++ > > being taken seriously by people in the scientific computation > > community. Haskell has even more _potential_, but it is > definitely unrealised potential. > > > > I am one of those mathematicians "waiting in the wings." > Haskell looked > very appealing at first, and the type system seems perfect, > especially for > things like multilinear algebra where currying and duality is > fundamental. > I too was put off by the Num issues though--strange mixture > of sophisticated > category theory and lack of a sensible hierarchy of algebraic objects. > > However, I've decided I'm more interested in helping to fix > it than wait; > so count me in on an effort to make Haskell more > mathematical. For me that > probably starts with the semigroup/group/ring setup, and good > arbitrary-precision as well as approximate linear algebra support. > > -- > > I've been watching this thread for quite a while now, and it seems to > me that there is quite a bit of interest in at least working on a new > Prelude. I've also noticed a 'The Other Prelude' page on the wiki > [http://haskell.org/haskellwiki/The_Other_Prelude] and they seem to > have a start on this. So it seems that we should actually start this, > because people will contribute. Can somebody with good Cabal skills > and maybe access to darcs.haskell.org start a new library for people > to start patching? > > Bryan Burgers > > > > On Apr 2, 2007, at 3:24 PM, Andrzej Jaworski wrote: > > >> I too was put off by the Num issues though--strange mixture of > >> sophisticated > >> category theory and lack of a sensible hierarchy of algebraic > >> objects. > > > > Perhaps we should replace CT with lattice theoretic thinking (e.g. > > functor = monotonic > > function) before cleaning up the type-related mess? > > See: http://citeseer.ist.psu.edu/269479.html > > > >> so count me in on an effort to make Haskell more mathematical. > >> For me that > >> probably starts with the semigroup/group/ring setup, and good > >> arbitrary-precision as well as approximate linear algebra support. > > > > I agree: semigoups like lattices are everywhere. > > Then there could be a uniform treatment of linear algebra, > > polynomial equations, operator > > algebra, etc. So, perhaps haste is not a good advice here? > > > > -Andrzej > >

3 2