- Haskell-Cafe - Haskell.org

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 21 Apr '07

21 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

fftw bindings
by Fawzi Mohamed 20 Apr '07

20 Apr '07

Hi everybody, I was wondering if someone had fftw bindings for haskell, or if I should roll my own. I did a small search but found nothing. Fawzi

8 11

Writing guards shorthand
by Joel Reymont 20 Apr '07

20 Apr '07

Support I want to infer the type given an Op that looks like this (incomplete): data Op = Minus | Plus | Mul | LT | GT Is there a shorthand way of bunching Minus, Plus and Mul in a function guard since they all result in TyNum whereas the rest in TyBool? I really don't want several function clauses and neither do I want separate guards for every constructor. Thanks, Joel -- http://wagerlabs.com/

7 11

Vacancy for a PhD student
by Johan Jeuring 20 Apr '07

20 Apr '07

(Knowledge of Haskell is a big plus; implementation of most of the tools will be done in Haskell.) Vacancy: PhD student in the Strategy Feedback project 1+3 years, Open University the Netherlands, location: Heerlen (preference). The project: In many subjects students have to acquire procedural skills. Problems in mathematics are often solved using a standard procedure, such as for example solving a system of linear equations by subtracting equations from top to bottom, and then substituting variables from bottom to top. Problems in computer science, physics, chemistry, electrotechnics, and other subjects, often require procedural skills as well. Furthermore, procedural skills appear at any educational level. E-learning systems offer excellent possibilities for practicing procedural skills. The first explanations and motivation for a procedure that solves a particular kind of problems are probably best taught in a class room, or studied in a book, but the subsequent practice can often be done behind a computer. There exist many e-learning systems or intelligent tutoring systems that support practicing procedural skills. The tools vary widely in breadth, depth, user-interface, etc, but, unfortunately, almost all of them lack sophisticated techniques for providing immediate feedback. If feedback mechanisms are present, they are hard coded in the tools, often even with the exercises. This situation hampers the usage of e-learning systems for practicing procedural skills. This project aims to investigate techniques for providing flexible and immediate feedback in tools that support practicing procedural skills. We want to use advanced techniques from computer science, taken from fields such as term rewriting, strategies, error-correcting parsers, and generic programming to provide feedback at each intermediate step from the start towards the solution of an exercise. We want to further develop some of these techniques, and apply and experiment with them in the domain of e-learning systems. Our goal is to obtain e-learning systems that give immediate and useful feedback. We will cooperate on this project with the Software Technology group from Utrecht University. Requirements: University degree in Computer Science. Good knowledge of functional programming, and several advanced computer science techniques. Knowledge of parsing, rewriting, strategies, generic programming, etc. will be useful. More information about the project can be found on http://ideas.cs.uu.nl/wiki/index.php/IDEAS:StrategicFeedback or contact Johan Jeuring (johanj(a)cs.uu.nl, +31 6 40010053). To apply: send a letter and your curriculum vitae before May 5, 2007 to: Open Universiteit Nederland, afdeling Personele ondersteuning, Postbus 2960, 6401 DL Heerlen. U kunt ook or an e-mail to: martin.vanloo(a)ou.nl Mention vacancynr FAC/INF/07024 In both cases, please cc Johan Jeuring (johanj(a)cs.uu.nl)

1 0

Morphing ASTs and scrapping boilerplate code
by Joel Reymont 20 Apr '07

20 Apr '07

Folks, I'm transforming ASTs as part of my compiler from one language into another. The source AST is a list of statements whereas the target AST is a "class definition". type Object a = State Obj a data Obj = Object { objSym :: Integer -- starting # for gensym , objVars :: M.Map String VarDecl , objProps :: M.Map String PropDecl , objMeths :: M.Map String MethodDecl } deriving (Show, Eq) I'm using a state monad and the transformations are supposed to update the state (object) as needed to add variables, methods, etc. class Morpher a b | a -> b where morph :: a -> Object b I have a lot of boilerplate code like this and wonder how I can scrape it. instance Morpher Type C.Type where morph TyInt = return C.TyInt morph TyFloat = return C.TyFloat morph TyStr = return C.TyStr morph TyBool = return C.TyBool morph TyColor = return C.TyColor morph TyStyle = return C.TyStyle morph (TyList ty) = liftM C.TyList (morph ty) morph (TyArray ty) = liftM C.TyArray (morph ty) morph (TySeries ty) = liftM C.TySeries (morph ty) morph (TyInput ty) = liftM C.TyProp (morph ty) morph (TyRef ty) = liftM C.TyRef (morph ty) morph TyUnit = return C.TyUnit morph TyPrintDest = return C.TyPrintDest Notice that I'm calling a constructor of the same name in a different module ... unless it's an exception. instance Morpher BackRef C.Expr where morph Now = C.Int 0 morph (BarsBack e) = morph e instance Morpher DataRef C.Expr where morph (DS x) = C.Int x How can I reduce the boilerplate here? Thanks, Joel -- http://wagerlabs.com/

2 2

First order Haskell without Data
by Neil Mitchell 19 Apr '07

19 Apr '07

Hi, I've been wondering what is essential to Haskell and what isn't. Not from a point of view of what could be removed from the language, but what could be removed from a Core language. Given the features of higher-order, laziness and data types: Laziness can be converted to higher-order functions Data types can be converted to higher-order functions Higher-order functions can be converted to Data So as far as I can see it we have left: {data-types only} {higher-order functions only} But we don't have laziness only, so my question is if it is possible to represent all of Haskell in a first-order language without data types, but with laziness. If its possible to do so in a strict first-order language without data types, then I'd also be interested. Are any of these known results? Thanks Neil References: * data types -> higher order is in "Efficient Interpretation by Transforming Data Types and Patterns to Functions" http://www.cs.nott.ac.uk/~nhn/TFP2006/Papers/03-JansenKoopmanPlasmeijer-Eff… * laziness -> functions, functions -> data is in "Definitional Interpreters for Higher-Order Programming Languages" http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf

4 4

Parallel executing of actions
by Mitar 19 Apr '07

19 Apr '07

Hi! Is there a parallel version of mapM_? Like it is for map (parMap)? I would like to execute actions in parallel as the computation of necessary data for actions is quite computational heavy. But it does not matter in which order those actions are executed. (I am rendering pixels with OpenGL and it does not matter in which order I draw them, but it matters that for one pixel it takes some time to calculate its color.) The example would be: main :: IO () main = do -- the order of printed characters is not important -- instead of putStrLn there will be a computationally big function -- so it would be great if those computations would be done in parallel -- and results printed out as they come mapM_ rwhnf (putStrLn) ["a","b","c","d"] Is this possible? Without unsafe functions? And without changing the semantics of the program. Mitar

9 13

RE: [Haskell] haskell question
by Simon Peyton-Jones 19 Apr '07

19 Apr '07

[Redirecting to Haskell Cafe] Hi Greg I think it's very likely that you *can* do what you want. I have not taken long enough to understand just what you are trying to do, but I do know why your program is failing, and I think you'll agree it *should* fail. Look at these lines (slightly simplified) class CoreAgentSyntax x where offer :: (CoreProcessSyntax p) => [n] -> (p a x) -> x data MinimalAgentSyntax nn pp = Concretion [nn] pp instance CoreAgentSyntax (MinimalAgentSyntax nn pp) where offer = Concretion The class decl says that every instance of 'offer' must have type forall p, forall n, forall a. (CoreProcessSyntax p) => [n] -> p a x -> x where x is the instance type. Not the "forall n"! Even once x is fixed, we must have a function that is polymorphic in n,p,a But in your instance declaration, offer = Concretion has the type [nn] -> pp -> MinimalAgentSyntax nn pp No for-alls, because the whole instance decl binds the 'nn'. Hence it's just not polymorphic enough. I'm not sure how to fix your problem. Perhaps you need another argument for CoreAgentSyntax? class CoreAgentSyntax n x where offer :: (CoreProcessSyntax p) => [n] -> (p a x) -> x instance CoreAgentSyntax nn (MinimalAgentSyntax nn pp) where offer = Concretion now you are in better shape. There's another problem because you use 'p' with kind * in some places and (*->*->*) in others, but thats a separate issue. Oleg is good at this kind of stuff. Simon From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Greg Meredith Sent: 18 April 2007 14:53 To: haskell(a)haskell.org Subject: [Haskell] haskell question Haskellians, In the attached file i have implemented the bare bones core of the syntax -- pre structural equivalence -- of Milner's presentation of \pi via abstractions and concretions. (There's a minor twist in that the notion of location affords more structure than in Milner's original presentation which i have added to support an ultimate probabilistic interpretation.) The file compiles with ghc as is. If you uncomment the last section, however, you see that to close the loop on the constraints for the agent syntax we hit a typing error. i think this is a hard constraint in Haskell that prevents this level of generality in the specification, but maybe you can see a way around it. i'm certainly no Haskell expert. Best wishes, --greg P.S. The reason for this level of generality is that with it you can close the loop and form a mutual recursion between the types for the syntax of processes and the type of names -- without having that choice predesigned into the structure of processes (or names). i can do this trick in OCaml with recursive modules, but it's definitely not pretty. i was hoping Haskell could make it pretty. -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

1 0

Re: Type classes and type equality
by oleg＠pobox.com 19 Apr '07

19 Apr '07

Neil Mitchell wrote: > I'm looking for a type class which checks whether two types are the > same or not. This problem is more complex than appears. It has been solved, however. IncoherentInstances are not required, as IncoherentInstances are generally unsafe. For the full discussion of various solutions, please see Section 9 and Appendix D of the HList paper: http://homepages.cwi.nl/~ralf/HList/paper.pdf The HList code is available http://darcs.haskell.org/HList/ It includes the examples from the paper.

3 5

Fwd: [Haskell-cafe] Transpose using array comprehension
by Chris Witte 19 Apr '07

19 Apr '07

I was trying to use the array comprehension of the Data Parallel Haskell package. http://haskell.org/haskellwiki/GHC/Data_Parallel_Haskell for instance I can define {-# OPTIONS -fparr -fglasgow-exts #-} module MatTest where import GHC.PArr ident = [:[:1,0:],[:0,1:]:] aVect = [:4,5:] dotP :: Num a => [:a:] -> [:a:] -> a dotP xs ys = sumP [:x * y | x <- xs | y <- ys :] matVecMul :: Num a => [:[:a:]:] -> [:a:] -> [:a:] matVecMul xs ys = [:dotP x ys | x <- xs:] but when I tried to define a matrix matrix multiplication matMel :: Num a => [:[:a:]:] -> [:[:a:]:] -> [:a:] I was at a loss for how to do it because i couldn't define transpose. On 4/18/07, Henning Thielemann <lemming(a)henning-thielemann.de> wrote: > > On Wed, 18 Apr 2007, Chris Witte wrote: > > > I just started playing around with GHC.PArr and array comprehension > > and I was wondering if there is a way to define the transpose of a > > matrix using array comprehension? > > Why not > > let swap :: (i,j) -> (j,i) > swap (a,b) = (b,a) > in ixmap (let (lower,upper) = bounds arr in (swap lower, swap upper)) > swap arr > > ? >

1 0

Re: [Haskell-cafe] question about Data.Binary and Double instance
by Duncan Coutts 19 Apr '07

19 Apr '07

On Wed, 2007-04-18 at 08:34 -0700, Bryan O'Sullivan wrote: > Duncan Coutts wrote: > > > I'm currently exploring more design ideas for Data.Binary including how > > to deal with alignment. Eliminating unnecessary bounds checks and using > > aligned memory operations also significantly improves performance. I can > > get up to ~750Mb/s serialisation out of a peak memory bandwidth of > > ~1750Mb/s, though a Haskell word-writing loop can only get ~850Mb/s. > > What are you using to measure the peak number? It seems very low to me. > Even Opterons of a few years of vintage can manage more than 5GB/s. I was using a C word writing loop with no unrolling. On x86 that turned into a 4 asm instruction loop. Reading words is indeed a good deal faster, and on my x86-64 machine reading 8-byte words is faster still. > It's also quite normal to get about half of your peak bandwidth unless > you're going out of your way to use non-temporal loads and stores (e.g. > via SSE2), which is something that e.g. gcc is not good at at all, if > you're using -fvia-c. I'm not interested so much in the peak throughput of the machine as what could be realistically achievable for binary serialisation. So comparing to a non-unrolled C loop seems fair to me. With sufficient improvements in the GHC backend we should be able to approach that. Then any difference is overhead in the Binary library, and that's what I'm really trying to measure. Duncan

1 0

Soft references
by Benja Fallenstein 19 Apr '07

19 Apr '07

Hi all, Is there a way to achieve the effect of soft references in GHC? Or if not, is there any hope that they will be implemented in the future? (Soft references are like weak references, except that they are only reclaimed by the garbage collector if memory is short.) I'm building a memoization table of visualizations of a data set, but I can't store *all* visualizations of that set in memory at the same time. My current solution is to use a least-recently-used cache, but this is unsatisfying because I have to specify the maximum number of objects in the cache; if I make that too large, I run out of memory, so I have to make it so small that I can't possibly run out, meaning that I have to make it a lot smaller than it *could* be. With soft references, the program could memoize the "optimal" number of items, with the user being able to influence the behavior through the 'maximum heap size' RTS option. Any ideas? Thanks, - Benja

2 1

FW: [Haskell-cafe] Tutorial on Haskell
by Taillefer, Troy (EXP) 19 Apr '07

19 Apr '07

=======================LONG WINDED RANT WARNING ====================================== I am not try to hate on Haskell obviously I am a fan otherwise I wouldn't be on this list but criticizing other languages is not only a pointless waste of time it is logically flawed on many levels. A lot of the best software is written and still being written in C++ so I will have to disagree with you that C++ is unreasonable. C++ is dangerous and has its flaws especially in the hands of a noob but it is also has some merits as well. People have very logical reasons for choosing a programming language including 1. Familiarity 2. Available people to work with 3. Tools 4. Libraries 5. Legacy 6. Political 7. Personal Preference etc... In terms of reasoning it is easier to reason in a language/Paradigm that you are familiar with than one that might be better but you are totally unfamiliar with and must learn from scratch. Go on IRC #HASKELL and see how many people are struggling conceptual ideas like Monads, Arrows and Functors I don't go there a lot but every time I am there are a couple of people who are asking questions like just what is a Monad. For myself I want to learn Category Theory because it seems powerful just like Set Theory (which I have found extremely useful). I find manipulating pointers and mutable variables much easier to understand and saner. Maybe if I was a mathematician instead of an Engineer/Computer Scientist I would feel different. Saying Haskell is better and everyone should use it because it is better is about as futile as saying we should all be speaking Esperanto because it is better then English. You would be an awfully lonely person with almost nobody to talk to if all you spoke was Esperanto or Haskell for that matter. I have yet to meet face to face another person who has even written toy code in Haskell let alone any real significant app. I can't use Haskell at work because no one could maintain it. I can't use Haskell in my graduate studies since my supervisor can't read Haskell. So I am stuck writing toy code as a hobby and an educational experience. Programs are mostly for humans to read and modify and lets face it there isn't a lot of people fluent in Haskell. So if I want to work and interact with other Software professionals I better be able to speak the lingua franca which is a derivative of C aka C/C++/C#/Java ect. Obviously C++ isn't that bad because people can write good cool software in it. I like Haskell but I haven't seen a ton of Killer Haskell apps yet ( Or even one for that matter). DARCS is coming close if they fix their conflict problems then Haskell will have its first killer app that I know off. I heard they are working on it this summer looking forward to it DARCS is really cool. Sorry for the long rant but I get tired of people with their juvenile and unconstructive statements like "C++ sucks" Or Language X is better then Language Y even if it could ever be objectively true (which I am sorry it can't be) who cares. ============================END RANT=================================================== ________________________________ From: Sebastian Sylvan [mailto:sebastian.sylvan@gmail.com] Sent: Wednesday, April 18, 2007 1:50 PM To: Taillefer, Troy (EXP) Cc: haskell-cafe(a)haskell.org Subject: Re: [Haskell-cafe] Tutorial on Haskell On 4/18/07, Taillefer, Troy (EXP) <troy.taillefer(a)lmco.com> wrote: I have to strongly disagree with the statement that developers like to debug. Debugging is necessary because you can't reason about any "sizeable" piece of code just is not tractable even in Haskell. Now automated tools for reasoning about programs are very cool but lets face it no real world developer will sit down start to manually formally reason about large pieces of code. I think the emphasis when mentioning "reasoning" really shouldn't be "you can reason formally about your programs and prove that they don't go wrong", nor "when it has gone wrong, you can reason about the program to figure out why", it should be "since the language doesn't do batshit insane things behind your back, your programs will mostly work the first time". The "reasoning" isn't an active task that you schedule time for, at least for a casual user like me, it's part of the actual programming. You do "reasoning" when writing in C++ as well, but you often get it wrong (because the language is, shall we say, unreasonable?) and that causes bugs. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862

2 1

SYB and opaque types
by Joel Reymont 19 Apr '07

19 Apr '07

Suppose I need to manually derive Data and Typeable for SourcePos from Parsec to make sure my code compiles. I won't actually be running the code I manually derive since the constructor that includes SourcePos will be skipped. With Neil Mitchell's (and #haskell) help I'm doing this to strip token locations from my AST: import Data.Generics import qualified Text.ParserCombinators.Parsec as P instance Data SourcePos where gfoldl r k x = k x typename_SourcePos = mkTyCon "SourcePos" instance Typeable SourcePos where typeOf _ = mkTyConApp typename_SourcePos ([]) strip = everywhere (mkT f) where f (TokenPos a _) = a f x = x I know that the warnings about gunfold, toConstr and dataTypeOf are harmless but how would I define them to avoid the warnings? Also, the definition of strip above requires -fno-monomorphism- restriction. Should I not worry about it? The code runs just fine, locations are being stripped and tests pass. Thanks, Joel -- http://wagerlabs.com/

3 2

Re: [Haskell] ANN: Data.Proposition 0.1
by Jan-Willem Maessen 18 Apr '07

18 Apr '07

Hmm, your BDD implementation claims (in the comment at the top) that "Equality is fast and accurate." But you don't do sharing optimizations, and use derived Eq (rather than object identity), so it's exponential in the number of nodes. Consider: A / \ B | \ / C / \ D | \ / E Here there are five nodes, but we will do two calls to see if C==C, four calls to see if E==E. If I continue the diagram downwards I add two nodes and double the number of equality calls on the leaf. The sharing optimizations are rather important to making an efficient BDD implementation. I haven't yet seen a Haskell-only BDD implementation that didn't have one or more of the following flaws: 1) IO in all the result types, even though the underlying abstraction is pure. 2) Inability to garbage collect unused nodes. 3) Loss of sharing leading to loss of fast equality. Does anyone have a Haskell-only BDD library which avoids all these problems? I wrote one with flaw #2, but was unable to make weak pointers and finalization behave in anything like a sensible fashion and gave up as it was a weekend project. The concurrency + unsafePerformIO mix was trickier than I initially expected, too. That said, this BDD implementation is pretty similar to the performance & behavior you'd get from Data.IntSet (where the bits of your int correspond to the True/False values of your variables). -Jan-Willem Maessen On Apr 16, 2007, at 9:07 AM, Neil Mitchell wrote: > Hi, > > I am now releasing Data.Proposition. This library handles > propositions, logical formulae consisting of literals without > quantification. It automatically simplifies a proposition as it is > constructed using simple rules provided by the programmer. > Implementations of propositions in terms of an abstract syntax tree > and as a Binary Decision Diagram (BDD) are provided. A standard > interface is provided for all propositions. > > Website: http://www-users.cs.york.ac.uk/~ndm/proposition/ > Darcs: darcs get --partial http://www.cs.york.ac.uk/fp/darcs/ > proposition/ > Haddock: http://www.cs.york.ac.uk/fp/haddock/proposition/Data- > Proposition.html > > The Haddock documentation also has a short example in it. > > This library is used substantially in the tool I have developed for my > PhD, and has been extensively tested. > > Thanks > > Neil > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell

3 2

Re: [Haskell-cafe] Re: Translating perl -> haskell, string "fill ins" with an error on invalid inputseems awfullycomplex. Is there a way to simplify?
by Thomas Hartman 18 Apr '07

18 Apr '07

Claus and Evan ++; that was very helpful. FWIW, my gut feeling is that Claus's first version was easier to understand than the revision with printf, which seems to me to involve a lot more monadic wizardry (Functor, MonadError, fmap, mapm). The first version, which just used maybe, was clear to me within seconds. But again, I learned a lot. Thanks.

3 6

Transpose using array comprehension
by Chris Witte 18 Apr '07

18 Apr '07

I just started playing around with GHC.PArr and array comprehension and I was wondering if there is a way to define the transpose of a matrix using array comprehension? Cheers Chris

2 1

Tutorial on Haskell
by dfeustel＠mindspring.com 18 Apr '07

18 Apr '07

What would be really useful is a Haskell Cookbook that shows how to do in Haskell things that are so easily done in imperative languages. How to solve simultaneous equations using Gaussian elimination comes to mind. Lots of examples would be great. Dave Feustel

2 1

Haskell job
by Lennart Augustsson 18 Apr '07

18 Apr '07

Hi all, Credit Suisse has started using Haskell within GMAG, the group that provides financial analytics for the bank. The main use of Haskell is for a Domain Specific Embedded Language that is being used by the people writing the financial analytics (these people typically have a PhD in mathematics or physics). We are looking to extend our Haskell group (which currently is me and Ganesh Sittampalam), so if you're an experienced Haskell person take the chance! Here's a URL to the Credit Suisse job ad: https://creditsuisse.taleo.net/servlets/CareerSection? art_ip_action=FlowDispatcher&flowTypeNo=13&pageSeq=2&reqNo=53820&art_ser vlet_language=en&selected_language=en&csNo=10020#topOfCsPage If you have any questions email Howard Mansell, howard.mansell@credit- suisse.com, or me. -- Lennart

1 0

Re: Release plans
by Brandon Michael Moore 18 Apr '07

18 Apr '07

On Tue, Apr 17, 2007 at 12:50:48PM +0200, Doaitse Swierstra wrote: > Just to show what kind of problems we are currently facing. The > following type checks in our EHC compiler and in Hugs, but not in the > GHC: > > module Test where > > data T s = forall x. T (s -> (x -> s) -> (x, s, Int)) > > run :: (forall s . T s) -> Int > run ts = case ts of > T g -> let (x,_, b) = g x id > in b Consider this additional code which also typechecks in Hugs: v :: forall s . T s v = T f f :: s -> ([s] -> s) -> ([s], s, Int) f v g = let x = [v] in (x, g x, 0) due to parametricity, run v can't depend on x or g x. Apparently id has type [x] -> x. Are EHC and Hugs supposed to support equirecursive types? Brandon

1 1

unsafeInerleaveIO and randomIO
by Marc Weber 18 Apr '07

18 Apr '07

stefan has pointed me a nice version: ============= ======================================================= randomInts :: IO [Int] randomInts = randoms `fmap` newStdGen main = do ints <- randomInts print $ take 5 ints =========== ========================================================= Anyway I'm curious why ============= ======================================================= module Main where import Data.Char import Control.Monad import Random import System.IO.Unsafe randomInts :: IO [Int] randomInts = unsafeInterleaveIO $ sequence $ cycle [unsafeInterleaveIO randomIO] main = do ints <- unsafeInterleaveIO randomInts print $ take 5 ints ============= ======================================================= doesn't return. Where did I miss another unsafeInerleaveIO to make it lazy enough? I still need a hint. Marc

3 3

implementing try for RWST ?
by oleg＠pobox.com 17 Apr '07

17 Apr '07

The examples presented so far seem to show that the computation will eventually run in the IO monad. One may wonder then why do we need RWST transformer, given that the IO monad can implement both the state and writer. At the very least me need the reader transformer, which is the least demanding monad. We can do away with the reader as well, depending on the circumstances (e.g., one may use implicit parameters or implicit configurations, or just pass IORefs). The pure IO or ReaderIO solution has, besides simplicity, the advantage of being more expressive. Monad transformers, besides inefficiency, impose the rigid layering of effects, and so cannot express some useful computations. The drawbacks of monad transformers and their limited expressivity are not often discussed, unfortunately. The following code shows Jeremy Shaw's example, with both persistent and backed out state. The combinator tryC handles the exception and preserves the state accumulated at the point of exception. In contrast, tryBC undoes the changes to the state in case of exception. Both combinators have their uses. module T where import Control.Monad.Reader import Data.IORef import Control.Exception import Prelude hiding (catch) type ReaderIO a v = ReaderT a IO v type StateIO a v = ReaderIO (IORef a) v type Counter = Integer -- |Increment the counter by 1 incIO :: StateIO Counter () incIO = do cref <- ask c <- liftIO $ readIORef cref let c' = c + 1 liftIO $ writeIORef cref c' liftIO $ putStrLn ("Incrementing counter to: " ++ show c') -- get the current value of the counter getC :: StateIO Counter Counter getC = ask >>= liftIO . readIORef -- Try that preserves the state tryC :: ReaderIO a v -> (Exception -> ReaderIO a v) -> ReaderIO a v tryC action onerr = do r <- ask liftIO $ catch (runReaderT action r) (\e -> runReaderT (onerr e) r) -- Try that backs up the state tryBC :: StateIO a v -> (Exception -> StateIO a v) -> StateIO a v tryBC action onerr = do r <- ask oldstate <- liftIO $ readIORef r liftIO $ catch (runReaderT action r) (\e -> do writeIORef r oldstate runReaderT (onerr e) r) -- The run function runC :: Counter -> StateIO Counter v -> IO v runC v a = newIORef v >>= runReaderT a test = runC 0 (do incIO v <- tryC (die >> (return $ Right "ok")) (return . Left . show) c <- getC -- get the resulting counter liftIO $ print (v,c)) where -- |increment the counter by one and then die die = incIO >> error "die!" {- *T> test Incrementing counter to: 1 Incrementing counter to: 2 (Left "die!",2) -} -- the same but with backtrackable state test2 = runC 0 (do incIO v <- tryBC (die >> (return $ Right "ok")) (return . Left . show) c <- getC liftIO $ print (v,c)) where -- |increment the counter by one and then die die = incIO >> error "die!" {- *T> test2 Incrementing counter to: 1 Incrementing counter to: 2 (Left "die!",1) -}

3 2

GHC 6.7 and Associated Types
by Maxime Henrion 17 Apr '07

17 Apr '07

Hello guys, I've been documenting myself on associated types, which look like a very nice way to deal with the problems that arise with multi-parameter type classes. As an exercise, I am trying to rewrite the MonadState type class from the mtl package without functional dependencies. Here is my (probably very naive) approach : class MonadState m where type StateType m :: * get :: m StateType put :: m StateType -> m () As for instances: instance MonadState (State s) where type StateType = s -- this is line 22 get = State $ \s -> (s, s) put s = State $ \_ -> ((), s) I think I'm probably doing some very stupid thing and missing important points. In any case, here's the error I get : State.hs:22:19: Not in scope: type variable `s' Failed, modules loaded: none. I'd be happy to be explained why this doesn't make sense, and how I should proceed to implement this correctly. I have tried various other approaches with no luck yet. Thanks, Maxime

3 6

>> and sequencing [newbie]
by David Powers 17 Apr '07

17 Apr '07

so... this is likely a question based on serious misunderstandings, but can anyone help me understand the exact mechanism by which monads enforce sequencing? Specifically, I'm confused by the >> operator. If I understand things properly f a >> g expands to something like: f >>= \_ -> g What I'm missing is how the expansion of f is ever forced under lazy evaluation. Since the result is never used, doesn't it just stay as a completely unevaluated thunk? Come to think of it... how is it that some IO actions sequence completely, while others manage to work in a lazy manner? My suspicion is that somehow the order of evaluation in Haskell gives the outermost expression a "first crack" at evaluation in all circumstances (e.g. http://users.aber.ac.uk/afc/stricthaskell.html#cps) , but that it somehow stops short of a forced deep sequencing... Which is all to say, I have no idea how the magic happens. -David

5 7

Efficient use of ByteString and type classes in template system
by Johan Tibell 17 Apr '07

17 Apr '07

Hi Haskell Café! I'm writing a perl/python like string templating system which I plan to release soon: darcs get http://darcs.johantibell.com/template The goal is to provide simple string templating; no inline code, etc.. An alternative to printf and ++. Example usage: > import qualified Data.ByteString as B > import Text.Template > > helloTemplate = "Hello, $name! Would you like some ${fruit}s?" > helloContext = [("name", "Johan"), ("fruit", "banana")] > > test1 = B.putStrLn $ substitute (B.pack helloTemplate) helloContext I want to make it perform well, especially when creating a template once and then rendering it multiple times. "Compiling" the template is a separate step from rendering in this use case: > compiledTemplate = template $ B.pack helloTemplate > > test2 = B.putStrLn $ render compiledTemplate helloContext A template is represented by a list of template fragments, each fragment is either a ByteString literal or a variable which is looked up in the "context" when rendered. > data Frag = Lit ByteString | Var ByteString > newtype Template = Template [Frag] This leads me to my first question. Would a lazy ByteString be better or worse here? The templates are of limited length. I would say the length is usually between one paragraph and a whole HTML page. The Template data type already acts a bit like a lazy ByteString since it consists of several chunks (although the chunck size is not adjusted to the CPU cache size like with the lazy ByteString). Currently the context in which a template is rendered is represented by a type class. > class Context c where > lookup :: ByteString -> c -> Maybe ByteString > > instance Context (Map String String) where > lookup k c = liftM B.pack (Map.lookup (B.unpack k) c) > > instance Context (Map ByteString ByteString) where > lookup = Map.lookup > > -- More instance, for [(String, String)], etc. I added this as a convenience for the user, mainly to work around the problem of not having ByteString literals. A typical usage would have the keys in the context being literals and the values some variables: > someContext = Map.fromList [("name", name), ("fruit", fruit)] I'm not sure if this was a good decision, With this I'm halfway to the (in)famous Stringable class and it seems like many smarter people than me have avoided introducing such a class. How will this affect performace? Take for example the rendering function: > render :: Context c => Template -> c -> ByteString > render (Template frags) ctx = B.concat $ map (renderFrag ctx) frags > > renderFrag :: Context c => c -> Frag -> ByteString > renderFrag ctx (Lit s) = s > renderFrag ctx (Var x) = case Text.Template.lookup x ctx of > Just v -> v > Nothing -> error $ "Key not found: " ++ (B.unpack x) How will the type dictionary 'c' hurt performance here? Would specializing the function directly in render help? > render (Template frags) ctx = B.concat $ map (renderFrag f) frags > where f = flip Text.Template.lookup ctx > > renderFrag f (Var x) = case f x of I can see the implementation taking one of the following routes: - Go full Stringable, including for the Template - Revert to Context = Map ByteString ByteString which was the original implementation. - Some middle road, without MPTC, for example: > class Context c where > lookup :: ByteString -> c ByteString ByteString -> Maybe ByteString This would allow the user to supply some more efficient data type for lookup but not change the string type. Having a type class would allow me to provide things like the possibility to create a Context from a record where each record accessor function would server as key. Something like: > data Person { personName :: String, personAge :: Int } would get converted (using Data?) to: > personContext = [("personName", show $ personName aPerson), > ("personAge", show $ personAge aPerson)] but not actually using a Map but the record itself. I guess my more general question is: how do I reason about the performance of my code or any code like this? Are there any other performance improvements that could be made? Also, I would be grateful if someone could provide some feedback on the implementation, anything goes! I still have some known TODOs: - Import error messages for invalid uses of "$". - Improve the regex usage overall. - Add some more functions; the plan is to add those function which could be expressed in efficiently with the current interface. An example is things like renderAndWrite, when writing doing a B.concat first is unnecessary. Cheers, Johan Tibell

3 3

multithreading speedup
by Fawzi Mohamed 17 Apr '07

17 Apr '07

I was trying to speed up a program that I wrote and so I thought about using multiple threads. I have a quite easy parallel program and I did the following do subRes <- MVar.newMVar [] putStrLn "starting threads" subV <- flip mapM [0 .. (nThreads - 1)] $ ( \i -> do subR <- MVar.newEmptyMVar let writeRes r = do { MVar.putMVar subR r } forkOS (do let r=eval (startData !! i) writeRes $! r putStr $ "writtenRes") return subR ) putStrLn "started threads" toFold <- mapM MVar.takeMVar subV putStrLn "about to fold" return $ foldl1 mergeRes toFold I know that the threads really calculate what I want, and as soon as they are finished I get the result. The problem is that I have no speed up, the time is basically the sum of the time for the two threads. I thought that ghc now would take advantage of the two cpus if I compiled with -threaded. Am I wrong, do I need some special flag, a newer version of the compiler (I have 6.6.20070129), or it is just normal? Thanks Fawzi

4 7

Partial parsers in Happy
by Juan Carlos Arevalo Baeza 17 Apr '07

17 Apr '07

Hi! I'm trying to use a partial monadic parser with Happy (using %partial %monad and %lexer). The problem is that the parser function always seems to eat up one token beyond the matched sequence regardless of what I do. So I can't, for instance, call the parser multiple times to parse a series of blocks, because after the first block is done, it misses the first token of the second block. I'm sure this has to have come up for someone before, but I've been unable to find any references. JCAB

2 2

Re: [Haskell-cafe] implementing try for RWST ?
by tpledger＠ihug.co.nz 17 Apr '07

17 Apr '07

Jeremy Shaw wrote: : | However, I think this is buggy, because changes | to 's' and 'w' will be lost if 'm' raises an | exception. : That's determined by the way you stack your monad transformers when declaring the type: adding error handling to a writer monad, or adding writing to an error handling monad. For a concrete example, see the result types in the following. The first has the Either inside the tuple, and the second has the tuple inside the Either. Prelude> :t Control.Monad.Writer.runWriter . Control.Monad.Error.runErrorT Control.Monad.Writer.runWriter . Control.Monad.Error.runErrorT :: Control.Monad.Error.ErrorT e (Control.Monad.Writer.Writer w) a -> (Either e a, w) Prelude> :t either Left Right . Control.Monad.Writer.runWriterT either Left Right . Control.Monad.Writer.runWriterT :: Control.Monad.Writer.WriterT w (Either a) a1 -> Either a (a1, w) Regards, Tom

2 1

Re: [web-devel] A light-weight web framework
by Ricardo Herrmann 17 Apr '07

17 Apr '07

The maintenance nightmare happens when someone uses the embedded language to specify business logic, and that's entirely the web-{developer,designer}'s fault. Thus, the problem is not that these languages shouldn't be powerful enough. IMHO, a safe approach would be simply not allowing I/O inside templates (hey, sounds familiar ;-) On 4/5/07, Maurice Codik <maurice.codik(a)gmail.com> wrote: > > A few things, some of which I sort of mentioned in my previous email: > > - If I'm already going to commit some time to learn a templating language, > why dont I just spend that same amount of time learning the little bit of > haskell I need to make the template work? If thats too much to ask, I can > just spit out HTML, and have the programmer put in the dynamic parts for me. > Both of these scenarios seem to be a more efficient use of time. > > - Who is the target audience? If its a big organization where there are > multiple designers and multiple devs, then your approach may work just fine. > If its the single developer, then something like what David suggested would > work even better. If its a small team (which may or may not include a > full-time designer), then something like what I suggested would work best. > For a web framework for haskell, I would guess that the latter two are much > more likely. > > - Embedding a real programming language in a template already gives you > power to do what ever you need to do. What if you need to implement some > logic that the template language doesnt support? In those cases, you're > usually out of luck and have to move that logic into a controller, where it > doesnt really belong (assuming its actual display logic, not business > logic). > > - It's really just a matter of taste. Any web framework thats worth using > should be flexible in its support of view technologies, but come with one > thats a sensible default. > > Maurice > > On 4/5/07, Joel Reymont <joelr1(a)gmail.com> wrote: > > > > Do you see anything wrong with the approach I suggested, though? > > > > On Apr 5, 2007, at 6:16 PM, Maurice Codik wrote: > > > > > That's not necesarily true. Templates where there is mostly markup, > > > but let you embed code into them using special tags (ex, <% code % > > > >) are extremely popular and work fairly well. They also keep the > > > template language simple because there is already a full-powered > > > programming language thats embedded into it. Good examples of this > > > method are ERB templates in Rails, JSPs, Perl Mason templates, etc. > > > > -- > > http://wagerlabs.com/ > > > > > > > > > > > > > > > -- > http://blog.mauricecodik.com > _______________________________________________ > web-devel mailing list > web-devel(a)haskell.org > http://www.haskell.org/mailman/listinfo/web-devel > > -- Ricardo Guimarães Herrmann "Any sufficiently complicated C or Fortran program contains an ad hoc, informally specified, bug-ridden, slow implementation of half of Common Lisp" "Any sufficiently complicated Lisp or Ruby program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Haskell"

5 5

Fwd: [Haskell-cafe] Tutorial on Haskell
by Ryan Dickie 17 Apr '07

17 Apr '07

Blast.. i didn't hit "reply all" so here's a forward of my mail to the group... --ryan ---------- Forwarded message ---------- From: Ryan Dickie <goalieca(a)gmail.com> Date: Apr 16, 2007 4:24 PM Subject: Re: [Haskell-cafe] Tutorial on Haskell To: Simon Peyton-Jones <simonpj(a)microsoft.com> I can tell you what me and my colleagues would be interested in (though none of us are actually going). We code a lot of math. You may call it scientific computing. Haskell seems like a natural fit for the task. In particular we are interested in: 1) the type system 2) concurrency (can these be set to run on a large system) 3) simple relation between what equations we write on paper, and what equations we write in haskell. I'm still a n00b to Haskell. For us languages like matlab, maple, etc. do not fit the job very well and run too slowly. C/C++ is usually what i use but it can be a pain. Python, etc... well its good for the glue i suppose. Haskell might fit that niche. On 4/16/07, Simon Peyton-Jones <simonpj(a)microsoft.com> wrote: > > Friends > > I have agreed to give a 3-hr tutorial on Haskell at the Open Source > Convention 2007 > http://conferences.oreillynet.com/os2007/ > > I'm quite excited about this: it is a great opportunity to expose Haskell > to a bunch of smart folk, many of whom won't know much about Haskell. My > guess is that they'll be Linux/Perl/Ruby types, and they'll be practitioners > rather than pointy-headed academics. > > One possibility is to do a tutorial along the lines of "here's how to > reverse a list", "here's what a type is" etc; you know the kind of > thing. But instead, I'd prefer to show them programs that they might > consider *useful* rather than cute, and introduce the language along the > way, as it were. > > So this message is to ask you for your advice. Many of you are exactly > the kind of folk that come to OSCON --- except that you know Haskell. So > help me out: > > Suggest concrete examples of programs that are > * small > * useful > * demonstrate Haskell's power > * preferably something that might be a bit > tricky in another language > > For example, a possible unifying theme would be this: > http://haskell.org/haskellwiki/Simple_unix_tools > > Another might be Don's cpu-scaling example > http://cgi.cse.unsw.edu.au/~dons/blog/2007/03/10<http://cgi.cse.unsw.edu.au/%7Edons/blog/2007/03/10> > > But there must be lots of others. For example, there are lots in the blog > entries that Don collects for the Haskell Weekly Newsletter. But I'd like > to use you as a filter: tell me your favourites, the examples you find > compelling. (It doesn't have to be *your* program... a URL to a great blog > entry is just fine.) Of course I'll give credit to the author. > > Remember, the goal is _not_ "explain monads". It's "Haskell is a great > way to Get The Job Done". > > Thanks! > > Simon > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

Re: `Expect'-like lazy reading/Parsec matching on TCP sockets
by Scott Bell 17 Apr '07

17 Apr '07

Ooops! It seems that this doesn't behave well with a -threaded RTS. I get an EOF on handles that I know for a fact shouldn't be receiving them. It still works well without -threaded, but does anyone know why I'm getting this behavior? hGetContentsTimeout :: Handle -> Int -> IO String hGetContentsTimeout h t = do hSetBuffering stdin NoBuffering ready <- hWaitForInput h t if (not ready) then return [] else do c <- hGetChar h s <- unsafeInterleaveIO (hGetContentsTimeout h t) return (c:s) (I did add EOF checking, but all that did was return the end of the list earlier than I wanted)

3 4

Type classes and type equality
by Neil Mitchell 17 Apr '07

17 Apr '07

Hi, I'm looking for a type class which checks whether two types are the same or not. My first guess is: class Same a b where same :: a -> b -> Bool instance Same a a where same _ _ = True instance Same a b where same _ _ = False In Hugs this seems to work with overlapping instances (not requiring unsafe overlapping instances). GHC requires {-# LANGUAGE MultiParamTypeClasses, IncoherentInstances #-} So my question is if this is safe? Will the compiler always pick the "right one"? Is there a better way to do this? The alternative I thought of is using Typeable, but this is not supported particularly well on Hugs (no deriving Typeable) and would require modifications to the existing data structures (additional derivings) so is not such a good choice. Thanks Neil

3 2

Re: [Haskell-cafe] Tutorial on Haskell
by Neil Bartlett 17 Apr '07

17 Apr '07

Well, given that concurrency is a hot topic at the moment, how about something based on STM? E.g. perhaps some kind of instant messaging server? Or "Twitter" except scalable. By ruthlessly eliminating features, you could get the core of one of these down to something that could be built in three hours. But please, no Santa Clauses ;-) Neil > Friends > > I have agreed to give a 3-hr tutorial on Haskell at the Open Source Convention 2007 > http://conferences.oreillynet.com/os2007/ > > I'm quite excited about this: it is a great opportunity to expose Haskell to a bunch of smart folk, many of whom won't know much about Haskell. My guess is that they'll be Linux/Perl/Ruby types, and they'll be > practitioners rather than pointy-headed academics. > > One possibility is to do a tutorial along the lines of "here's how to reverse a list", "here's what a type is" etc; you know the kind of thing. But instead, I'd prefer to show them programs that they might consider *useful* rather than cute, and introduce the language along the way, as it were. > > So this message is to ask you for your advice. Many of you are exactly the kind of folk that come to OSCON --- except that you know Haskell. So help me out: > > Suggest concrete examples of programs that are > * small > * useful > * demonstrate Haskell's power > * preferably something that might be a bit > tricky in another language > > For example, a possible unifying theme would be this: > http://haskell.org/haskellwiki/Simple_unix_tools > > Another might be Don's cpu-scaling example > http://cgi.cse.unsw.edu.au/~dons/blog/2007/03/10 > > But there must be lots of others. For example, there are lots in the blog entries that Don collects for the Haskell Weekly Newsletter. But I'd like to use you as a filter: tell me your favourites, the examples you find compelling. (It doesn't have to be *your* program... a URL to a great blog entry is just fine.) Of course I'll give credit to the author. > > Remember, the goal is _not_ "explain monads". It's "Haskell is a great way to Get The Job Done". > > Thanks! > > Simon > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

type inference futility
by Paul Wankadia 16 Apr '07

16 Apr '07

The following code has ambiguity, but I can't figure out how to get around it. Am I missing something trivial? Am I going in the wrong direction? Thank you in advance for your time and for any help that you can offer. > data MehQueue = MehQueue > > class MehBase a where new :: IO a > instance MehBase MehQueue where new = return MehQueue > > class (MehBase a) => HasShift a where shift :: a -> IO a > instance HasShift MehQueue where shift a = return a > > main :: IO () > main = do > x <- new > shift x > return () Please note that I intend to extend this example with MehStack, HasPush and HasPop. You can probably guess where I'm going with all this.

3 3

ghci Crashing...
by Gaetano Caruana 16 Apr '07

16 Apr '07

Hi all. I am new to this list ;) Today I have encountered something new that has never happened to me in the past 6 months that I have been using ghci and Haskell. I wrote this function: type Line = (Point,Point) type Point = (Float,Float) circleLineIntersection :: Float -> Float -> Float -> Line -> Maybe [Point] circleLineIntersection h k r ((x1,y1),(x2,y2)) = do let perpdist = calcPerpDist (h,k) ((x1,y1),(x2,y2)) noSolution = perpdist > r oneSolution = perpdist == r twoSolutions = perpdist < r in do if noSolution then Nothing else let dx = x2 - x1 dy = y2 - y1 dr = sqrt (dx * dx + dy * dy) bigD = x1 * y2 - x2 * y1 x1 = ( bigD * dy + sign (dy) * dx * sqrt( r * r * dr * dr - bigD * bigD ) ) / (dr * dr) y1 = - bigD * dx + abs(dy) * sqrt( r * r * dr * dr - bigD * bigD ) / (dr * dr) x2 = ( bigD * dy - sign (dy) * dx * sqrt( r * r * dr * dr - bigD * bigD ) ) / (dr * dr) y2 = - bigD * dx - abs(dy) * sqrt( r * r * dr * dr - bigD * bigD ) / (dr * dr) in if oneSolution then do Just [(x1,y1)] else do Just [(x1,y1),(x2,y2)] Compiling is fine... When I run the function like this.... circleLineIntersection 1 1 1 ((1,1),(2,2)) it simply outputs.... Just [( No CPU usage. I am using fglasgow-exts Thanks for your help. Gaetano

2 1

System.Random
by Ketil Malde 16 Apr '07

16 Apr '07

Hi, I've recently stumbled upon some issues with the System.Random module, and thought I'd try to remedy them. However, I'm not quite sure what an optimal resolution is. Problem 1 is that I often get the same "random" number on consecutive program runs [1]. Looking at the code for initialization (called with '0' argument on program start): mkStdRNG :: Integer -> IO StdGen mkStdRNG o = do ct <- getCPUTime (TOD sec ms) <- getClockTime return (createStdGen (sec * 12345 + ms + ct + o)) Considering that 'getCPUTime' tends to return 0 early in the program, and that we simply ignore the picosecond part of 'getClockTime', it's fairly obvious why we get this result. What is not obvious is the rationale for discarding 'ms', or for that matter, the 12345 multiplication - can anybody shed some light on this? Anyway, on my Linux system, I get (unsurprisingly considering the defintion of time_t) picoseconds in even millions, and successive calls to getClockTime are not successive enough to give the same result in my cases. A better implementation would perhaps use /dev/urandom, but that is possibly not portable enough? The second issue is reading the random state from a string [2]. I realize (as Simon points out) that you can use 'reads' to get the remainder of the string, but as many find it confusing (at least the OP and I :-), I wonder what the rationale is behind this kind of interface? And checking how the state is actually calculated: stdFromString :: String -> (StdGen, String) stdFromString s = (mkStdGen num, rest) where (cs, rest) = splitAt 6 s num = foldl (\a x -> x + 3 * a) 1 (map ord cs) So, it picks six chars, and folds them into an Int for mkStdGen. Now, this number (due to the low multiplier) never exceeds 93549. Since we have an Int of state, why not use the whole range? Why not fold with a multiplier of 256? (All of this is trivial to fix of course, but I worry about changing code I don't understand the rationale behind.) One final question: are there build and install instructions for 'base'? I got the code from darcs, but I haven't find a way to build it and replace the bundled 'base' with a new version. -k References: [1] http://hackage.haskell.org/trac/ghc/ticket/1272 [2] http://www.nabble.com/Re% 3A--Haskell-cafe--System.Random-StdGen-read-fails-on-some-strings--tf3394495.html#a9450043 [3] http://web.archive.org/web/20011027002011/http://dilbert.com/comics/dilbert…

1 0

partial kinds and instances
by Matthew Pocock 16 Apr '07

16 Apr '07

Hi, I saw that it's possible to peal off kinds from the right-hand side when instantiating classes. Is it possible to peel them off from the left-hand side? Or in any order? I have been told in #haskell by people who seems to know that Very Bad Things happen if you do this without also making the kind system more clever. Is there a quick fix that will give me the same effect, without introducing a newtype or re-writing the original type declaration to introduce the extra types in a different order? Illustrative code below. Matthew data MyType e = Singleton e data MyOtherType k v = Empty | Node k v data YetAnotherType k v = OtherEmpty | OtherNode k v type RevYAT v k = YetAnotherType k v class Iterable ite where iterate :: ite e -> [e] instance Iterable MyType where iterate (Singleton e) = [e] instance Iterable (MyOtherType k) where iterate ite = [] --broken but illustrative instance Iterable (RevYAT v) where iterate it = [] --broken again Type synonym `RevMOM' should have 2 arguments, but has been given 1 In the instance declaration for `Iterable (RevYAT v)'

1 0

Re: [Haskell] Re: ANN: wl-pprint-1.0: Wadler/Leijen pretty printer
by Duncan Coutts 16 Apr '07

16 Apr '07

On Mon, 2007-04-16 at 10:08 +0000, Arthur van Leeuwen wrote: > Goody! UU.PPrint is now on hackage! Regrettably, this does seem like > a bit of a waste of time, as UU.PPrint was already cabalised as part > of the Haskell Utrecht Tools at http://www.cs.uu.nl/wiki/HUT/ > which also contains the parser combinators and DData, Daan > Leijen's datastructure library. > > Doei, Arthur. (Who thinks Utrecht does too little marketing of its code :)) I'd like to note that uulib and uuagc have been included in Gentoo for ages! :-) Duncan

1 0

Re: [Haskell-cafe] k-minima in Haskell
by raghu vardhan 16 Apr '07

16 Apr '07

There seems to be some confusion about the question. There are two key things to keep in mind here: 1) You must make at most O(k*n) comparisons (in the worst case) if the list has length n. 2) The output must be the indices and not the numbers themselves. So, any algorithm that sorts is no good (think of n as huge, and k small). Another interesting caveat to this is that if k=2, you can actually solve the problem with just (n+log n) comparisons in worst case(instead of 2*n, that you get by a naive approach), and it's a nice exercise to do this. As a further clarification, this is not a homework question. I genereally do whatever programming I do in Matlab, as I work with matrices (huge ones) and use this function a lot. I just wanted to see how different an implementation you can get in Haskell (I am new to Haskell so I might not be able to come up with the best way to do this). ----- Original Message ---- From: Stefan O'Rear <stefanor(a)cox.net> To: raghu vardhan <mrvr84(a)yahoo.co.in> Cc: haskell-cafe(a)haskell.org Sent: Wednesday, 11 April, 2007 10:47:08 PM Subject: Re: [Haskell-cafe] k-minima in Haskell On Wed, Apr 11, 2007 at 08:38:48PM -0700, Stefan O'Rear wrote: > On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote: > > What's the best way to implement the following function in haskell: > > Given a list and an integer k as input return the indices of the least > > k elements in the list. The code should be elegant and also, more > > importantly, must not make more than the minimum O(k*length(list)) > > number of operations. > > Go read and thoroughly understand "Why Functional Programming > Matters." > > Also, your asyptotic complexity bound is just plain wrong. I'd give > faster code, but Don is suspicious (and I can never tell these things > myself). > > Stefan Don tells me (in #haskell) that you are legitimate, so here is the example: kminima k lst = take k $ sort lst If you want to be really explicit about it, here is a sort that will work: sort [] = [] sort l@(x:_) = filter (<x) l ++ filter (==x) l ++ filter (>x) l (A stable quicksort, btw) Note that this is FASTER than your bound - somewhere between O(n) and O(n*log n). Ain't lazy evaluation great? :) Stefan Send a FREE SMS to your friend's mobile from Yahoo! Messenger. Get it now at http://in.messenger.yahoo.com/

11 13

GADTs and Typeclasses
by Dominic Steinitz 16 Apr '07

16 Apr '07

Will I run into problems using typeclasses with GADTs? I've come up with this to model a fragment of ASN.1. I'd hate to spend a lot of time on this only to find out it's well known that these two features don't mix very well. Thanks, Dominic. data Type :: * -> * where INTEGER :: Type Int BOOLEAN :: Type Bool BITSTRING :: Type BitString NUMERICSTRING :: Type NumericString ReferencedType :: Type () -- for now ConstrainedType :: Type a -> Constraint a -> Type a SizeConstrainedType :: Size a => Type a -> Constraint Int -> Type a FromConstrainedType :: From a => Type a -> Constraint a -> Type a

2 1

LL(1) parsing of declarators
by Stefan O'Rear 16 Apr '07

16 Apr '07

I'm writing a code generator for C, and I'm trying to parse a C-like input language using LL(1) (parsec specifically). The syntax of declarators is giving me trouble: (simplified) declaration = qualifiers >> (declarator `sepBy1` char ',') qualifiers = many1 name declarator = name now if we have "<name> <name>", they are both parsed by the greedy many1 in qualifiers! I can make this work with some ugly rearranging: declaration = fdeclarator >> many (char ',' >> declarator) fdeclarator = name >> many1 name declarator = name is there a more elegant way? Stefan

2 3

darcs error
by Ruben Zilibowitz 15 Apr '07

15 Apr '07

What does it mean if I'm trying to check out a darcs repository and I get the following error? darcs: ./.DS_Store: openBinaryFile: does not exist (No such file or directory) .DS_Store files ought to be filtered out by the default boring file. I don't know how one got into the repository and started causing this error. Is there some way to repair the repository? darcs repair doesn't seem to help. Regards, Ruben

2 2

Weaving fun
by Bas van Dijk 15 Apr '07

15 Apr '07

Hello, For my own exercise I'm writing a function 'weave' that "weaves" a list of lists together. For example: weave [[1,1,1], [2,2,2], [3,3]] ==> [1,2,3,1,2,3,1,2] weave [[1,1,1], [2,2], [3,3,3]] ==> [1,2,3,1,2,3,1] Note that 'weave' stops when a list is empty. Right now I have: weave :: [[a]] -> [a] weave ll = work ll [] [] where work ll = foldr f (\rst acc -> work (reverse rst) [] acc) ll f [] g = \_ acc -> reverse acc f (x:xs) g = \rst acc -> g (xs:rst) (x:acc) However I find this definition hard to read and I'm questioning its efficiency especially due to the 'reverse' parts (how do they impact performance and can they be removed?) So I'm wondering if 'weave' can be defined more "elegantly" (better readable, shorter, more efficient, etc.)? happy hacking, Bas van Dijk

10 16

Calling C function in Mac OS X
by Sergey Perminov 15 Apr '07

15 Apr '07

I wish to optimize Haskell code using ByteString, direct reading Doubles form it, direct writing Doubles to it. I've tried Don Stewart's code http://hpaste.org/26 that uses calling to C functions to implement necessary readDouble & showDouble. readDouble works ok. showDouble always return "nan" in Mac OS X (but works well in Windows). I'm using GHC 6.6 in Mac (http://www.haskell.org/ghc/download_ghc_66.html#macosxppc) and in Windows (http://www.haskell.org/ghc/download_ghc_66.html#windows) I've made showInt based on showDouble: http://hpaste.org/1390 It works well in Mac OS X. It seems that problem happens only when I send CDouble (or CLDouble) to C function. My conf: PowerBook G4, Mac OS X 10.4.9, powerpc-apple-darwin8-gcc-4.0.1 What may cause this? How to fix it?

2 2

k-minima in Haskell
by raghu vardhan 15 Apr '07

15 Apr '07

What's the best way to implement the following function in haskell: Given a list and an integer k as input return the indices of the least k elements in the list. The code should be elegant and also, more importantly, must not make more than the minimum O(k*length(list)) number of operations. R M Send a FREE SMS to your friend's mobile from Yahoo! Messenger. Get it now at http://in.messenger.yahoo.com/

13 20

Do monads imply laziness?
by Brian Hurt 15 Apr '07

15 Apr '07

This is probably an off-topic question, but I can't think of a better forum to ask it: does the existance of monads imply laziness in a language, at least at the monadic level? Consider the following: a purely functional, eagerly evaluated programming language, that uses monads to encapsulate the awkward squad. In this programming language, a program generates an IO monad whose encapsulating computation performs side effecting affections- it writes to stdout, say. But this generated monad never has it's value evaluated- the monad is tossed away uninspected. Does the side effect happen? If the answer is at least potientially "no", then monads are lazily evaluated, and thus monads imply laziness (at least at the monadic level). On the other hand, if the answer is "yes", then monads do not imply laziness. Thanks, Brian

3 2

Left-factoring with Parsec
by Joel Reymont 14 Apr '07

14 Apr '07

Suppose I have expr = expr ":" expr ":" expr. Can the above be left-factored to fail on empty input so that my parser doesn't go into a loop? Thanks, Joel -- http://wagerlabs.com/

3 4