Re: [Haskell-cafe] Haskell Quiry
Ashutosh, ERROR file:.\-as.hs:5 - Unresolved top-level overloading *** Binding : main *** Outstanding context : (Read c, Read b, Show c, Show b) Add an type annotation: main = do j <- readFile "sig1.key" let (x,y) = (read j) :: (Int, Int)-- <- putStrLn ("value=" ++ (show (x,y))) Cheers, Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Quiry
I want to read some data from a file "Signature.ken" , for that I have written a program but its showing some errors (the file "signature.ken" contains data of the type = (122,152) ) main = do j <- readFile "sig1.key" let (x,y) = (read j) putStrLn ("value=" ++ (show (x,y))) ERROR file:.\-as.hs:5 - Unresolved top-level overloading *** Binding : main *** Outstanding context : (Read c, Read b, Show c, Show b) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What puts False before True?
Brandon, If I'm reading the reports correctly, the Ord instance was actually added in the Haskell 1.1 standard, by changing the definition of Bool from data Bool = True | False to data Bool = True | False deriving (Eq, Ord, Ix, Enum, Text, Binary) It's data Bool = False | True It seems like we actually get that order because deriving Ord makes constructors earlier in the definition compare greater than later constructors, and nobody was bothered by that ordering. It's the other way around: data T = Less | More deriving (Eq, Ord) gives you *Main> Less < More True Cheers, Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
On Thursday 31 May 2007 20:56:47 Andrew Coppin wrote: > Jon Harrop wrote: > > If you write a simple, numerically-intensive program that runs in the > > Mathematica rewriter then its performance is about 100-1,000x slower than > > that of a native-code compiled language like Haskell. Mathematica is > > often 30x slower than interpreted OCaml bytecode. > > Is this before or after compiling the Mathematica code? The 100-1,000x slower is without compilation in Mathematica. I found the ray tracer to be 30x slower in compiled Mathematica compared to OCaml bytecode (OCaml native code is much faster still). So GHC will easily beat Mathematica on such tasks. Incidentally, once you've reimplemented the core Mathematica language in 4 days, you might like to reimplement their compiler. I believe their spec is freely available but you could just redo the whole thing yourself. You could probably extend it and optimise it quite easily. For example, it doesn't support recursion and I don't think it does type inference. > I don't know, I thought one of the big advantages of Mathematica was > supposed to be that it can transform problems into the most efficiently > solvable form, select between multiple algorithms, etc. On certain very specific problems, yes. So it might check to see if a matrix is symmetric and use a faster routine when possible. As far as the languange itself is concerned, it is fairly mundane. > And I mostly use it to do insane things like give me parametric > solutions to giant polynomials and so forth... ;-) I used it to take integrals, do lots of FFTs, some general data analysis and lots of graph plotting. There are plenty of other computer algebra packages that could handle the integrals (although I never found any were better than just doing it by hand) and general-purpose languages that are better suited to the analysis, so now I just use it as a graph plotter. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What puts False before True?
On Fri, 01 Jun 2007 03:33:41 +0100, you wrote: >The question, however, still remains: why False = 0 and True 1? I >appreciate that it's so in boolean algebra but why? Why not True = 0 >and False = 1? There is a correspondence between a Boolean algebra and an algebraic ring. If we identify 0 with FALSE and 1 with TRUE, then that correspondence leads to a natural identification of addition with EXCLUSIVE OR, and multiplication with AND: 0 + 0 = 0FALSE XOR FALSE = FALSE 0 + 1 = 1FALSE XOR TRUE = TRUE 1 + 0 = 1TRUE XOR FALSE = TRUE 1 + 1 = 0TRUE XOR TRUE = FALSE (carry is ignored) 0 * 0 = 0FALSE AND FALSE = FALSE 0 * 1 = 0FALSE AND TRUE = FALSE 1 * 0 = 0TRUE AND FALSE = FALSE 1 * 1 = 1TRUE AND TRUE = TRUE >A Boolean value denotees veracity whereas an ordered value concerns >magnitude (priority), indeed, order!! It is frequently desirable to enumerate things, even when those things don't have a well-defined order. In such cases, we have to impose an order, perhaps arbitrarily. Within a given programming context, it doesn't matter what we choose for our enumeration order, but it's generally best to go along with whatever de facto standard there is, if for no other reason than to avoid going insane. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What puts False before True?
PR Stanley wrote: I think so, too. In Boolean algebra (which predates computers, much less C), FALSE has traditionally been associated with 0, and TRUE with 1. And since 1 > 0, TRUE > FALSE. The question, however, still remains: why False = 0 and True 1? I appreciate that it's so in boolean algebra but why? Why not True = 0 and False = 1? Because if you take (&&) to be (*), and (||) to be (+), you get a homomorphism between the two resulting algebras (assuming 1+1 = 1). That is, if we define: h(False) = 0 h(True) = 1 then: h(a&&b) = h(a) * h(b) h(a||b) = h(a) + h(b) -Paul P.S. Another reason to justify False < True is that show False < show True. :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
On 5/31/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: Polymorphic extensible records with subtyping are already expressible in Haskell. There is nothing needs to be added: http://homepages.cwi.nl/~ralf/HList/ http://homepages.cwi.nl/~ralf/OOHaskell/ The last time I tried this code, I reported to haskell-cafe that OOHaskell does not work when compiled as a library (at least under GHC). For some reason the code that uses OOHaskell had to be compiled along side it. Is this now fixed? If so, could it be available via hackage as a library for people to use? I can't tell if it's only meant as proof of concept or for actual use. But, your response makes me think it is intended for actual use if people would like to do that (hence my interest in getting the code into hackage). Thanks, Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
Polymorphic extensible records with subtyping are already expressible in Haskell. There is nothing needs to be added: http://homepages.cwi.nl/~ralf/HList/ http://homepages.cwi.nl/~ralf/OOHaskell/ The full code is available via darcs http://darcs.haskell.org/OOHaskell/ As to polymorphic variants, they too are implementable in Haskell right now. No new extensions are required. http://www.haskell.org/pipermail/haskell/2006-July/018172.html http://darcs.haskell.org/HList/src/VariantP.hs The code shows that the expression problem is solved in Haskell as it is. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] New (?) Partial Monad
Some time ago I noticed that a function I was writing had the exact type as liftM2, and I so I ended up generalizing a monad. I thought I should document it really well, and the result is this: http://www.downstairspeople.org/darcs/partial/Partial.pdf $ darcs get http://www.downstairspeople.org/darcs/partial I would appreciate any feedback. Is this even original? --Lane ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What puts False before True?
>I think it's mathematical convention more than the C convention Haskell >is agreeing with. I think so, too. In Boolean algebra (which predates computers, much less C), FALSE has traditionally been associated with 0, and TRUE with 1. And since 1 > 0, TRUE > FALSE. The question, however, still remains: why False = 0 and True 1? I appreciate that it's so in boolean algebra but why? Why not True = 0 and False = 1? A Boolean value denotees veracity whereas an ordered value concerns magnitude (priority), indeed, order!! Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What puts False before True?
On Thu, 31 May 2007 13:51:20 -0700, you wrote: >I think it's mathematical convention more than the C convention Haskell >is agreeing with. I think so, too. In Boolean algebra (which predates computers, much less C), FALSE has traditionally been associated with 0, and TRUE with 1. And since 1 > 0, TRUE > FALSE. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
stefan: > Al, > > >Has there been any work on extending Haskell's type system with > >structural subtyping? > > Koji Kagawaga. Polymorphic variants in Haskell. In Andres Loeh, > editor, Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell, > Portland, Oregon, USA, September 17, 2006, pages 37--47. ACM Press, > 2006. [1] > > >What is the canonical solution to the expression problem in Haskell? > > Not canonical but Loeh and Hinze have proposed open data types: > For a short term solution, we used Typeable + type classes to provide a open Message data type. Similar techniques are used in Simon Marlow's extensible exceptions paper. -- An open Message type class Typeable a => Message a -- -- A wrapped value of some type in the Message class. -- data SomeMessage = forall a. Message a => SomeMessage a -- -- And now, unwrap a given, unknown Message type, performing a (dynamic) -- type check on the result. -- fromMessage :: Message m => SomeMessage -> Maybe m fromMessage (SomeMessage m) = cast m -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: [Haskell] boilerplate boilerplate
Actually, standalone deriving doesn't really solve the boilerplate boilerplate problem. My original complaint here is that I don't want to explicitly declare a deriving (Data,Typeable) for every type used somewhere inside a larger type I am using. In this particular case, I am using SYB to autogenerate/autoparse XML. The Atom/RSS datatype has a lot of elements in it. Having to do an explicit declaration of deriving (Data,Typeable) for each of them is just a tremendous beat-down no matter where I do it. A simple solution to the problem is just to have the compiler automatically derive Data and Typeable for all classes. Perhaps initially there is some compiler flag like -fSYB. Slightly more elegant would be to not automatically derive if the user has done so explicitly and to add syntax to the deriving clause like "deriving ... not (Data,Typeable)" to tell the compiler that these instances should be unavailable for this type. A substantially more general/elegant solution would be for the compiler to derive instances automatically for any classes whose methods I use and for which there has been no explicit contradictory declaration. But I assume that is harder and having Data and Typeable means you can use SYB and not worry so much about deriving instances anymore. Most elegant would be for the user to be able to add derivable classes via import declarations, but again simply having Data and Typeable is a 95% solution and the perfect should not be the enemy of the good. -Alex- Simon Peyton-Jones wrote: | does that help to keep it on the radar?-) | claus Indeed! But please modify the wiki. Email has a half life of about 1 day! S ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
Jon Harrop after myself: The semantic pattern-matcher within an algebraic package, is worlds apart from the syntactic/structural pattern-matcher of Haskell. Can you elaborate on this? I would imagine that the pattern matcher in a term-level Haskell interpreter would be quite similar to one from a toy Mathematica-like rewriter. Also, what aspects of this do you think would take more than 4 days? Well, I don't know what is your definition of "toy". I can make in about 15 minutes a toy atomic bomb, using Lego. Certainly, there is a possibility and need for syntactic pattern matching, as in Haskell, although the identification of common terms is so important that I would rather use a unification procedure, like in logic languages. But this is not enough for computer algebra. OK, if you wish some SIMPLE examples (among infinitely more) of something beyond... * the simplification of rational expressions, beginning with the reduction of (x^2-1)/(1+x)-x = 1, ending with a full polynomial factorizer... Gathering of all the 'x in a+x+b+x+ ... + x + ... so as to get M*x is already not so trivial, and requires some decisions. Will you keep your expressions sorted? How?... * sin(z)^2 + ... + cos(z)^2 should simplify to 1 + ... independently of z, so the equivalence of shared expressions should be treated seriously. We are usually not interested in 'term-level' trivialities. If you look at the plethora of pattern-matching functions in Mathematica, all those MemberQ, MatchQ, FreeQ, all those DeleteCases, the functions which give you the *position* at which a given pattern occurs within a formula, etc., you become a bit modest. If you add to it the possibility/necessity of renaming the variables in patterns present within the Function[{x}...] formulae, you see that just assimilating the documentation needs something like 4 days. Of course, this is not restricted to Mathematica. All Comp. Algebra systems have such tools. But, OK, I am old, tired and slow. There are, fortunately for us, some people very fast and efficient. Jerzy Karczmarczuk. PS. Somebody (A. Coppin?) said that Mathematica not without reason costs 1. Welll, less than 2000, and for students there are much cheaper possibi- lities. I am the last to make free ads for Wolfram, I recommend the usage of Axiom and Maxima to my students, but there is no need to say publicly some dubious truths about commercial software. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
On 5/31/07, Brandon S. Allbery KF8NH <[EMAIL PROTECTED]> wrote: On May 31, 2007, at 15:47 , Andrew Coppin wrote: > If you're bored... can you come up with a solution to this? > > http://warp.povusers.org/ProgrammingChallenge.html Is it me, or does this look like a job for Data.Binary? It's not just you. When I read it I thought "First I'd steal code from Data.Binary..." ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
On May 31, 2007, at 15:47 , Andrew Coppin wrote: If you're bored... can you come up with a solution to this? http://warp.povusers.org/ProgrammingChallenge.html Is it me, or does this look like a job for Data.Binary? -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
On Thu, May 31, 2007 at 11:36:54PM +0200, Tomasz Zielonka wrote: > You can imitate the C++ code using the FFI libraries: > > import Foreign.Storable > import Foreign > import Data.Word > import Data.Bits > > getDoubleBits :: Double -> IO String > getDoubleBits d = alloca $ \ptr -> do > poke ptr d > bs <- peekArray (sizeOf d) (castPtr ptr :: Ptr Word8) > return . concatMap (concatMap (show . fromEnum) . flip map [7,6..0] . > testBit) $ bs > > (I'm not sure this code prints bits in the right order). > You can generalize this to > getStorableBits :: Storable a => a -> IO String Note also that you can use unsafePerformIO to safely get pure functions doing both these operations. -- David Roundy Department of Physics Oregon State University ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Crazy idea: overloading function application notation
Derek Elkins after a long chain which began: This is a crazy idea I've been working on: overload the syntax "x y" so it can mean function application "f x = f(x)" or multiplication "x y = x*y". ... This change would -definitely- lead to massive ambiguity and potentially lead to unresolvable cases. My favourite example of a guaranteed mess is the implementation of Peano- Church numerals as polymorphic functions in Haskell. You can multiply them, you can act with one upon another one as well. But the multiplication is the composition, and the functional application is the (inverted) exponentiation! I belive that trying to produce something similar to the proposal above would result in a True Disgrace. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Crazy idea: overloading function application notation
Claus Reinke wrote: This is a crazy idea I've been working on: overload the syntax "x y" so it can mean function application "f x = f(x)" or multiplication "x y = x*y". The reason is simply that I appreciate the brevity of MLs function application but I also appreciate the brevity of Mathematica's multiplication. Is it possible to implement this in Haskell using type classes? Is there any way this could actually be practicable? i'm not sure about practicalities - since Haskell programs are mostly identifiers and their applications, redefining application is going to lead to confusion. general rule for extending pure functional languages: do not mess with application, or you risk losing your nice theory. a rather steep price to pay for replacing '*' with ' ', no? you could, however, define a 'Num' instance for functions so that 'f * g = f . g' and 'fromInteger n = fromInteger . const n' or similar (though the types are not likely to make you happy), or you could try replacing the standard 'Num' class with one permitting differently- typed parameters to '(*)', and then try to define multiplication as application rather than composition.. (and if you think that is confusing, think again about overloading application;-) Indeed. This change would -definitely- lead to massive ambiguity and potentially lead to unresolvable cases. the rest of this message will not help with your particular problem, but is in reply to your subject line: in general, Haskeller's like to enjoy the advantages of overloading something so fundamental as application without endangering that fundament, even if that means a little more typing to indicate where a non-standard overloading is possible. so overloaded application uses a different notation and conventions. recall that '($)' is function application, and consider the following types: flip ($) :: a -> (a -> b) -> b (>>=) :: (Monad m) => m a -> (a -> m b) -> m b you'll notice that monadic bind corresponds to reverse function application, lifted into a monad. of course, there are many ways to do such lifting, so it is interesting to consider what the particular choice of monadification here means. if we permit monadic effects in all of parameter, function, and result, we'd get a type like this for lifted, reversed function application: m a -> m (m a -> m b) -> m b the type of '(>>=)' differs from this in two positions, meaning no monadic effects while computing the function, and no monadic effects in the function parameter _after_ substitution into the function body. the latter implies that, even though Haskell's standard application is based on call-by-need (or call-by-name, since sharing isn't required), its monadic application is based on call-by-value: any monadic effects in computing the argument have to be executed _before_ passing the (effect-free part of the) argument to the function. i've often wondered about this discrepancy. Laziness "causes" Haskell to be pure because understanding side-effecting code in a lazy language is... tricky to say the least. Why then would we want laziness for monads? Also, nothing is stopping you from defining a "lazy" apply when you -do- want it. but if you just want overloaded application, rather than mess with the meaning and notation of built-in application, Monads may be the way to go. it might also give one indication of why Monads are so popular in Haskell, and so little heard of in languages which do allow unconstrained overloading of application. Um... they are probably so little heard of in languages that allow unconstrained overloading of application because they are so little heard of in -any- other language. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
OK, so you're saying that in 4 days you wrote something that out-performs Mathematica, a program that has existed for decades and has a vast, highly-funded R&D effort behind it featuring some of the brightest minds in the field? If you want some amusement, just search for "Jon Harrop" in comp.lang.lisp. Write a newer, better, faster Mathematica in four days! I will show you how! Just attend one of my seminars comming soon to your area! [*] -alex http://www.ventonegro.org/ [*] Some attendees may not actually build a faster Mathematical in four days. Results vary. Tim Newsham http://www.thenewsh.com/~newsham/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
Andrew Coppin cites me and asks: jk wrote: ... The World had many symbolic math packages: Reduce, Macsyma, Schoonschip (beloved by high- energy physicists), Maple, Scratchpad2/Axiom, later MuSIMP/MuMATH for small platforms, etc. I find that statement interesting. I have never come across *any* other package that can perform _symbolic_ mathematics. (Sure, there are packages that can perform specific operations - solving certain kinds of equations, transforming matricies, rearranging formulas. But I have never seen any other package where you can just do *anything*.) You must be joking, but OK, I am naive, and I will answer as it were serious. Really, haven't heard about Maple??? http://www.maplesoft.com/ Its limited library is integrated within Matlab Symbolic Toolbox, and if you *have* Maple and Matlab, the latter can use the full force of the former. Maple is commercial as Mathematica, but there are perfectly usable free packages as well, for example Axiom and Maxima (Macsyma rekindled). http://wiki.axiom-developer.org/FrontPage http://maxima.sourceforge.net/ There is also a system constructed in Paderborn, MuPAD, which was free, but for survival reasons it became 100% commercial (although the old free version circulates still on the Web...) http://www.mupad.de/ The are more free stuff, GAP, MaCaulay,... In general, check http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems DoCon is mentioned here as well. Some disappeared, but the choice remains pretty large. But yes - I have tried to implement that pattern matching engine a couple of times in Pascal. (Remember Pascal?) Getting it to work for a few test cases is easy. Getting it to *properly* handle associativity and commutivity is really nontrivial. (I mean *really* nontrivial! Or perhaps I am an inferior programmer - one of the two!) The mathematically sensitive matching/substitution is a hard task even if you have at your disposal a reasonably full unifier. Forget Pascal, take Prolog, which will save several days/weeks of the implementation of basic stuff. Even then, it will be quite tedious to write a package able say, to reduce rational formulae, to reduce a polynomial modulo an ideal, to implement the basic trig identities, find a reasonable common form for expressions containing complex exponentials AND trigonometrics, etc. ...other symbolic math tools exist? Ask a few more times. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Existentials and type var escaping
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Roberto Zunino wrote: > In this function > > data C = C Int > foo :: C -> C > foo ~(C x) = C x > > foo is _not_ the identity: its result must be non bottom, i.e. the > constructor C is "forced" to its argument. foo undefined = undefined foo (C undefined) = C undefined foo (C 13) = C 13 Looks like the identity to me? (id _is_ strict after all) foo' (C x) = x `seq` (C x) would be different though: foo' (C undefined) = undefined Isaac -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGX0HQHgcxvIWYTTURAoE2AKDFNn2bSVqoVjqWj8jyBfgKjYVh1gCeLqdT pGz49AfTUbblaMeeyBR8a84= =sFp6 -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Monads and constraint satisfaction problems (CSP)
Brandon, Jeremy, et al, Thanks for the pointers. The paper by OlegK, et al, articulates exactly the structure i was noticing, except that i was coming at it from the other end. i was noticing that a wide range of these CSP-style problems could be decomposed into a trivial monad (e.g., list, multiset, set) and some additional search machinery (over which a good solution should be parametric). They show how to add a reasonable upper limit on the search machinery to any monad. Best wishes, --greg Date: Thu, 31 May 2007 11:36:55 -0700 From: "Jeremy Shaw" <[EMAIL PROTECTED]> Subject: Re: [Haskell-cafe] Monads and constraint satisfaction problems (CSP) To: "Greg Meredith" <[EMAIL PROTECTED]> Cc: haskell-cafe Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain; charset=US-ASCII At Thu, 31 May 2007 10:42:57 -0700, Greg Meredith wrote: > BTW, i think this could have a lot of bang-for-buck because the literature i > read exhibited two basic features: > >- the "standard" treatments (even by CS-types) are decidedly not >compositional >- the people in the field who face industrial strength csp problems >report that they have to take compositional approaches because the problems >are just too large otherwise (both from a human engineering problem as well >as a computational complexity problem) This paper describes a non-monadic, compositional method for solving CSPs: http://www.cse.ogi.edu/PacSoft/publications/2001/modular_lazy_search_jfp.pdf There is also the LogicT monad transformer: http://okmij.org/ftp/Computation/monads.html j. -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Existentials and type var escaping
On 31/05/07, Isaac Dupree <[EMAIL PROTECTED]> wrote: foo undefined = undefined That's not true. When you evaluate foo undefined, it matches the first (irrefutable) pattern immediately, without any deconstruction of the undefined argument (which is the entire point of it being a lazy pattern). So it becomes the right hand side, C . Only when you force that would you have to force the undefined argument, so foo undefined = C undefined: *Main> foo undefined C *** Exception: Prelude.undefined -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
On Thu, May 31, 2007 at 08:47:28PM +0100, Andrew Coppin wrote: > If you're bored... can you come up with a solution to this? > > http://warp.povusers.org/ProgrammingChallenge.html > > (Obviously a pretty silly challenge, but hey.) > > My first instinct was to use Data.Bits - but I see no instance for > Double. You can imitate the C++ code using the FFI libraries: import Foreign.Storable import Foreign import Data.Word import Data.Bits getDoubleBits :: Double -> IO String getDoubleBits d = alloca $ \ptr -> do poke ptr d bs <- peekArray (sizeOf d) (castPtr ptr :: Ptr Word8) return . concatMap (concatMap (show . fromEnum) . flip map [7,6..0] . testBit) $ bs (I'm not sure this code prints bits in the right order). You can generalize this to getStorableBits :: Storable a => a -> IO String Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
On Thu, May 31, 2007 at 08:47:28PM +0100, Andrew Coppin wrote: > My first instinct was to use Data.Bits - but I see no instance for > Double. (Presumably because performing bitwise operations on a Double is > a pretty odd thing to want to do.) So my next guess is to do some > bizzare type system hackery that allows you to transform a Double > into... whichever integer type is the same size, and proceed from there. > Does anybody know how to do that? This reminds me. it would be nice if we could remove the 'Num' superclass of Bits, having bitwise operations and being a number are fairly unrelated and having to declare bogus instances is annoying. It is probably just a holdover from C that we think of them as related. 'Bool' would be a simple example of something that is a good instance of bits, but not Num. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Existentials and type var escaping
In this function data C = C Int foo :: C -> C foo ~(C x) = C x foo is _not_ the identity: its result must be non bottom, i.e. the constructor C is "forced" to its argument. I wonder if a similar function is definable for existential types: data E = forall a . E a foo :: E -> E foo, as defined above does not work (lazy patterns not allowed), and in foo y = E (case y of E x -> x) a variable escapes. I also tried with CPS with no success. Is foo definable at all? I'm starting to think that it is not, and that there must be a very good reason for that... Thank you, Zun. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Just for a laugh...
On 31 May 2007 21:52:33 +0100, Jon Fairbairn <[EMAIL PROTECTED]> wrote: Yes, but you didn't say that it's not only silly but demonstrates the opposite of expressiveness as it's all about breaking an abstraction and must be non-portable code (because it's definition is that it won't give the same results on different hardware), so such code should be *hard* to write in a good language. Well, I would suggest that maybe *good* is not completely congruent with *expressive* (at least for this case). If I want to write a program to learn how IEEE floats are constructed, by destructing them, then I *should* be able to. I have no solutions of my own though :-( I wait in eager expectation D. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
On Thursday 31 May 2007, Andrew Coppin wrote: > If you're bored... can you come up with a solution to this? > > http://warp.povusers.org/ProgrammingChallenge.html > > (Obviously a pretty silly challenge, but hey.) With some help from int-e in irc: > {-# OPTIONS_GHC -fglasgow-exts #-} > import GHC.Base > import GHC.Word > import GHC.Exts > import Numeric > import Data.Char > doubleToBits (D# d) = W64# (unsafeCoerce# d) > main = interact $ unlines > . map (pad . (\x -> showIntAtBase 2 intToDigit x "") >. doubleToBits . read) > . lines > where pad l = replicate (64 - length l) '0' ++ l I suspect that that doesn't respect the endianness of the machine like the C++ does, though. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Just for a laugh...
On 31/05/07, Andrew Coppin <[EMAIL PROTECTED]> wrote: Note that the challenge asks for the "internal" bitmap representation of an IEEE double-precision integer - not the mathematical binary expansion. (In particular, things like Infinity and NaN have special bit sequences.) Ah, sorry, then disregard my solution. I did wonder why you'd immediately jump to Data.Bits. -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Just for a laugh...
Andrew Coppin <[EMAIL PROTECTED]> writes: > Jon Fairbairn wrote: > > "David House" <[EMAIL PROTECTED]> writes: > > > > > >> On 31/05/07, Andrew Coppin <[EMAIL PROTECTED]> wrote: > >> > >>> If you're bored... can you come up with a solution to this? > >>> > >> Try using floatToDigits: > >> http://haskell.org/ghc/docs/latest/html/libraries/base/Numeric.html#v%3AfloatToDigits > >> > >> "floatToDigits takes a base and a non-negative RealFloat number, and > >> returns a list of digits and an exponent." > >> > > > > I think you also need floatRadix and floatDigits. > > > > Note that the challenge asks for the "internal" bitmap > representation of an IEEE double-precision integer - not the > mathematical binary expansion. Hence my remark above. > (In particular, things like Infinity and NaN have special > bit sequences.) > > Did I mention that this is a silly challange yet? Yes, but you didn't say that it's not only silly but demonstrates the opposite of expressiveness as it's all about breaking an abstraction and must be non-portable code (because it's definition is that it won't give the same results on different hardware), so such code should be *hard* to write in a good language. -- Jón Fairbairn [EMAIL PROTECTED] http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html (updated 2007-05-07) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What puts False before True?
On Thu, May 31, 2007 at 10:03:05AM +0100, PR Stanley wrote: > > >> What is the basic philosophy for Bool being a member of Ord? I hear two questions, why is Bool a member of Ord at all, and why was it ordered with False before True. If I'm reading the reports correctly, the Ord instance was actually added in the Haskell 1.1 standard, by changing the definition of Bool from data Bool = True | False to data Bool = True | False deriving (Eq, Ord, Ix, Enum, Text, Binary) (Text was later broken into Read and Show) I imagine it was added because you generally can't derive an instance of a class for a new type unless all the types you mention in the definition already have instances. Also, there are Ord instances like (Ord a, Ord b) => Ord (a,b), and it's sometimes handy to be able to use types like (String, Bool) as keys in a Map, or keep them in a Set. Probably there are other useful things you can do. > >> What justifies False < True? > >in most interpretations this equals: > > > >False == 0 > >True == 1 > >Indeed, it's the same in C but what justifies the decision in Haskell? It seems like we actually get that order because deriving Ord makes constructors earlier in the definition compare greater than later constructors, and nobody was bothered by that ordering. I can't see how one of the orders could be more expressive or otherwise technically better than the other, so I suppose you might as well agree with other conventions. I think it's mathematical convention more than the C convention Haskell is agreeing with. But this is all just speculation - the members of the Haskell comittee could tell us why this all actually happened, and at least a few read this list. Brandon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: New book: Real-World Haskell!
Malte Milatz wrote: Simon Marlow: While we're on fish, what's wrong with the humble Haddock? :-) It may at least make for a tasty curry ... Oh dear God, what next? Will you say a blessing over the food in a *Church*? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OpenGL
Creighton Hogg wrote: Check out this blog entry as a nice starting place http://blog.mikael.johanssons.org/archive/2006/09/opengl-programming-in-haskell-a-tutorial-part-1/ Thanks for this... (I too would like to start hacking around with OpenGL!) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Just for a laugh...
Jon Fairbairn wrote: "David House" <[EMAIL PROTECTED]> writes: On 31/05/07, Andrew Coppin <[EMAIL PROTECTED]> wrote: If you're bored... can you come up with a solution to this? Try using floatToDigits: http://haskell.org/ghc/docs/latest/html/libraries/base/Numeric.html#v%3AfloatToDigits "floatToDigits takes a base and a non-negative RealFloat number, and returns a list of digits and an exponent." I think you also need floatRadix and floatDigits. Note that the challenge asks for the "internal" bitmap representation of an IEEE double-precision integer - not the mathematical binary expansion. (In particular, things like Infinity and NaN have special bit sequences.) Did I mention that this is a silly challange yet? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
Tomasz Zielonka wrote: On Thu, May 31, 2007 at 08:47:28PM +0100, Andrew Coppin wrote: If you're bored... can you come up with a solution to this? http://warp.povusers.org/ProgrammingChallenge.html (Obviously a pretty silly challenge, but hey.) I fail to see what this has to do with "expressive power", which it's supposed to test. In this test assembler is the most expressive language. Yes, silly. Silly? Yes. Proposed by a C++ programmer? Yes. (Personally I can't think of a reason for *wanting* to do such a thing... but never mind. I am however mildly - I emphasize mildly - curiose to see if it can be done in Haskell.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Just for a laugh...
"David House" <[EMAIL PROTECTED]> writes: > On 31/05/07, Andrew Coppin <[EMAIL PROTECTED]> wrote: > > If you're bored... can you come up with a solution to this? > > Try using floatToDigits: > http://haskell.org/ghc/docs/latest/html/libraries/base/Numeric.html#v%3AfloatToDigits > > "floatToDigits takes a base and a non-negative RealFloat number, and > returns a list of digits and an exponent." I think you also need floatRadix and floatDigits. -- Jón Fairbairn [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
On Thu, May 31, 2007 at 08:47:28PM +0100, Andrew Coppin wrote: > If you're bored... can you come up with a solution to this? > > http://warp.povusers.org/ProgrammingChallenge.html > > (Obviously a pretty silly challenge, but hey.) I fail to see what this has to do with "expressive power", which it's supposed to test. In this test assembler is the most expressive language. Yes, silly. Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
[EMAIL PROTECTED] wrote: The conditions of its career were far from obvious. The World had many symbolic math packages: Reduce, Macsyma, Schoonschip (beloved by high- energy physicists), Maple, Scratchpad2/Axiom, later MuSIMP/MuMATH for small platforms, etc. I find that statement interesting. I have never come across *any* other package that can perform _symbolic_ mathematics. (Sure, there are packages that can perform specific operations - solving certain kinds of equations, transforming matricies, rearranging formulas. But I have never seen any other package where you can just do *anything*.) * First symbolic packages treated *first* the symbolic expressions as something to be evaluated/simplified. One sees that Maple has been built on this principle. Mathematica changed a bit the perspective, along - perhaps - the same lines as Schoonschip, where the fundamental stuff was *rewriting/ transformations*. So, Mathematica since the begininng was equipped with a very powerful pattern-matcher/substitution contraption. For the sake of efficiency it was less powerful than a general unifier, but it was really nice (and it existed already in SMP, before the birth of Mathematica). Now, again, somebody would do that in 4 days?? The semantic pattern-matcher within an algebraic package, is worlds apart from the syntactic/structural pattern-matcher of Haskell. This helped a lot to popularize Mathematica, and has been shamelessly abused in the advertising, where our friends used to say "we DO MATHEMATICS with computers". Non-sense, of course... Pattern matching *so* rich, in fact, that you can even use it to do things that aren't mathematics - although the default input syntax isn't really geared to it. But yes - I have tried to implement that pattern matching engine a couple of times in Pascal. (Remember Pascal?) Getting it to work for a few test cases is easy. Getting it to *properly* handle associativity and commutivity is really nontrivial. (I mean *really* nontrivial! Or perhaps I am an inferior programmer - one of the two!) * All the numerical, standard stuff, the interface between the symbolic and the numerical functions, with plots 2D/3D, etc. Too often people speak about that, comparing, say, Matlab with Mathematica (while Matlab has no symbolics, etc.) Here the Mathematica team did a serious, thorough job, trying to adapt the richness of this layer to many branches of science and engineering. It was mainly a compilation process, they hardly added anything new, but made a coherent, useful library. Won't repeat it in 4 days, or even in 4 months. Again, Mathematica has all these functions defined, it has vast *libraries* of identities for transforming them, *and* it has efficient numerical algorithms to compute them. (If you believe the product literature, for many functions there are several different possible algorithms depending on how accurate you want it, what arguments you're trying to compute it on, etc.) I really don't see anybody easily duplicating all this... = Is there any sense in "making Mathematica with Haskell"? As a package, most certainly no, too much to implement, for what? In order to have another tool of the kind which already exists? ...other symbolic math tools exist? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just for a laugh...
On 31/05/07, Andrew Coppin <[EMAIL PROTECTED]> wrote: If you're bored... can you come up with a solution to this? Try using floatToDigits: http://haskell.org/ghc/docs/latest/html/libraries/base/Numeric.html#v%3AfloatToDigits "floatToDigits takes a base and a non-negative RealFloat number, and returns a list of digits and an exponent." -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
Jon Harrop wrote: If you write a simple, numerically-intensive program that runs in the Mathematica rewriter then its performance is about 100-1,000x slower than that of a native-code compiled language like Haskell. Mathematica is often 30x slower than interpreted OCaml bytecode. Is this before or after compiling the Mathematica code? Incidentally, when I try to recompile with optimizations turned on, GHC refuses to work: $ ghc htrace.hs -o htrace $ ghc -O2 htrace.hs -o htrace compilation IS NOT required I must delete the target or edit the source to get it to recompile. I assume this is a known bug? This one surprised me... I'm pretty sure I tried recompiling with -O2 and it recompiled everything. Maybe I imagined it? Right, but that is just calling an internal function that is written in C. Provided you only ever call a few library functions, performance will be excellent in Mathematica. But when you cannot phrase your program in terms of the built-in library functions, performance is terrible and this is when everyone reaches for a more efficient tool. I don't know, I thought one of the big advantages of Mathematica was supposed to be that it can transform problems into the most efficiently solvable form, select between multiple algorithms, etc. To me, performance is way down on the list of things that make Mathematica great. Integrated graphics is probably the main benefit. I mostly use MMA as a glorified graph plotter. And I mostly use it to do insane things like give me parametric solutions to giant polynomials and so forth... ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
Lennart Augustsson wrote: Why do you seem so in awe of Mathematica? Oh, well, I guess it is only the most powerful maths software ever written... no biggie. It's just another language with a good set of libraries. Claims that it is the best, fastest, etc comes from Wolfram advertising, no doubt. :) The claim that it is the fastest clearly doesn't hold (much to my surprise). The claim that it is the most powerful, well... I have yet to see anything that can come close to the symbolic power of Mathematica. Let's face it, the thing costs nearly ten grand for a reason... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Just for a laugh...
If you're bored... can you come up with a solution to this? http://warp.povusers.org/ProgrammingChallenge.html (Obviously a pretty silly challenge, but hey.) My first instinct was to use Data.Bits - but I see no instance for Double. (Presumably because performing bitwise operations on a Double is a pretty odd thing to want to do.) So my next guess is to do some bizzare type system hackery that allows you to transform a Double into... whichever integer type is the same size, and proceed from there. Does anybody know how to do that? (Otherwise... wasn't there some library somewhere for serialising values in binary?) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Frisby grammars that have context
On Tue, 2007-05-29 at 10:18 -0400, Mark T.B. Carroll wrote: > I've been playing with Text.Parsers.Frisby to see how it stacks against > other options and, while it's been great so far, I am finding that I > can't encode a grammar where what's acceptable depends on what's already > been parsed in some nontrivial way. To take a simple example, imagine a > grammar where the only lower-case letters that are acceptable are those > where their upper-case equivalent occurred earlier in the text. ... > Is this supposed to not be possible in Frisby, or (quite likely) am I > missing something that allows me to? I've thought about things like > trying to fmap further calls to apply runPeg to rest, but I've not > figured out a trick that will actually work. I've never used Frisby, but I have read about Parsing Expression Grammars, and I'm pretty sure that this is supposed to not be possible. Basically, PEG parsers manage to be linar-time by caching the result of attempting to parse a particular nonterminal at a particular input position. If your nonterminal depends on previous input to decide what to accept, then such caching would no longer be valid. Carl Witty ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
On Thu, May 31, 2007 at 09:04:30PM +0200, Tomasz Zielonka wrote: > On Thu, May 31, 2007 at 06:16:20PM +0100, Jon Harrop wrote: > > > I can't think of a lightweight way to encode overlapping enumerations in > > > Haskell. > > > > I'd like to know if this is possible in Haskell. > > Maybe this way using GADTs and typeclasses? I haven't used such code in > practice - there may be some hidden traps. Let me be the first one to admit that this approach is highly unmodular - you have to define all cases in one place, or at least each group of overlapping enum types. Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
On Thu, May 31, 2007 at 06:16:20PM +0100, Jon Harrop wrote: > > I can't think of a lightweight way to encode overlapping enumerations in > > Haskell. > > I'd like to know if this is possible in Haskell. Maybe this way using GADTs and typeclasses? I haven't used such code in practice - there may be some hidden traps. {-# OPTIONS -fglasgow-exts #-} module Enum where data Height data Size class HasMEDIUM t instance HasMEDIUM Height instance HasMEDIUM Size data ENUM t where LOW :: ENUM Height MEDIUM :: HasMEDIUM t => ENUM t HIGH:: ENUM Height SMALL :: ENUM Size BIG :: ENUM Size Example use: *Enum> :t [MEDIUM, LOW] [MEDIUM, LOW] :: [ENUM Height] *Enum> :t [MEDIUM, SMALL] [MEDIUM, SMALL] :: [ENUM Size] *Enum> :t [MEDIUM, SMALL, LOW] :1:16: Couldn't match expected type `Size' against inferred type `Height' Expected type: ENUM Size Inferred type: ENUM Height In the expression: LOW Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monads and constraint satisfaction problems (CSP)
At Thu, 31 May 2007 11:36:55 -0700, Jeremy Shaw wrote: > This paper describes a non-monadic, compositional method for solving CSPs: > > http://www.cse.ogi.edu/PacSoft/publications/2001/modular_lazy_search_jfp.pdf btw, there are multiple versions of this paper. This version includes a section on dynamic variable ordering, as well as some improvements to the other sections. j. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monads and constraint satisfaction problems (CSP)
At Thu, 31 May 2007 10:42:57 -0700, Greg Meredith wrote: > BTW, i think this could have a lot of bang-for-buck because the literature i > read exhibited two basic features: > >- the "standard" treatments (even by CS-types) are decidedly not >compositional >- the people in the field who face industrial strength csp problems >report that they have to take compositional approaches because the problems >are just too large otherwise (both from a human engineering problem as well >as a computational complexity problem) This paper describes a non-monadic, compositional method for solving CSPs: http://www.cse.ogi.edu/PacSoft/publications/2001/modular_lazy_search_jfp.pdf There is also the LogicT monad transformer: http://okmij.org/ftp/Computation/monads.html j. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parse error on input "|"
thx much green... this helped for the parser failure. Dan you were right too, cause now i got the interfering types [(Int,Int)] and Polynom for line 2. But i fixed this by replacing it with ([],[]) So thx much guys :D greenrd wrote: > > You neglected a ) - remember to count your parentheses in future when > you get an error directly after a parenthesised expression. > > -- > Robin > > On Thu, 31 May 2007 08:09:23 -0700 (PDT) > Akijmo <[EMAIL PROTECTED]> wrote: > >> >> Hi everyone. >> I am new to this Forum, Haskell and i am german, so i am sorry for >> "noob" failures or spelling mistakes. >> >> I am currently learning for an informatic exam (11th class) and i >> tried to code a function to sum a polynom with a pair of polynoms... >> (I actually want to to code a polynomdivision in which i need this) >> >> But I get the parse error mentioned in the headline. It is referring >> to the first line of the case differentiation. >> Hopefully you can help me, here's the code: >> >> polyplusd :: Polynom -> (Polynom, Polynom) -> Polynom >> polyplusd [] p = p >> polyplusd p [] = p >> polyplusd p@((g1,e1):p1) (n, (q@((g2,e2):p2)) >> | g1>g2 = (g1,e1):(polyplusd p1 (n,q)) >> | g2>g1 = (g2,e2):(polyplusd p (n,p2)) >> | g1==g2 && e1+e2 /=0 =(g1, >> e1+e2):(polyplusd p1 (n,p2)) | otherwise = polyplusd p1 (n,p2) > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- View this message in context: http://www.nabble.com/Parse-error-on-input-%22%7C%22-tf3847082.html#a10899124 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monads and constraint satisfaction problems (CSP)
On Thu, May 31, 2007 at 10:42:57AM -0700, Greg Meredith wrote: > All, > > All this talk about Mathematica and a reference to monadic treatments of > backtracking reminded me that a year ago i was involved in work on a > Mathematica-like widget. At the time i noticed that a good deal of the > structure underlying LP, SAT and other solvers was terribly reminiscent of > comprehension-style monadic structure. i think i asked Erik Meijer if he > knew of any work done on this and posted to LtU, but nobody seemed to have > understood what i was mumbling about. So, let me try here: does anybody know > of references for a monadic treatment of constraint satisfaction? It's not particularly monadic, but you might check out "Modular Lazy Search for Constraint Satisfaction Problems" http://cse.ogi.edu/PacSoft/publications/.../modular_lazy_search.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Monads and constraint satisfaction problems (CSP)
All, All this talk about Mathematica and a reference to monadic treatments of backtracking reminded me that a year ago i was involved in work on a Mathematica-like widget. At the time i noticed that a good deal of the structure underlying LP, SAT and other solvers was terribly reminiscent of comprehension-style monadic structure. i think i asked Erik Meijer if he knew of any work done on this and posted to LtU, but nobody seemed to have understood what i was mumbling about. So, let me try here: does anybody know of references for a monadic treatment of constraint satisfaction? BTW, i think this could have a lot of bang-for-buck because the literature i read exhibited two basic features: - the "standard" treatments (even by CS-types) are decidedly not compositional - the people in the field who face industrial strength csp problems report that they have to take compositional approaches because the problems are just too large otherwise (both from a human engineering problem as well as a computational complexity problem) 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parse error on input "|"
The second argument of the second line of the definition does not match the expected type. (Polynom,Polynom) is a tuple, not a list, so []::(a,a) is not well typed for any a. Dan Akijmo wrote: Hi everyone. I am new to this Forum, Haskell and i am german, so i am sorry for "noob" failures or spelling mistakes. I am currently learning for an informatic exam (11th class) and i tried to code a function to sum a polynom with a pair of polynoms... (I actually want to to code a polynomdivision in which i need this) But I get the parse error mentioned in the headline. It is referring to the first line of the case differentiation. Hopefully you can help me, here's the code: polyplusd :: Polynom -> (Polynom, Polynom) -> Polynom polyplusd [] p = p polyplusd p [] = p polyplusd p@((g1,e1):p1) (n, (q@((g2,e2):p2)) | g1>g2 = (g1,e1):(polyplusd p1 (n,q)) | g2>g1 = (g2,e2):(polyplusd p (n,p2)) | g1==g2 && e1+e2 /=0 =(g1, e1+e2):(polyplusd p1 (n,p2)) | otherwise = polyplusd p1 (n,p2) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Network.HTTP+ByteStrings Interface--Or: How to shepherd handles and go with the flow at the same time?
The HAppS HTTP code basically delivers the first 64k and a handle to acquire the rest. The 99% or higher case is that the document fits in memory so the 64k bound is fine. If you have something bigger, the user is going to have to decide how to handle that on a case by case basis. Note: chunk-encoding means that there is no theoretical limit to how big an HTTP request or response may be. -Alex- Jules Bean wrote: I've been having something of a discussion on #haskell about this but I had to go off-line and, in any case, it's a complicated issue, and I may be able to be more clear in an email. The key point under discussion was what kind of interface the HTTP library should expose: synchronous, asynchronous? Lazy, strict? As someone just pointed out, "You don't like lazy IO, do you?". Well, that's a fair characterisation. I think unsafe lazy IO is a very very cute hack, and I'm in awe of some of the performance results which have been achieved, but I think the disadvantages are underestimated. Of course, there is a potential ambiguity in the phrase 'lazy IO'. You might interpret 'lazy IO' quite reasonably to refer any programming style in which the IO is performed 'as needed' by the rest of the program. So, to be clear, I'm not raising a warning flag about that practice in general, which is a very important programming technique. I'm raising a bit of a warning flag over the particular practice of achieving this in a way which conceals IO inside thunks which have no IO in their types: i.e. using unsafeInterleaveIO or even unsafePerformIO. Why is this a bad idea? Normally evaluating a haskell expression can have no side-effects. This is important because, in a lazy language, you never quite know[*] when something's going to be evaluated. Or if it will. Side-effects, on the other hand, are important things (like launching nuclear missiles) and it's rather nice to be precise about when they happen. One particular kind of side effect which is slightly less cataclysmic (only slightly) is the throwing of an exception. If pure code, which is normally guaranteed to "at worst" fail to terminate can suddenly throw an exception from somewhere deep in its midst, then it's extremely hard for your program to work out how far it has got, and what it has done, and what it hasn't done, and what it should do to recover. On the other hand, no failure may occur, but the data may never be processed, meaning that the IO is never 'finished' and valuable system resources are locked up forever. (Consider a naive program which reads only the first 1000 bytes of an XML document before getting an unrecoverable parse failure. The socket will never be closed, and system resources will be consumed permanently.) Trivial programs may be perfectly content to simply bail out if an exception is thrown. That's very sensible behaviour for a small 'pluggable' application (most of the various unix command line utilities all bail out silently or nearly silently on SIGPIPE, for example). However this is not acceptable behaviour in a complex program, clearly. There may be resources which need to be released, there may be data which needs saving, there may be reconstruction to be attempted on whatever it was that 'broke'. Error handling and recovery is hard. Always has been. One of the things that simplifies such issues is knowing "where" exceptions can occur. It greatly simplifies them. In haskell they can only occur in the IO monad, and they can only occur in rather specific ways: in most cases, thrown by particular IO primitives; they can also be thrown 'To' you by other threads, but as the programmer, that's your problem!. Ok. Five paragraphs of advocacy is plenty. If anyone is still reading now, then they must be either really interested in this problem, or really bored. Either way, it's good to have you with me! These issues are explained rather more elegantly by Oleg in [1]. So, where does that leave the HTTP library? Well here are the kinds of interface I can imagine. I'm deliberately ignoring all the stuff about request headers, request content, and imagining that this is all about URL -> ByteString. Here are the options that occur to me: A. Strict, synchronous GET sSynGET :: URL -> IO ByteString Quite simply blocks the thread until the whole data has arrived. Throws some kind of exception on failure, presumably. This is a simple primitive, appropriate for relatively small files (files which fit comfortably in your memory) and simple programs. It's also great for programs which want to take their own control over the degree of asynchrony; they can just fork as many threads as they choose to GET with. B. Strict, asynchronous GET sAsynGET :: URL -> IO (MVar ByteString) Download the entire data, but do it in a separate thread. Give me an MVar so I can synchronise on the data's arrival in whichever way suits my program best. Suitable for small files which fit conveniently in memory.
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
On Thursday 31 May 2007 17:46:38 Al Falloon wrote: > I kind of saw the overlapping enumeration case as just a common special > case of the AST problem. Theoretically, yes. In practice, this is quite an important distinction because enumerations do not suffer from the obfuscated error messages that arise when you have polymorphic variants derived from "too much" inference. > I can't think of a lightweight way to encode overlapping enumerations in > Haskell. I'd like to know if this is possible in Haskell. > If someone can come up with one, it would probably shed some light on the > right direction for the AST problem. I should emphasise that not everyone agrees with me here. I've noticed that Jacques Garrigue uses polymorphic variants in that way (their intended way). I have tried several times but I always give up and revert to ordinary variants for their simpler error messages. Sometimes I replace the ordinary variants with polymorphic variants when the program is complete, but only to make me look more intelligent. Just to clarify what you mean, the following "subst" function substitutes variables `Var _ in an expression and OCaml infers that the output expression needs no `Var constructor (the type 'b): # let rec subst vars = function | `Int _ as e -> e | `Var var -> List.assoc var vars | `Add(f, g) -> `Add(subst vars f, subst vars g);; val subst : ('a * ([> `Add of 'b * 'b | `Int of 'c ] as 'b)) list -> ([< `Add of 'd * 'd | `Int of 'c | `Var of 'a ] as 'd) -> 'b = You can see how inferred sum types can get unwieldy quite quickly. > The other uses of PV, I hadn't been aware of, but it makes a lot of sense. Yes. I've found them quite useful in application areas that are better suited to more dynamic typing, like GUI and web programming. Polymorphic variants do a lot to close the gap there. Incidentally, I have heard people express concerns that polymorphic variants will let more bugs through the static type checker because they are weaker. I have never had a run-time problem caused by an unintended inference. My problems with polymorphic variants always boil down to the error messages. For example, forgetting the last "var" in that function allows it to pass type checking with a completely different inferred type: # let rec subst vars = function | `Int _ as e -> e | `Var var -> List.assoc var vars | `Add(f, g) -> `Add(subst vars f, subst g);; val subst : (('b * ([> `Add of 'c * (([< `Add of 'd * 'a | `Int of 'e | `Var of 'b ] as 'd) -> 'c) | `Int of 'e ] as 'c)) list as 'a) -> 'd -> 'c = -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
On Thursday 31 May 2007, Al Falloon wrote: > OCaml has been getting a lot of mileage from its polymorphic variants > (which allow structural subtyping on sum types) especially on problems > relating to AST transformations and the infamous "expression problem". > > Has there been any work on extending Haskell's type system with > structural subtyping? > > What is the canonical solution to the expression problem in Haskell? > > What techniques do Haskellers use to simulate subtyping where it is > appropriate? > > I bring this up because I have been working on a Scheme compiler in > Haskell for fun, and something like polymorphic variants would be quite > convinent to allow you to specify versions of the AST (input ast, after > closure conversion, after CPS transform, etc.), but allow you to write > functions that work generically over all the ASTs (getting the free > vars, pretty printing, etc.). I'm not sure if it qualifies (as, I don't know OCaml), but you might want to look into some of the papers proposing extensible record systems for Haskell. Some of them note that the same type system extensions for records can be used for variants. Specifically, Daan Leijen's paper "Extensible records with scoped labels" goes into how they might work, although there may be other good papers on the subject. Would such a proposal be comparable to what OCaml has? Unfortunately, I don't think implementing such a proposal is high on the to-do list for any of the compilers currently. There's too little time in the day to build all the type system fanciness everyone could want, I guess. :) -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
Stefan Holdermans wrote: Al, Has there been any work on extending Haskell's type system with structural subtyping? Koji Kagawaga. Polymorphic variants in Haskell. In Andres Loeh, editor, Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell, Portland, Oregon, USA, September 17, 2006, pages 37--47. ACM Press, 2006. [1] What is the canonical solution to the expression problem in Haskell? Not canonical but Loeh and Hinze have proposed open data types: Andres Loeh and Ralf Hinze. Open data types and open functions. In Annalisa Bossi and Michael J. Maher, editors, Proceedings of the 8th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, July 10--12, 2006, Venice, Italy, pages 133--144. ACM Press, 2006. [2] Thanks for the pointers. I will definitely be reading these papers. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] small hack on hasktags to make it collect class names
You can download the modified version from http://mawercer.de/marcweber/hasktags.hs Marc Weber ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parse error on input "|"
You neglected a ) - remember to count your parentheses in future when you get an error directly after a parenthesised expression. -- Robin On Thu, 31 May 2007 08:09:23 -0700 (PDT) Akijmo <[EMAIL PROTECTED]> wrote: > > Hi everyone. > I am new to this Forum, Haskell and i am german, so i am sorry for > "noob" failures or spelling mistakes. > > I am currently learning for an informatic exam (11th class) and i > tried to code a function to sum a polynom with a pair of polynoms... > (I actually want to to code a polynomdivision in which i need this) > > But I get the parse error mentioned in the headline. It is referring > to the first line of the case differentiation. > Hopefully you can help me, here's the code: > > polyplusd :: Polynom -> (Polynom, Polynom) -> Polynom > polyplusd [] p = p > polyplusd p [] = p > polyplusd p@((g1,e1):p1) (n, (q@((g2,e2):p2)) > | g1>g2 = (g1,e1):(polyplusd p1 (n,q)) > | g2>g1 = (g2,e2):(polyplusd p (n,p2)) > | g1==g2 && e1+e2 /=0 =(g1, > e1+e2):(polyplusd p1 (n,p2)) | otherwise = polyplusd p1 (n,p2) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
Jon Harrop wrote: On Thursday 31 May 2007 15:36:13 Al Falloon wrote: I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). Although this is the theoretical justification for OCaml's polymorphic variants, it is not their most common use. They are more commonly used to implement overlapping enumerations (see LablGL), to avoid sum type declarations with short scope (e.g. [`Some|`None| `Maybe] inside a single function) and when sum types keep changing during development. I kind of saw the overlapping enumeration case as just a common special case of the AST problem. I can't think of a lightweight way to encode overlapping enumerations in Haskell. If someone can come up with one, it would probably shed some light on the right direction for the AST problem. The other uses of PV, I hadn't been aware of, but it makes a lot of sense. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
Thomas Schilling wrote: I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). Proper subtyping or at least extendable ADTs would be nicer, but you can have type-checked progress flags using phantom types, e.g.: I thought that phantom types might be a solution, but how to you statically ensure that the AST has only the constructors that are appropriate for each phase? GADTS maybe. Constructors allowed in all phases, or in just one can be encoded easily enough. But then how do you encode a constructor that can be in two out of three phases? Maybe two phantom types? It all starts getting a little hairy. I will have to go through the papers that the others have provided to see if someone has already explored this direction. I have an inkling that there is a good idea here, it just might take some time to tease it out. Thanks for the replies. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parse error on input "|"
Hi everyone. I am new to this Forum, Haskell and i am german, so i am sorry for "noob" failures or spelling mistakes. I am currently learning for an informatic exam (11th class) and i tried to code a function to sum a polynom with a pair of polynoms... (I actually want to to code a polynomdivision in which i need this) But I get the parse error mentioned in the headline. It is referring to the first line of the case differentiation. Hopefully you can help me, here's the code: polyplusd :: Polynom -> (Polynom, Polynom) -> Polynom polyplusd [] p = p polyplusd p [] = p polyplusd p@((g1,e1):p1) (n, (q@((g2,e2):p2)) | g1>g2 = (g1,e1):(polyplusd p1 (n,q)) | g2>g1 = (g2,e2):(polyplusd p (n,p2)) | g1==g2 && e1+e2 /=0 =(g1, e1+e2):(polyplusd p1 (n,p2)) | otherwise = polyplusd p1 (n,p2) -- View this message in context: http://www.nabble.com/Parse-error-on-input-%22%7C%22-tf3847082.html#a10895849 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
apfelmus wrote: Al Falloon wrote: OCaml has been getting a lot of mileage from its polymorphic variants (which allow structural subtyping on sum types) especially on problems relating to AST transformations and the infamous "expression problem". Has there been any work on extending Haskell's type system with structural subtyping? There's OO'Haskell but I don't know much about it. The problem with subtyping is that it renders type inference undecidable and is more limited than parametric polymorphism. It's more like a "syntactic sugar", you can always explicitly pass around embeddings (a' -> a) and projections (a -> Maybe a'). I can see how nominal subtyping would make type inference a pain, but I'm pretty sure its solvable for structural subtyping because the inference algorithm can simply grow the type as it unifies the different terms. I think this paper describes how they pulled it off for OCaml: http://citeseer.ist.psu.edu/garrigue02simple.html Its true that subtyping can be considered syntactic sugar, but its the same sort of syntactic sugar as typeclasses, which are pretty popular. In fact, the mapping you suggest is so close to the mapping of typeclasses that it suggests some sort of convenient subtyping library using typeclasses might be possible. Has anyone looked into this? Is that what Data.Typeable provides? What is the canonical solution to the expression problem in Haskell? What techniques do Haskellers use to simulate subtyping where it is appropriate? I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). For this use case, there are some techniques available, mostly focussing on traversing the AST and not so much on the different data constructors. Functors, Monads and Applicative Functors are a structured way to do that. S. Liang, P. Hudak, M.P. Jones. Monad Transformers and Modular Interpreters. http://web.cecs.pdx.edu/~mpj/pubs/modinterp.html C. McBride, R. Paterson. Applicative Programming with Effects. http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf B. Bringert, A. Ranta. A Pattern for Almost Compositional Functions. http://www.cs.chalmers.se/~bringert/publ/composOp/composOp.pdf Thank you, I will definitely look through those. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
apfelmus wrote: Al Falloon wrote: OCaml has been getting a lot of mileage from its polymorphic variants (which allow structural subtyping on sum types) especially on problems relating to AST transformations and the infamous "expression problem". Has there been any work on extending Haskell's type system with structural subtyping? There's OO'Haskell but I don't know much about it. The problem with subtyping is that it renders type inference undecidable and is more limited than parametric polymorphism. It's more like a "syntactic sugar", you can always explicitly pass around embeddings (a' -> a) and projections (a -> Maybe a'). Quite. So another interesting question to ask is 'has anyone proposed any good syntactic sugar?' Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
Mark T.B. Carroll wrote: I don't know what the infamous "expression problem" is, nor am I familiar with polymorphic variants or structural subtyping, but have you looked at the Data.Generics.* stuff and Scrap Your Boilerplate papers? They may be relevant. The expression problem is "a new name for an old problem", basically being able to extend a data type and functions over the data type in seperate modules with no knowledge of each other. Here is a link to (I think) the original description: http://www.daimi.au.dk/~madst/tool/papers/expression.txt Structural subtyping is something like "duck typing" in dynamic languages, but checked at compile time. For records, it means that if you only access two labels then the function will work on any record that has those labels with those types, even if it may have more labels. For variants (or sum-types, or tagged unions, or whatever they are called in Haskell) it means that if your function can handle certain cases, then it can also handle values that range over less cases. So in pseudo-Haskell with imaginary subtyping: data Vertical a = U a | D a data Horizontal a = L a | R a data Direction a = #Vertical a | #Horizontal a -- borrowing ocaml syntax: this means that Direction shares constructors with Vertical and Horizontal getData :: Direction a -> a getData (U a) = a getData (D a) = a getData (L a) = a getData (R a) = a getLeftStick :: IO (Vertical Int) getRightStick :: IO (Horizontal Int) main = do { accel <- getLeftStick; print (getData accel) } So getData doesn't care that accel is Horizontal and not Direction because Horizontal is a sub-type of direction. Of course, in this syntax since you named the subtyping relationship its more technically nominal subtyping (like in traditional static OO languages) not structural subtyping (which figures out the subtype relationship from the structure automatically, so if we just reused the U,D,L, and R constructors in Direction). I have looked into SYB briefly. I will probably end up using it to keep the amount of code to a minimum, but it won't save me from having to define a different data type for each version of the AST if I want to preserve type safety. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
Al Falloon wrote: > OCaml has been getting a lot of mileage from its polymorphic variants > (which allow structural subtyping on sum types) especially on problems > relating to AST transformations and the infamous "expression problem". > > Has there been any work on extending Haskell's type system with > structural subtyping? There's OO'Haskell but I don't know much about it. The problem with subtyping is that it renders type inference undecidable and is more limited than parametric polymorphism. It's more like a "syntactic sugar", you can always explicitly pass around embeddings (a' -> a) and projections (a -> Maybe a'). > What is the canonical solution to the expression problem in Haskell? > > What techniques do Haskellers use to simulate subtyping where it is > appropriate? > > I bring this up because I have been working on a Scheme compiler in > Haskell for fun, and something like polymorphic variants would be quite > convinent to allow you to specify versions of the AST (input ast, after > closure conversion, after CPS transform, etc.), but allow you to write > functions that work generically over all the ASTs (getting the free > vars, pretty printing, etc.). For this use case, there are some techniques available, mostly focussing on traversing the AST and not so much on the different data constructors. Functors, Monads and Applicative Functors are a structured way to do that. S. Liang, P. Hudak, M.P. Jones. Monad Transformers and Modular Interpreters. http://web.cecs.pdx.edu/~mpj/pubs/modinterp.html C. McBride, R. Paterson. Applicative Programming with Effects. http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf B. Bringert, A. Ranta. A Pattern for Almost Compositional Functions. http://www.cs.chalmers.se/~bringert/publ/composOp/composOp.pdf The fundamental way is to compose your data types just like you compose your functions. Here's an example data Expr a= A (ArithExpr a) | C (Conditional a) data ArithExpr a = Add a a | Mul a a data Conditional a = IfThenElse a a a | CaseOf a [(Int,a)] newtype Expression = E (Expr Expression) Now, functions defined on (Conditional a) can be reused on Expressions, although with some tedious embedding an projecting. I think that the third paper mentioned above makes clever use of GADTs to solve this. The topic of Generic programming is related to that and Applicative Functors make a reappearance here (although not always explicitly mentioned). http://haskell.org/haskellwiki/Research_papers/ /Generics#Scrap_your_boilerplate.21 Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
On Thursday 31 May 2007 11:39:14 [EMAIL PROTECTED] wrote: > ... > Mathematica changed a bit the perspective, along - perhaps - the same > lines as Schoonschip, where the fundamental stuff was *rewriting/ > transformations*. So, Mathematica since the begininng was equipped with > a very powerful pattern-matcher/substitution contraption. For the sake > of efficiency it was less powerful than a general unifier, but it was > really nice (and it existed already in SMP, before the birth of > Mathematica). Now, again, somebody would do that in 4 days?? > The semantic pattern-matcher within an algebraic package, is worlds > apart from the syntactic/structural pattern-matcher of Haskell. Can you elaborate on this? I would imagine that the pattern matcher in a term-level Haskell interpreter would be quite similar to one from a toy Mathematica-like rewriter. Also, what aspects of this do you think would take more than 4 days? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
On Thursday 31 May 2007 15:36:13 Al Falloon wrote: > I bring this up because I have been working on a Scheme compiler in > Haskell for fun, and something like polymorphic variants would be quite > convinent to allow you to specify versions of the AST (input ast, after > closure conversion, after CPS transform, etc.), but allow you to write > functions that work generically over all the ASTs (getting the free > vars, pretty printing, etc.). Although this is the theoretical justification for OCaml's polymorphic variants, it is not their most common use. They are more commonly used to implement overlapping enumerations (see LablGL), to avoid sum type declarations with short scope (e.g. [`Some|`None| `Maybe] inside a single function) and when sum types keep changing during development. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] equations and patterns
On Thu, 31 May 2007, Stefan Holdermans wrote: > Mingli, > > > > class Lattice e where > > > join :: e -> e -> e > > > meet :: e -> e -> e > > > > > > -- associative law > > > join x (join y z) = join (join x y) z > > > join (join x y) z = join x (join y z) > > If you are not to sell your soul to advanced and perhaps obscure type > hacking, you cannot express laws like this *in* Haskell. > > More concretely, one usually does not provide such laws as default > implementations of a class' methods. Instead, they are stated in, for > instance, comments and the documentation that goes with your library. > These then form an informal obligation for programmers that provide > instances of your class to let these instances obey the laws. Like here: http://darcs.haskell.org/numericprelude/src/Algebra/Lattice.hs > If you provide an instance of the class you could use testing > framework, e.g., QuickCheck [1], to assert that the required > properties hold. I assume they can in some way also be used for GHC's optimizer. http://www.haskell.org/haskellwiki/Playing_by_the_rules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). Proper subtyping or at least extendable ADTs would be nicer, but you can have type-checked progress flags using phantom types, e.g.: data LT flag = L String (LT flag) | A (LT flag) (LT flag) | Var String data Input data Renamed data CPSed data ConstPropd rename :: LT Input -> LT Renamed cps :: LT Renamed -> LT CPSed constantPropagate :: LT CPSed -> LT ConstPropd dumpExpr :: (forall a. LT a) -> String -- ignores progress flag This way you have at least a way to check that the proper phases have been run before. It might even be possible to store different things in the nodes (not tested), like in: newtype Ident = MkIdent String class VarType flag vt | flag -> vt instance VarType Input String instance VarType Renamed Ident instance VarType CPSed Ident instance VarType ConstPropd Ident data LT flag = (VarType flag vt => L vt (LT flag)) | ... (This probably doesn't work, but you get the idea.) / Thomas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
Al, Has there been any work on extending Haskell's type system with structural subtyping? Koji Kagawaga. Polymorphic variants in Haskell. In Andres Loeh, editor, Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell, Portland, Oregon, USA, September 17, 2006, pages 37--47. ACM Press, 2006. [1] What is the canonical solution to the expression problem in Haskell? Not canonical but Loeh and Hinze have proposed open data types: Andres Loeh and Ralf Hinze. Open data types and open functions. In Annalisa Bossi and Michael J. Maher, editors, Proceedings of the 8th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, July 10--12, 2006, Venice, Italy, pages 133--144. ACM Press, 2006. [2] Cheers, Stefan [1] http://portal.acm.org/citation.cfm? id=1159842.1159848&coll=ACM&dl=ACM&type=series&idx=1159842&part=Proceedi ngs&WantType=Proceedings&title=Haskell&CFID=24140934&CFTOKEN=52915302 [2] http://portal.acm.org/citation.cfm? id=1140335.1140352&coll=ACM&dl=ACM&type=series&idx=1140335&part=Proceedi ngs&WantType=Proceedings&title=International%20Conference%20on% 20Principles%20and%20Practice%20of%20Declarative% 20Programming&CFID=24141725&CFTOKEN=61657761 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Crazy idea: overloading function application notation
On Thu, 31 May 2007, Jon Harrop wrote: > This is a crazy idea I've been working on: overload the syntax "x y" so it can > mean function application "f x = f(x)" or multiplication "x y = x*y". The > reason is simply that I appreciate the brevity of MLs function application > but I also appreciate the brevity of Mathematica's multiplication. > > Is it possible to implement this in Haskell using type classes? Is this "wantable"? > Is there any way this could actually be practicable? On http://www.haskell.org/haskellwiki/Num_instance_for_functions I have described, what happens if you want too many meanings for the same syntax. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Implementing Mathematica
Jon Harrop wrote: Arbitrary precision integers are quite a performance burden and they are rarely used. I would not expect a language that is trying to be efficient to impose arbitrary precision integers (or floats). Apparently you have looked inside a computer *algebra* system, one that does *exact* computations (i.e. on polynomials with exact coefficients, not floats/doubles). Arbitrary precision integers are not a 'burden', they are an absolute necessity. Algorithms on polynomials will almost inevitably produce 'coefficient growth'. Even things as simple as sub-resultant computations (for computing extended GCDs) have this problem. And this is not a fluke or a problem with state-of-the-art, there are known cases where this is inevitable. Like Jerzy, I wonder why I get suckered in to these conversations. I guess we both have this silly need to set the record straight. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
OCaml has been getting a lot of mileage from its polymorphic variants (which allow structural subtyping on sum types) especially on problems relating to AST transformations and the infamous "expression problem". Has there been any work on extending Haskell's type system with structural subtyping? What is the canonical solution to the expression problem in Haskell? What techniques do Haskellers use to simulate subtyping where it is appropriate? I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). -- Alan Falloon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Language extensions
Roberto Zunino wrote: Ah, silly me! I checked that inequality was preserved, but forgot that (==) diverges on infinite list! Indeed, strictly speaking, Eq [] does not satisfy the Eq invariant x==x. All haskell types contain divergence. So all Eq types have exactly this same problem. We 'like' infinite lists because they are a kind of 'productive divergence'. But they still diverge. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Language extensions [was: Memoization]
I really liked this explanation -- very clear, with good analogies. Thanks! Martin My music: http://www.youtube.com/profile?user=thetonegrove Claus Reinke wrote: quantified types (forall/exist): an easy way to memorize this is to think of 'forall' as a big 'and' and of 'exists' as a big 'or'. e :: forall a. a -- e has type 'Int' and type 'Bool' and type .. e :: exists a. a -- e has type 'Int' or type 'Bool' or type .. That doesn't entirely make sense. (What am I on about? That doesn't make *any* sense...) indeed?-) then you've probably already figured out what those types mean! there aren't many variations of an expression that has *all* types ("you can't please everyone"), and if an expression has a type but we have no way of knowing what that type is, there isn't much we can do with it (like advice from the Oracle of Delphi). but both of these kinds of quantified types make a lot more sense in larger contexts. lets take 'forall'/'big and' first: the problem with 'forall a. a' is to produce something that is everything to everyone, which is rather hard; but what about 'forall a. a -> a'? that is like a general shipping agency - they don't care what you give them, they just put it in a box and move it from one place to another (if it doesn't like to be shipped in such an indifferent way, it'll break, but that's not their problem); such general shipping is both 'Integer' shipping *and* 'String' shipping *and* ..; other examples are 'forall a. a -> a -> a', which is a general selector (given two 'a's, it returns one of them), or 'forall a,b. a -> b -> a' (given an 'a' and a 'b', it returns the 'a'). 'id :: forall a. a -> a' can be instantiated to 'id :: Bool -> Bool' *and* to 'id :: Char -> Char' *and* to all other identities on rank-1 types besides, so one could say that it really has *all* of those types. what about 'exists'/'big or' then? the problem with 'exists a. a' is that while we know there exists a type, we have no way of knowing what that type is, so we can't really do anything with an expression of such a type. that is very much like an abstract data type, implemented on top of a hidden representation type. what we need are some operations on that abstract type, so how about 'exists r.(r a, r a -> a -> r a, r a -> a)' we still don't know what 'r' is, but we have some 'r a', we have a way to combine 'r a' and 'a' into a new 'r a', and a way to extract an 'a' from an 'r a', so we're no longer entirely helpless. in fact, that looks a lot like an abstract container type, perhaps a stack with push and top, or a queue with add and front, or a cell with put and get. whatever it may be, the 'r' is hidden, so it could be '([a], [a]->a->[a], [a]->a)' *or* it could be '(Set a, Set a -> a -> Set a, Set a -> a)' *or* it could be based on *any* other rank-1 type constructor. hth, claus oracle advice: 'invade :: exists great_empire. great_empire -> ()' ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Language extensions
Tomasz Zielonka wrote: On Wed, May 30, 2007 at 11:21:45PM +0200, Roberto Zunino wrote: ($!) Data.List.repeat -- ;-) unbounded types You got me - I'm not sure how to respond to that. Let's try: this function doesn't preserve computable equality. Ah, silly me! I checked that inequality was preserved, but forgot that (==) diverges on infinite list! Indeed, strictly speaking, Eq [] does not satisfy the Eq invariant x==x. BTW, why so many exclamation marks in your code? Are they essential? Only strict g's are allowed in parametericity, IIUC. Otherwise: let g = \x -> (x,4) f (map g []) == g (f []) iff f [] == g bottom iff bottom == (bottom,4)which is false. Zun. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Implementing Mathematica
Jon Harrop wrote: On Wednesday 30 May 2007 22:15:55 Andrew Coppin wrote: Note that (as I understand it) GHC implements Haskell's Integer type using the GMP. And for some reason or other, they want to remove this feature... Arbitrary precision integers are quite a performance burden and they are rarely used. I would not expect a language that is trying to be efficient to impose arbitrary precision integers (or floats). In Haskell, Int gives you the standard signed, fixed size integer for your machine, and Integer gives arbitrary precision integers. Int8, Int16, ... provide signed ints of a known size, and Word8, Word16 give the unsigned. They are all instances of Num, so integer literals will be whatever type is needed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Building error Gtk2Hs under GHC 6.6.1 on Solaris 10 x86
On Thu, 2007-05-31 at 13:48 +0200, Christian Maeder wrote: > How about switching from sed to perl, then? /me runs away screaming Actually the easier fix was to not look for an optional "qualified" string (ie dropping the \(qualified \)* clause) as it turns out we didn't need it anyway. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Crazy idea: overloading function application notation
On 31/05/07, Jon Harrop <[EMAIL PROTECTED]> wrote: Is it possible to implement this in Haskell using type classes? Is there any way this could actually be practicable? I had a go but didn't manage to quite get it. Here's my attempt, and the error it produces: {-# OPTIONS_GHC -fglasgow-exts #-} type Endo a = a -> a -- Dummy instances to satisfy the (Show n, Eq n) => Num n constraints instance Show (Endo a) where show _ = "" instance Eq (Endo a) where _ == _ = False instance Num a => Num (Endo a) where fromInteger x = (fromInteger x *) x + y = \z -> x z + y z x * y = \z -> x z * y z abs x = error "Aaargh." signum x = error "Aaargh." main = print (2 3) /home/david/hs/sandbox/application-multiplication.hs:15:14: No instance for (Num (t -> a)) arising from the literal `2' at /home/david/hs/sandbox/application-multiplication.hs:15:14-16 Possible fix: add an instance declaration for (Num (t -> a)) In the first argument of `print', namely `(2 3)' In the expression: print (2 3) In the definition of `main': main = print (2 3) Failed, modules loaded: none. It seems to be wanting a more general instance than the one I'm providing, for whatever reason. Using print ((2 :: Endo Integer) 3) works, but that's hardly satisfactory. -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: New book: Real-World Haskell!
Simon Marlow: > While we're on fish, what's wrong with the humble Haddock? :-) It may at least make for a tasty curry ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Building error Gtk2Hs under GHC 6.6.1 on Solaris 10 x86
How about switching from sed to perl, then? Cheers Christian Duncan Coutts schrieb: > This is a bug in mk/chsDepend(.in) probably due to some difference in > how sed works in Solaris compared to Linux. > > the mk/chsDepend shell script looks at a .chs file and tries to find all > the lines that look like: > > {#import Some.Module.Name#} > > and then find the .chi files corresponding to those import lines. It > looks from the error message that it's picking up "{#import" as if it > were a module. > > The shell/sed code that is probably going wrong is: > > DEPS=`$GREP "{#import" $FULLNAME 2> /dev/null \ >| $SED 'y/./\//;s/^{#import \(qualified \)*\([a-zA-Z1-9/]*\)#}.*/\2/'`; > > testing this with standard solaris sed (on Solaris 9) reveals the > problem, standard Solaris sed is terrible! :-) > > The problem is that standard Solaris /usr/bin/sed does not allow * on > sub-expressions, for example this sed regexp "\(bar\)*" does not match > the string "bar bar". The other Solaris sed that is not on the path by > default works fine (/usr/xpg4/bin/sed). Well actually it needs a minor > patch too, it doesn't like the escape in "y/./\//", but if we change it > to "y|.|/|" then it's happy. > > So the solution I think is for me to change the configure script to look > for /usr/xpg4/bin/sed in preference to /usr/bin/sed on Solaris and also > to make that other minor syntax fix. > > The workaround you can try is to edit mk/chsDepend and set SED to either > gnu sed or to /usr/xpg4/bin/sed though in the latter case you'll also > need to fix the "y|.|/|" bit. Then you'll need to make clean and make > again. > > Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Crazy idea: overloading function application notation
This is a crazy idea I've been working on: overload the syntax "x y" so it can mean function application "f x = f(x)" or multiplication "x y = x*y". The reason is simply that I appreciate the brevity of MLs function application but I also appreciate the brevity of Mathematica's multiplication. Is it possible to implement this in Haskell using type classes? Is there any way this could actually be practicable? i'm not sure about practicalities - since Haskell programs are mostly identifiers and their applications, redefining application is going to lead to confusion. general rule for extending pure functional languages: do not mess with application, or you risk losing your nice theory. a rather steep price to pay for replacing '*' with ' ', no? you could, however, define a 'Num' instance for functions so that 'f * g = f . g' and 'fromInteger n = fromInteger . const n' or similar (though the types are not likely to make you happy), or you could try replacing the standard 'Num' class with one permitting differently- typed parameters to '(*)', and then try to define multiplication as application rather than composition.. (and if you think that is confusing, think again about overloading application;-) the rest of this message will not help with your particular problem, but is in reply to your subject line: in general, Haskeller's like to enjoy the advantages of overloading something so fundamental as application without endangering that fundament, even if that means a little more typing to indicate where a non-standard overloading is possible. so overloaded application uses a different notation and conventions. recall that '($)' is function application, and consider the following types: flip ($) :: a -> (a -> b) -> b (>>=) :: (Monad m) => m a -> (a -> m b) -> m b you'll notice that monadic bind corresponds to reverse function application, lifted into a monad. of course, there are many ways to do such lifting, so it is interesting to consider what the particular choice of monadification here means. if we permit monadic effects in all of parameter, function, and result, we'd get a type like this for lifted, reversed function application: m a -> m (m a -> m b) -> m b the type of '(>>=)' differs from this in two positions, meaning no monadic effects while computing the function, and no monadic effects in the function parameter _after_ substitution into the function body. the latter implies that, even though Haskell's standard application is based on call-by-need (or call-by-name, since sharing isn't required), its monadic application is based on call-by-value: any monadic effects in computing the argument have to be executed _before_ passing the (effect-free part of the) argument to the function. i've often wondered about this discrepancy. but if you just want overloaded application, rather than mess with the meaning and notation of built-in application, Monads may be the way to go. it might also give one indication of why Monads are so popular in Haskell, and so little heard of in languages which do allow unconstrained overloading of application. claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: New book: Real-World Haskell!
Clifford Beshers wrote: Scott Cruzen wrote: I'd like to suggest the Mantis shrimp because they have excellent vision, they're long lived and they pack a punch. They certainly do. An excellent choice. Personally, I'd like to see the Giant Sea Bass., just because they're so stately: http://week.divebums.com/2006/Sep05-2006/index.html http://week.divebums.com/2006/Aug28-2006/index.html Actually, I'd like to see my favorite fish, the Sarcastic Fringehead, but I'm trying to be somewhat realistic: http://week.divebums.com/2006/Oct02-2006/fringehead_steve-murvine.jpg While we're on fish, what's wrong with the humble Haddock? :-) Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Resolved: ffi linking problem
jeff p wrote: In case anyone else finds this useful... My linking problem was finally resolved by using the -fvia-C flag when compiling with ghc. Thanks to Stefan O'Rear who pointed out the possibility and wrote: Does using -fvia-C help at all? The C compiler understands header files and is sometimes better equipped to resolve things. If -fvia-C fixes your problem, then your code has a bug, strictly speaking. If your foreign call requires some information from a header file, then the right way to call it is by making a small C wrapper function and calling that. Bear in mind that we'll be deprecating -fvia-C in the future, and also that you might want your code to work in GHCi too, which doesn't read any header files when compiling foreign imports. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
On Thursday 31 May 2007 00:10:27 Stefan O'Rear wrote: > You said that constructing a specification is the hardest part of > implementing Mathematica, and you also say you managed to clone it. > Can you reveal your specification, or did WR give you a NDA? NDA, although I did most of the reverse engineering independently beforehand. They use lots of nifty tricks (basically any trick that you can do easily in C) but there were plenty of other tricks they didn't try because they are far from obvious in C. I found an interesting alternative was to keep a lazily evaluated set of the symbols found in each subexpression. This could be used to cull searches and avoid unnecessary rewriting but also had no significant performance overhead. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
This will be a long sermon. Sorry. Lennart Augustsson writes: Why do you seem so in awe of Mathematica? It's just another language with a good set of libraries. Claims that it is the best, fastest, etc comes from Wolfram advertising, no doubt. :) All this discussion began to degenerate a bit (I don't know why, but it happens almost always when people begin to speak about Mathematica in a context far from it... There is, it seems, some Original Sin in this business, but most of you are too young to remember the well known Wolfram Controversy when SMP transmuted into Mathematica...) Anyway... Mathematica made its career not as a *language*, and not immediately as a set of libraries, but as an *integrated package* capable of doing SYMBOLIC mathematics, with a very decent user interfacing and graphics a bit better than its competitors. The conditions of its career were far from obvious. The World had many symbolic math packages: Reduce, Macsyma, Schoonschip (beloved by high- energy physicists), Maple, Scratchpad2/Axiom, later MuSIMP/MuMATH for small platforms, etc. The group of Wolfram knew all that, they knew that in order to implement something reasonable, one has to fulfil several conditions. * The algebraic expressions must have a sound design, there must be a sufficiently universal, yet efficient representation of math formulae. For the polynomial arithmetic this is trivial, it is one of my standard Haskell exercices at the undergraduate level. The symbolic differentia- tion as well. But already the polynomial factorization may be a mess, and requires a good deal of algorithmic knowledge. I am reluctant to believe that anybody implemented this in 4 days... Anybody tried Zassenhaus? Not *too* complicated, implemented in Pari and elsewhere, but quite elaborate. For general functors the *simplification* issue is not decidable. You can't assess a given representation as "the best" formula with a given semantics. Again, the simplifier/evaluator is a complicated part of the package, not something you can do in a few days. Please, have a look on the internal structure of DoCon of Sergei Mechveliani, he did a lot of work in Haskell, and the story is still incomplete. (Let's omit the real mess, for example the Risch symbolic integration algorithms, efficient Gröbner bases, etc.) * First symbolic packages treated *first* the symbolic expressions as something to be evaluated/simplified. One sees that Maple has been built on this principle. Mathematica changed a bit the perspective, along - perhaps - the same lines as Schoonschip, where the fundamental stuff was *rewriting/ transformations*. So, Mathematica since the begininng was equipped with a very powerful pattern-matcher/substitution contraption. For the sake of efficiency it was less powerful than a general unifier, but it was really nice (and it existed already in SMP, before the birth of Mathematica). Now, again, somebody would do that in 4 days?? The semantic pattern-matcher within an algebraic package, is worlds apart from the syntactic/structural pattern-matcher of Haskell. This helped a lot to popularize Mathematica, and has been shamelessly abused in the advertising, where our friends used to say "we DO MATHEMATICS with computers". Non-sense, of course... * All the numerical, standard stuff, the interface between the symbolic and the numerical functions, with plots 2D/3D, etc. Too often people speak about that, comparing, say, Matlab with Mathematica (while Matlab has no symbolics, although, being a decent object-oriented language, has tools which permitted the construction of symbolic toolboxes, the linking of the Maple library, etc.) Here the Mathematica team did a serious, thorough job, trying to adapt the richness of this layer to many branches of science and engineering. It was mainly a compilation process, they hardly added anything new, but made a coherent, useful library. Won't repeat it in 4 days, or even in 4 months. = Is there any sense in "making Mathematica with Haskell"? As a package, most certainly no, too much to implement, for what? In order to have another tool of the kind which already exists? Sergei did a feasibility study, and worked hard on the interplay between mathematical structures and the Haskell type system. This, surely, *IS* a useful work. And it should continue. We (in the generic meaning of the True Believers in the Functional Church) can implement other things, for example some formal mathematics dealing with logic, or with the category theory, or with the computational geometry or with (my dream) the *true* implementation of quantum calculi. Knock, knock! Wake up, the sermon is over. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: equations and patterns
Thanks all. I just found this list is very nice. Everybody are so friendly. Regards, Mingli On 5/31/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: mingli yuan wrote: > Seems mathematic axioms and pattern matching are different things. > So how could I rewrite the equations to pattern matching? Which technique > should I learn? Haskell is more suitable for re-writing systems, which are based on oriented equations. The question of orientation is well-described, for example, in the book Term Rewriting and All That by Franz Baader, Tobias Nipkow http://www4.in.tum.de/~nipkow/TRaAT/ I should also point out Clean, where equations like associativity can be stated -- and even proven by Clean's built-in proof assistant. But something can be done in Haskell too. It is quite a general technique: free term algebra. It is explained in two excellent papers, John Hughes: The Design of a Pretty-printing Library http://citeseer.ist.psu.edu/hughes95design.html and Ralf Hinze: Deriving Backtracking Monad Transformers (ICFP2000) http://citeseer.ist.psu.edu/hinze00deriving.html The following Haskell98 code demonstrates the technique for your problem. Well, actually we take quite a similar problem: instead of lattices, we take rings -- or, to be precise, Num. They have two operations (+) and (*) which are too (usually taken to be) associative. This property is not stated in the Num class. Rather, it is described informally in comments. But we can deal with that property formally and directly. We introduce a free term algebra as follows > data FN = N Int | Add FN FN | Mul FN FN > deriving (Eq,Show) and define an embedding of it in Haskell: > instance Num FN where > fromInteger = N . fromInteger > (+) = Add > (*) = Mul So, we can write > test1 :: FN > test1 = (1 + 2) * 3 * 4 + 5 and see the result Add (Mul (Mul (Add (N 1) (N 2)) (N 3)) (N 4)) (N 5) Well, this doesn't actually do anything. It is a free term algebra after all. We need to give it a meaning, that is, define an observation function, or an interpreter > -- Interpreter (the observation function): big-step semantics > interp :: FN -> Int > interp (N x) = x > interp (Add x y) = interp x + interp y > interp (Mul x y) = interp x * interp y Now, evaluating "interp test1" gives 41. One may question the wisdom of this round-about way of adding and multiplying integers. Indeed, first we `compile' an arithmetic expression to the `byte-code'. Next, we wrote a byte-code interpreter, 'interp'. The benefit is that we can insert a `byte-code optimizer' before the interpretation. And here we may associate to the right > mul_right :: FN -> Maybe FN > mul_right (Mul (Mul a b) c) = Just (Mul a (Mul b c)) > mul_right x = congruence mul_right x > test3 = closure mul_right test1 *FreeNum> test3 Add (Mul (Add (N 1) (N 2)) (Mul (N 3) (N 4))) (N 5) or to the left, distribute multiplication over addition > mul_add_distr (Mul a (Add b c)) = Just (Add (Mul a b) (Mul a c)) > mul_add_distr (Mul (Add b c) a) = Just (Add (Mul b a) (Mul c a)) > mul_add_distr x = congruence mul_add_distr x > test4 = closure mul_add_distr test1 *FreeNum> test4 Add (Add (Mul (Mul (N 1) (N 3)) (N 4)) (Mul (Mul (N 2) (N 3)) (N 4))) (N 5) or combine arbitrary number of steps > test5 = closure (compose mul_add_distr mul_right) test1 *FreeNum> test5 Add (Add (Mul (N 1) (Mul (N 3) (N 4))) (Mul (N 2) (Mul (N 3) (N 4 (N 5) Here's the complete code -- Haskell98! -- Free Term algebra for Nums module FreeNum where -- we'll use Ints as the base for simplicity data FN = N Int | Add FN FN | Mul FN FN deriving (Eq,Show) instance Num FN where fromInteger = N . fromInteger (+) = Add (*) = Mul test1 :: FN test1 = (1 + 2) * 3 * 4 + 5 -- Interpreter (the observation function): big-step semantics interp :: FN -> Int interp (N x) = x interp (Add x y) = interp x + interp y interp (Mul x y) = interp x * interp y test2 = interp test1 -- optimizer -- the driver: it applies an optimization step. If it succeeded, it applies -- again. Otherwise, we are finished. -- In other words, compute the transitive closure of the optimization step closure step term = maybe term (closure step) (step term) congruence step (N _) = Nothing congruence step (Add x y) = choose Add (x,step x) (y,step y) congruence step (Mul x y) = choose Mul (x,step x) (y,step y) -- Here's the benefit of laziness: we don't actually do step y -- if step x succeeded choose fn (_,Just x) (y,_)= Just $ fn x y choose fn (x,Nothing) (_,Just y) = Just $ fn x y choose fn (_,Nothing) (_,Nothing) = Nothing -- One step: associate Mul to the right -- (a `Mul` b) `Mul` c ==> a `Mul` (b `Mul` c) -- or: (Mul (Mul a b) c) ==> (Mul a (Mul b c)) mul_right :: FN -> Maybe FN mul_right (Mul (Mul a b) c) = Just (Mul a (Mul b c)) mul_right x = congruence mul_right x -- do the opposite mul_left :: FN -> Maybe FN mul_left (Mul a (Mul b c)) = Just (Mul (Mul a
[Haskell-cafe] Re: equations and patterns
mingli yuan wrote: > Seems mathematic axioms and pattern matching are different things. > So how could I rewrite the equations to pattern matching? Which technique > should I learn? Haskell is more suitable for re-writing systems, which are based on oriented equations. The question of orientation is well-described, for example, in the book Term Rewriting and All That by Franz Baader, Tobias Nipkow http://www4.in.tum.de/~nipkow/TRaAT/ I should also point out Clean, where equations like associativity can be stated -- and even proven by Clean's built-in proof assistant. But something can be done in Haskell too. It is quite a general technique: free term algebra. It is explained in two excellent papers, John Hughes: The Design of a Pretty-printing Library http://citeseer.ist.psu.edu/hughes95design.html and Ralf Hinze: Deriving Backtracking Monad Transformers (ICFP2000) http://citeseer.ist.psu.edu/hinze00deriving.html The following Haskell98 code demonstrates the technique for your problem. Well, actually we take quite a similar problem: instead of lattices, we take rings -- or, to be precise, Num. They have two operations (+) and (*) which are too (usually taken to be) associative. This property is not stated in the Num class. Rather, it is described informally in comments. But we can deal with that property formally and directly. We introduce a free term algebra as follows > data FN = N Int | Add FN FN | Mul FN FN > deriving (Eq,Show) and define an embedding of it in Haskell: > instance Num FN where > fromInteger = N . fromInteger > (+) = Add > (*) = Mul So, we can write > test1 :: FN > test1 = (1 + 2) * 3 * 4 + 5 and see the result Add (Mul (Mul (Add (N 1) (N 2)) (N 3)) (N 4)) (N 5) Well, this doesn't actually do anything. It is a free term algebra after all. We need to give it a meaning, that is, define an observation function, or an interpreter > -- Interpreter (the observation function): big-step semantics > interp :: FN -> Int > interp (N x) = x > interp (Add x y) = interp x + interp y > interp (Mul x y) = interp x * interp y Now, evaluating "interp test1" gives 41. One may question the wisdom of this round-about way of adding and multiplying integers. Indeed, first we `compile' an arithmetic expression to the `byte-code'. Next, we wrote a byte-code interpreter, 'interp'. The benefit is that we can insert a `byte-code optimizer' before the interpretation. And here we may associate to the right > mul_right :: FN -> Maybe FN > mul_right (Mul (Mul a b) c) = Just (Mul a (Mul b c)) > mul_right x = congruence mul_right x > test3 = closure mul_right test1 *FreeNum> test3 Add (Mul (Add (N 1) (N 2)) (Mul (N 3) (N 4))) (N 5) or to the left, distribute multiplication over addition > mul_add_distr (Mul a (Add b c)) = Just (Add (Mul a b) (Mul a c)) > mul_add_distr (Mul (Add b c) a) = Just (Add (Mul b a) (Mul c a)) > mul_add_distr x = congruence mul_add_distr x > test4 = closure mul_add_distr test1 *FreeNum> test4 Add (Add (Mul (Mul (N 1) (N 3)) (N 4)) (Mul (Mul (N 2) (N 3)) (N 4))) (N 5) or combine arbitrary number of steps > test5 = closure (compose mul_add_distr mul_right) test1 *FreeNum> test5 Add (Add (Mul (N 1) (Mul (N 3) (N 4))) (Mul (N 2) (Mul (N 3) (N 4 (N 5) Here's the complete code -- Haskell98! -- Free Term algebra for Nums module FreeNum where -- we'll use Ints as the base for simplicity data FN = N Int | Add FN FN | Mul FN FN deriving (Eq,Show) instance Num FN where fromInteger = N . fromInteger (+) = Add (*) = Mul test1 :: FN test1 = (1 + 2) * 3 * 4 + 5 -- Interpreter (the observation function): big-step semantics interp :: FN -> Int interp (N x) = x interp (Add x y) = interp x + interp y interp (Mul x y) = interp x * interp y test2 = interp test1 -- optimizer -- the driver: it applies an optimization step. If it succeeded, it applies -- again. Otherwise, we are finished. -- In other words, compute the transitive closure of the optimization step closure step term = maybe term (closure step) (step term) congruence step (N _) = Nothing congruence step (Add x y) = choose Add (x,step x) (y,step y) congruence step (Mul x y) = choose Mul (x,step x) (y,step y) -- Here's the benefit of laziness: we don't actually do step y -- if step x succeeded choose fn (_,Just x) (y,_)= Just $ fn x y choose fn (x,Nothing) (_,Just y) = Just $ fn x y choose fn (_,Nothing) (_,Nothing) = Nothing -- One step: associate Mul to the right -- (a `Mul` b) `Mul` c ==> a `Mul` (b `Mul` c) -- or: (Mul (Mul a b) c) ==> (Mul a (Mul b c)) mul_right :: FN -> Maybe FN mul_right (Mul (Mul a b) c) = Just (Mul a (Mul b c)) mul_right x = congruence mul_right x -- do the opposite mul_left :: FN -> Maybe FN mul_left (Mul a (Mul b c)) = Just (Mul (Mul a b) c) mul_left x = congruence mul_left x test3 = closure mul_right test1 -- Let us distribute multiplication over addition -- a * (b+c) => a*b + a*
Re: [Haskell-cafe] What puts False before True?
This question: > What is the basic philosophy for Bool being a member of Ord? ... > What justifies False < True? resulted in some answers: in most interpretations this equals: False == 0 True == 1 ... Although this is not a must, I would like to remind you also that in formal math there *IS* a strong relation between the ordering and binary 'algebraic' relation. The Boolean algebra / Boolean lattice in a nice structure, and Ord could in principle be derived from the login connectives. But this is a subsumption, which in Haskell cannot be done automatically, so we do it explicitly... See here: http://en.wikipedia.org/wiki/Boolean_algebra Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
Jon Harrop wrote: > However, I can't think how you might return physically identical > results when possible in Haskell. Perhaps you might be interested then in the following function that non-destructively updates a subterm in a large term, preserving sharing. The function can be used to do a substitution in a term. The function is described in http://okmij.org/ftp/Haskell/Zipper2.lhs beginning with the phrase ``We start therefore with an improved term enumerator that maximally preserves sharing. If no updates were done, the result of the traversal is the original term itself -- rather than its copy. Furthermore, this property holds for each subterm. The new traversal function lets us operate on subterms in pre-order, in-order, or post-order. More importantly, it lets us effectively span a `canonical' spanning tree on a term, so each node can be unambiguously identified. We do not require equality on (sub)terms.'' That was the second article in a series; please see http://okmij.org/ftp/Computation/Continuations.html#zipper for the full series. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What puts False before True?
> What is the basic philosophy for Bool being a member of Ord? you can do sth like Data.Set.fromList [minBound .. maxBound] :: Data.Set.Set Bool Sorry, not quite sure what you mean. > What justifies False < True? in most interpretations this equals: False == 0 True == 1 Indeed, it's the same in C but what justifies the decision in Haskell? and == (*) or == max not == (1 -) a `xor` b == (a + b) `mod` 2 and not this: False == 1 True == 0 and == max or == (*) not == (1 -) a `xor` b == (a + b) `mod` 2 Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Implementing Mathematica
On Thu, 2007-05-31 at 08:46 +0100, Simon Peyton-Jones wrote: > | $ ghc htrace.hs -o htrace > | $ ghc -O2 htrace.hs -o htrace > | compilation IS NOT required > Yes, I think it's a bug. GHC should really compare the flags used > last time with the flags used this time [...] As an (easier) alternative, I would find it in line with my expectations if GHC always recompiled in the absence of --make, and recompiled based on time stamps in the presence of --make. -k ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] enumFrom* strangeness on GHC?
On 5/31/07, Felipe Almeida Lessa <[EMAIL PROTECTED]> wrote: BTW, how do you usually proceed when finding out why your code said "Segmentation fault."? (should this question move to a new thread?) $ gdb my_crashing_program [wait till crush] [on the gdb command line:] $ bt [prints backtrace] If you're lucky, this helps a little. ;) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Mathematica
http://hackage.haskell.org/trac/ghc/ticket/106 It got changed to Won't Fix. Consider this a yell! On 31/05/07, Simon Peyton-Jones <[EMAIL PROTECTED]> wrote: | Incidentally, when I try to recompile with optimizations turned on, GHC | refuses to work: | | $ ghc htrace.hs -o htrace | $ ghc -O2 htrace.hs -o htrace | compilation IS NOT required Yes, I think it's a bug. GHC should really compare the flags used last time with the flags used this time, and recompile if they have changed. If enough people yell about it, we'll probably fix it! Meanwhile opening a Trac bug report (or perhpas feature request) would be a good start. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] updating packages
Have you tried cabal-install? It may or may not work. (It should have come with Cabal.) On 5/31/07, jeff p <[EMAIL PROTECTED]> wrote: Hello, I just moved to ghc-6.6.1and was wondering if there is an automatic way to update the various packages I had installed previously. thanks, jeff ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- "Remember! Everytime you say 'Web 2.0' God kills a startup!" - userfriendly.org, Jul 31, 2006 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] equations and patterns
On 5/31/07, Stefan Holdermans <[EMAIL PROTECTED]> wrote: Dan, > If you want to enforce associativity just create your own Eq > instance and > make it a pattern there. Could you elaborate on that? It's still early here and I've had only one cup of of coffee yet. Cheers, Stefan QuickCheck allows you to approximately verify properties by testing them on randomly generated input. The stated properties thus cannot formally be proved, but they act as a pretty good formal specification. (Full automatic theorem proving for a language as expressive as Haskell is impossible or infeasible. So we have to approximate.) prop_assocJoin x y z = join x (join y z) == join (join x y) z -- or, more generally associative :: (Eq a) => (a -> a -> a) -> a -> a -> a -> Bool associative f x y z = f x (f y z) == f (f x y) z prop_assocJoin = associative join -- to check this for a given implementation of "join", you need to: import Test.QuickCheck Main> quickCheck prop_assocJoin This also requires that QC can generate arbitrary values of type "e". See the QuickCheck documentation for more infos on that: http://www.cs.chalmers.se/~rjmh/QuickCheck/manual.html / Thomas -- "Remember! Everytime you say 'Web 2.0' God kills a startup!" - userfriendly.org, Jul 31, 2006 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Implementing Mathematica
| Incidentally, when I try to recompile with optimizations turned on, GHC | refuses to work: | | $ ghc htrace.hs -o htrace | $ ghc -O2 htrace.hs -o htrace | compilation IS NOT required Yes, I think it's a bug. GHC should really compare the flags used last time with the flags used this time, and recompile if they have changed. If enough people yell about it, we'll probably fix it! Meanwhile opening a Trac bug report (or perhpas feature request) would be a good start. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] equations and patterns
Dan, If you want to enforce associativity just create your own Eq instance and make it a pattern there. Could you elaborate on that? It's still early here and I've had only one cup of of coffee yet. Cheers, Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] equations and patterns
If you want to enforce associativity just create your own Eq instance and make it a pattern there. Initially when I started doing Haskell it seemed that you could just type an equation of constructors and have it enforced as a rule. This actually isn't the case (someone correct me if I'm wrong) but it is being researched ATM. Dan On 5/31/07, Stefan Holdermans <[EMAIL PROTECTED]> wrote: Mingli, > > class Lattice e where > > join :: e -> e -> e > > meet :: e -> e -> e > > > > -- associative law > > join x (join y z) = join (join x y) z > > join (join x y) z = join x (join y z) If you are not to sell your soul to advanced and perhaps obscure type hacking, you cannot express laws like this *in* Haskell. More concretely, one usually does not provide such laws as default implementations of a class' methods. Instead, they are stated in, for instance, comments and the documentation that goes with your library. These then form an informal obligation for programmers that provide instances of your class to let these instances obey the laws. If you provide an instance of the class you could use testing framework, e.g., QuickCheck [1], to assert that the required properties hold. Cheers, Stefan [1] www.cs.chalmers.se/~rjmh/QuickCheck/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Language extensions
On Wed, May 30, 2007 at 05:12:48PM +0200, Henk-Jan van Tuyl wrote: > On Wed, 30 May 2007 09:38:10 +0200, Tomasz Zielonka > <[EMAIL PROTECTED]> wrote: > >On Tue, May 29, 2007 at 09:43:03PM +0100, Andrew Coppin wrote: > >>Henning Thielemann wrote: > >>>On Sun, 27 May 2007, Andrew Coppin wrote: > But every now and then I discover an expression which is > apparently not expressible without them - which is odd, > considering they're only "sugar"... > >>> > >>>Example? > >> > >>Until I learned the trick of using lists as monads, I was utterly > >>perplexed as to how to get a Cartesian product > > > >This is far from not expressible: > >cart xs ys = concatMap (\x -> map ((,) x) ys) xs > > A bit simpler is: > cart xs ys = [(x, y) | x <- xs, y <- ys] > > or: > cart xs ys = > do > x <- xs > y <- ys > return (x, y) I was responding to Andrew saying that computing cartesian product is apparently not expressible without list comprehensions. Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe