April 2007 - Haskell-Cafe

newbie question on ordering
by Nikolay Metchev 23 Apr '07

23 Apr '07

Hello guys, I have decided to try and get back into Haskell recently. I have used it in the past but have forgotten large chunks. I am trying to express the logic of a particular card game. For this purpose I need to be able to order cards in various orders. At first I thought that the Ord class was my answer but I found it very verbose. Below is my best attempt so far but I can't help but feel it too is verbose and that there must be a better way of comparing cards in different orders. data Face = Ace | Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King deriving (Enum, Show, Eq) data Suit = Clubs | Diamonds | Hearts | Spades deriving (Show, Enum, Eq) type Card = (Face, Suit) listComparator :: (Eq a) => [a] -> a -> a -> Ordering listComparator xs a b = compare x y where x = elemIndex a xs y = elemIndex b xs sequentialBonusFaceOrder :: [Face] sequentialBonusFaceOrder = [Seven, Eight, Nine, Ten, Jack, Queen, King, Ace] fourOfAKindBonusFaceOrder :: [Face] fourOfAKindBonusFaceOrder = [Queen, King, Ten, Ace, Nine, Jack] sequentialBonusFaceComparator :: Face -> Face -> Ordering sequentialBonusFaceComparator = listComparator sequentialBonusFaceOrder fourOfAKindBonusFaceComparator :: Face -> Face -> Ordering fourOfAKindBonusFaceComparator = listComparator fourOfAKindBonusFaceOrder The problem with this approach is that if you want to compare you to write things of the following nature: fourOfAKindBonusFaceComparator f1 f2 == GT this isn't very clear especially if you want "<=" you have to do fourOfAKindBonusFaceComparator f1 f2 /= GT Any suggestions would be nice.

3 2

question about Data.Binary and Double instance
by David Roundy 22 Apr '07

22 Apr '07

Hi all, I'm wondering what exactly inspired the decode/encodeFloat implementation for Data.Binary? It seems to me like it'd be much better to use a standard format like IEEE, which would also be much more efficient, since as far as I know, on every implementation a Double and a CDouble are identical. Are there any suggestions how I could use Data.Binary to actually read a binary file full of Doubles? Should I just use the Array interface, and forget laziness and hopes of handling different-endian machines? Or is there some way to reasonably do this using Data.Binary? -- David Roundy Department of Physics Oregon State University

6 15

ANNOUNCE: xmonad 0.1
by Spencer Janssen 22 Apr '07

22 Apr '07

The xmonad dev team is pleased to announce the inaugural release of: xmonad: a tiling window manager http://xmonad.org Xmonad is a minimalist tiling window manager for X, written in Haskell. Windows are managed using automatic layout algorithms, which can be dynamically reconfigured. At any time windows are arranged so as to maximise the use of screen real estate. All features of the window manager are accessible purely from the keyboard: a mouse is entirely optional. Xmonad is configured in Haskell, and custom layout algorithms may be implemented by the user in config files. A principle of Xmonad is predictability: the user should know in advance precisely the window arrangement that will result from any action. By default xmonad provides three layout algorithms: tall, wide and fullscreen. In tall or wide mode, windows are tiled and arranged to prevent overlap and maximise screen use. Sets of windows are grouped together on virtual screens, and each screen retains its own layout, which may be reconfigured dynamically. Multiple physical monitors are supported via Xinerama, allowing simultaneous display of a number of screens. By utilising the expressivity of a modern functional language with a rich static type system, Xmonad provides a complete, featureful window manager in less than 500 lines of code, with an emphasis on correctness and robustness. Internal properties of the window manager are checked using a combination of static guarantees provided by the type system, and type-based automated testing. A benefit of this is that the code is simple to understand, and easy to modify. More information, screenshots, documentation and community resources are available from: http://xmonad.org Xmonad is available from hackage, and via darcs. Happy hacking! The Xmonad Team: Spencer Janssen Don Stewart Jason Creigh

1 0

Lessons from memory leak in streaming parser
by Oren Ben-Kiki 21 Apr '07

21 Apr '07

First, let me thank all the people who responded to my issue, it was very helpful. I would have responded earlier but I was on a business trip and out of contact for the last week. On the bright side I used the time to re-work my implementation. Instead of relying on Haskell's lazy evaluation, elegant as it may be, I changed it to use a continuation passing style. Every invocation of the parser returns a few tokens and a parser for the rest of the input. Interestingly, this approach maps well to non-lazy languages - basically anything that supports closures - unlike the original method that relied on lazy evaluation. So in principle I can now convert the Haskell code to Scheme, Ruby, or even JavaScript. At any rate, once I have done that, things started to fall into place. I still had minor leaks, but the results of profiling were actually proving useful for a change. I needed to turn off lazy evaluation in several key places (almost all record fields are now strict, and a 'seq' was needed in one crucial location). The result is a parser that can handle anything you throw at it with constant (reasonably low) memory usage. It is dog-slow (about 8k/sec, or twice that if compiling with -O2) but I was expecting that. So, lesson learned - lazy evaluation in Haskell is a very nice feature, but extremely difficult to debug, profile and control. Using continuations may be less elegant at places, but is much more practical. You can see the final result in version 0.3 of the YamlReference package I just uploaded to the Cabal database. This is intended to be an "executable version" of the YAML specification (the BNF file, which is actually Haskell code, is almost exactly the list of spec BNF productions). Thanks again for all the help, Oren Ben-Kiki

1 0

Installation of hs-plugins
by Philipp Volgger 21 Apr '07

21 Apr '07

Hello everybody, could somebody please tell me how hs-plugins has to be installed. I tried it with hs-plguin 1.0rc1 and I was unable to build it. I did runhaskell Setup.lhs configure runhaskell Setup.lhs build (Crash without any information) I tried it wiht GHC 6.4, 6.4.1 and 6.6. I am using Windows XP with SP2.

2 2

anyone interested in developing a Language.C library?
by Duncan Coutts 21 Apr '07

21 Apr '07

Hi all, If anyone is interested in developing a Language.C library, I've just completed a full C parser which we're using in c2hs. It covers all of C99 and all of the GNU C extensions that I have found used in practise, including the __attribute__ annotations. It can successfully parse the whole Linux kernel and all of the C files in all the system packages on my Gentoo installation. It's implemented as an alex lexer and a happy parser. The happy grammar has one shift/reduce conflict for the dangling if/then/else issue (which could be hidden by using precedence but it's clearer not to). So if someone is interested in developing a more widely usable Language.C library, I think this would be a good place to start. There's plenty to do however: * The c2hs C AST is ok but probably not enough for a general purpose library. * The parser currently uses some other c2hs infrastructure which would need disentangling to pull the parser out (mostly identifiers and unique name supply management). * It does not record everything into the parse tree, eg __attribute__s are parsed but ignored. * It does no semantic analysis after parsing (though other bits of c2hs to a very little) * In at least one place the parser is deliberately too liberal (to avoid ambiguities) which would require simple extra checks after parsing to detect. * The lexical syntax has not been checked against the spec fully, it is probably over-liberal in some cases. * I've not done much performance work, the lexer has not been seriously tuned, it still lexes via a String. Having said that, the performance is not at all bad, on a 3Ghz box it does ~20k lines/sec. * The parser error messages are terrible (it might be interesting to try porting from happy to frown for this purpose) There's probably more stuff, but that's what I can think of right now. So if anyone is interested then let me know, I can give some pointers (hopefully the useful kind, not the void * kind). You can get the code from the c2hs darcs repo: darcs get --partial http://darcs.haskell.org/c2hs/ The C parser bits are under c2hs/c/ Duncan Licensing: It's not 100% clear. At the moment it's marked as GPL, but it's derived from several sources so we need to be careful about that. Personally I'm happy to use LGPL. It derives from c2hs obviously, which is GPL, though we could enquire about re-licencing, especially since there is very little of c2hs stuff used in it any more. It also derives partly from James A. Roskind's C grammar (in particular the grammar of declarations). His copyright license is fairly liberal but this need double-checking. It also derives from the C99 spec and I read the comments in the gcc C parser as a guide to GNU C's extensions to the C grammar (no code or comments were copied however). Testing: I tested it thus far by writing a little gcc wrapper script, so you can build any ordinary bit of C software using this wrapper and it'll call gcc with the same args but it'll also try and parse the input file. It reports into a log file. I've not tried the gcc C parser testsuite. This approach is probably good for other tests like trying to see if parsing and pretty printing can round-trip correctly; if not identical token streams (since parsing drops redundant brackets etc) checking if gcc produces identical .S/.o files. Something that c2hs needs is to calculate sizes of types and structure member offsets correctly. This is also something that could be tested in this style, by comparing on thousands of example .c files with what gcc thinks.

4 4

QuickCheck subsumes unit testing
by dons＠cse.unsw.edu.au 21 Apr '07

21 Apr '07

Just to walk the walk, and not just talk the talk, here's a quick unit testing 'diff' driver I hacked up for QuickCheck. When run, it 'diffs' (well, just prints ;-) the incorrect values from the unit test: $ runhaskell T.hs sort unit test : Falsifiable after 0 tests: - [1,2,3] + [1,3,2] >From a normal QC specification like: prop0 = (sort [3,2,1], [1,3,2]) main = mapM_ (\(s,a) -> printf "%-25s: " s >> a n) tests where n = 100 tests = [("sort unit test", mytest prop0)] The full driver code is attached. It is just proof of concept, but you can see how to extend it to be smarter/prettier. Note that we actually probably want to use SmallCheck here, to prevent bogus repetition of the test. (I.e. 500 tests all passed, for a unit test). Note also, the driver would need further extending, since we've changed the structure of the Testable values. Cheers, Don

2 1

Re: [Haskell-cafe] Program optimisation
by David Roundy 21 Apr '07

21 Apr '07

On Fri, Apr 20, 2007 at 08:33:41PM +0100, Andrew Coppin wrote: > >Indeed, unboxed arrays are much nicer, but the whole Array batch of the > >standard library is pretty useless, in my experience. You can roll your > >own relatively easily using ForeignPtr, similar to Data.ByteString, but > >that's a bit of a pain. > > There is no *way* I'm playing with C. The entire point of Haskell is to > allow mankind to eradicate C forever. :-) ForeignPtr doesn't have anything to do with C, it's just the data structure you need to use if you want to write your own unboxed array. > I was more interested in seeing people's comments about the program > changes. For example, why would an in-place update be slower than lots > of dynamically-allocated lists? That's totally counterintuitive. Also, > is there any way in hell I can make the program stricter without > mutilating the entire thing to use unboxed arrays? I couldn't figure out > a way to do this. (Would be nice if there was a compiler switch to just > turn off all laziness - but as far as I can tell, there isn't.) The in-place update (without boxing) still dynamically allocates thunks, which are similar in cost to cons cells (for some definition of similar). Unboxed arrays are exactly what you want--except that the UArray type is limited, which is why I recommended rolling your own. Hopefully the PArr package will help reduce the pain of using arrays. In any case, in my opinion Haskell desperately needs more strict data types, as strict types can go a long way towards eliminating all sorts of pain. I remember once going through all sorts of pain trying to avoid stack overflows when using Data.Map to compute a histogram, which all would have been avoided if there were a strict version of Data.Map (or even just strict functions on the lazy Data.Map). I don't think eliminating all laziness is a good idea, but (optional) strict datatypes most certainly are, as they can go a very long ways towards eliminating memory leaks. -- David Roundy Department of Physics Oregon State University

3 6

Why Mathematical Soundness Matters.
by Vivian McPhail 21 Apr '07

21 Apr '07

Hi All, This is in regard to previous posts about mathematical preludes. > class Set a > > class (Set s) => SemiGroup s o where > semigroup_op :: o -> (s,s) -> s > -- closure > -- associative > > class (SemiGroup s o) => Monoid s o where > identity :: o -> s > > class (Monoid s o) => Group s o where > inverse :: o -> s -> s > > class Optimisable a where > cost :: Set b => a -> b First, consider a semigroup, which is a set with an associative operation. Into this structure falls Matrices with multiplication. There is scope for optimisation of a series of multiplications. Inductively for each m1 * m2 * m3 compare the cost of m1 * m2 versus m2 * m3 which can be simply obtained from the size of the index of the matrix. Thus expressions like (14,3) x (3,15) x (15,2) can be computed as (14,3) x ((3,15) x (15,2)) and not in a more expensive way. Furthermore, if we tag identities with a phantom type, we can eliminate needless operations like 3 + 0. Not as much optimisation can be achieved with inverses (3 + -3) because it might be just as expensive to calculate that something is an inverse as to do actual calculation. So how can this optimisation be performed? Well this is a question that I put forward to you, Gentle Reader. Static: It seems to me that expressions the types of which are known at compile-time can be optimised by using type-level programming in combination with compiler rewrite rules, e.g. if we have a type class SizeLarger then the expression > semigroup_op (semigroup_op m1 m2) m3 can be rewritten as > semigroup_op m1 (semigroup_op m2 m3) depending upon the SizeLarger types of the various (semigroup_op _ _) function calls. Another method is to manipulate the expressions as ASTs and convert to the concrete using TH. But what about dynamic data? Dynamic: These are terms whose types are not known until run-time (such as would happen when loading an arbitrary matrix from a file). In this case we can't use compiler term-rewriting or TH, but what options are there? Depending upon the speed/complexity of type-checking versus computation would it not be feasible to use run-time type checking (a polymorphic Dynamic type) to achieve this optimisation? Yes there is a lot to said in favour of static type-checking, but there are cases in which it is not feasible, witness type-level bounds checking of run-time loaded matrices of unknown shape. In a program that used run-time typechecking (yes there would be a computational overhead) the dynamic stuff would be isolated from the 'trusted' statically checked program and values could only be injected through trusted entry points (e.g. get4SquareDoubleMatrix :: Dynamic -> IO (Array ((D4 $ Sz),(D4 $ Sz)) Double). In any case, writing 'simple' arithmetic expressions would become more cumbersome because of the overhead of annotating types and possibly moving between ASTs and the concrete. But if we a had collection of mathematically sound classes like SemiGroup, Monoid, Group, Field, etc... then these optimisations could be built into the compiler and we could sugar the programmer-side just as it has been for Monads. In conclusion, I put this forward as a reason for Mathematically Meaningful Numeric Classes and in obiter I am putting forward support for polymorphic Dynamic types (run-time typechecking). Cheers, Vivian

1 0

Re: how would Albus Dumbledore sell Haskell
by Greg Meredith 20 Apr '07

20 Apr '07

Simon, Regarding Justin Bailey's idea of a calculator -- here's a twist. There is some sample Haskell code of Conway's account of numbers as games floating around the internet (http://www.dcs.ed.ac.uk/home/pgh/conway.html, http://www.dcs.ed.ac.uk/home/pgh/Conway.lhs) i can't vouch for the code as i have not read it in anger. However, i've always thought it would be fun to do the standard calculator example, but with Conway games on the back end for doing the arithemetic. Some of the attractions: - you could have another set of buttons for displaying the games respresentation of the numbers - you could really emphasize the polymorphism of the basic operations - you could emphasize the use of laziness for calculations involving infinitary entities - you could explain Conway games (which are an intellectual treat for those who never seen them and just get better and better the more you return to them) Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

1 0