Re: [Haskell-cafe] Monadic tunnelling: the art of threading one monad through another
Derek Elkins wrote: What you're actually showing is that these effects can be -embedded- in IO (i.e. that IO already supports them). I noticed you didn't try to make an instance for the Cont monad. Actually, if we added continuations to IO, we'd be set. We wouldn't even need your typeclass. Yes, precisely. Your use of the term 'embedded' parallels the fact I called the method 'embed'. It's a useful technique because it enables you to give more specific types to your functions: to use StateT IO instead of just using IO and instead of using ad-hoc IORefs yourself you can use the StateT methods and have the IORefs behind the scenes when you need to thread through another monad. Similarly you can give pure types to callbacks (either plain State s, or the parametric forall m. StateT s m) which makes it easier to specify and test them. It even has applications in an untrusted code environment, where it's dangerous to accept callbacks of IO type. Of course, you can't do Cont or List (unless I'm missing something) because they are both capable of duplicating the current continuation, and it's not possible to duplicate the entire IO state (a.k.a. the RealWorld#). Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[4]: [Haskell-cafe] In-place modification
Hello ok, Thursday, July 12, 2007, 3:29:25 AM, you wrote: own simple IR engine. It's really pretty simple. My model answer in C is two separate programs, an index builder and a query engine, and is 804 SLOC in 1075 total lines. Each year, despite our advice, some student does it in Java. using student's work, it's easy to proof that Basic is faster than assembler (and haskell is as fast and memory-efficient as C, citing haskell-cafe) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Tue, 10 Jul 2007, Jonathan Cast wrote: On Tuesday 10 July 2007, Andrew Coppin wrote: Stefan O'Rear wrote: Consider the ST monad, which lets you use update-in-place, but is escapable (unlike IO). ST actions have the form: ST s α Meaning that they return a value of type α, and execute in thread s. All reference types are tagged with the thread, so that actions can only affect references in their own thread. What about putting the runST monad explanation to the Wiki? It seems to be an FGA (frequently given answer). :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Tue, 10 Jul 2007, Albert Y. C. Lai wrote: Andrew Coppin wrote: Wait... I thought Unicode was still an experimental prototype? Since when does it work in the real world?? That myth is as old as Haskell is an experimental prototype. Old as in that's an old one. Windows has been well supporting Unicode since 2000. That is pretty much of the real world. The only reason you see α as the Greek letter alpha and not scrambled code is that I send it as Unicode and your Windows and Thunderbird also support Unicode and therefore they display it to you properly. I don't see a greek letter alpha here, but scrambled code in 'pine' here. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Thu, Jul 12, 2007 at 09:12:14AM +0200, Henning Thielemann wrote: On Tue, 10 Jul 2007, Jonathan Cast wrote: On Tuesday 10 July 2007, Andrew Coppin wrote: Stefan O'Rear wrote: Consider the ST monad, which lets you use update-in-place, but is escapable (unlike IO). ST actions have the form: ST s α Meaning that they return a value of type α, and execute in thread s. All reference types are tagged with the thread, so that actions can only affect references in their own thread. What about putting the runST monad explanation to the Wiki? It seems to be an FGA (frequently given answer). :-) I think it already is, in the Research Papers section. :-) Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[6]: [Haskell-cafe] Toy compression algorithms [was: A very edgy language]
Hello ajb, Thursday, July 12, 2007, 9:25:35 AM, you wrote: what you mean by flat and static applied to PPM? static PPM models exist - they carry probabilities as separate table very like static Huffman encoding. is flat the same as order-0? Static means that the frequency distribution is fixed. Flat means that the frequency histogram is flat. (Every code word is predicted to occur with the same frequency, resulting in a binary code.) well, ppm differs from simple order-0 coder in that it uses previous symbols to calculate probability. lzw differs from order-0 coder with flat static probabilities in that it encodes a whole word each time. there is nothing common between ppm and lzw except for this basic order-0 model, so i don't see any reasons to call lzw a sort of ppm. it will be more fair to say that lzw is order-0 coder with static flat probabilities, you agree? can you give a link? i never heard about such algorithm http://en.wikipedia.org/wiki/Canonical_Huffman_code you said about algorithm that efficiently encodes english words using huffman codes. is such algorithm really exists? -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Thursday 12 July 2007, Henning Thielemann wrote: On Tue, 10 Jul 2007, Albert Y. C. Lai wrote: Andrew Coppin wrote: Wait... I thought Unicode was still an experimental prototype? Since when does it work in the real world?? That myth is as old as Haskell is an experimental prototype. Old as in that's an old one. Windows has been well supporting Unicode since 2000. That is pretty much of the real world. The only reason you see α as the Greek letter alpha and not scrambled code is that I send it as Unicode and your Windows and Thunderbird also support Unicode and therefore they display it to you properly. I don't see a greek letter alpha here, but scrambled code in 'pine' here. There's your problem right there. Get either a terminal or a mail program that knows UTF-8. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Unicode support (Was: Type system madness)
On Thu, 12 Jul 2007, Jonathan Cast wrote: On Thursday 12 July 2007, Henning Thielemann wrote: On Tue, 10 Jul 2007, Albert Y. C. Lai wrote: Andrew Coppin wrote: Wait... I thought Unicode was still an experimental prototype? Since when does it work in the real world?? That myth is as old as Haskell is an experimental prototype. Old as in that's an old one. Windows has been well supporting Unicode since 2000. That is pretty much of the real world. The only reason you see α as the Greek letter alpha and not scrambled code is that I send it as Unicode and your Windows and Thunderbird also support Unicode and therefore they display it to you properly. I don't see a greek letter alpha here, but scrambled code in 'pine' here. There's your problem right there. Get either a terminal or a mail program that knows UTF-8. I do now understand how well supported is meant. If a program doesn't support UTF-8/Unicode, that's not the problem of Unicode, but the problem of the program and its users. If we restrict the range of considered applications to those which support UTF-8 then UTF-8 is globally supported. This leads me to an idea: We declare exclusively Haskell programs being real programs then we can safely claim that Haskell is the only language, where real programs can be written in. :-] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] haskell - db, on Solaris
Thanks, all. I forgot, that Takusen uses OCI, not ODBC, sorry. I'm getting it now. |'ve looked more closely at HSQL, also. Indeed, it uses native interfaces, as Alistair pointed out. And since it supports both Oracle and MySql, I think it will be my first try. Typeful queries are not important to me. But having one library instead of 2 distinct ones is appealing. And avoiding depending on a separate unixODBC is also good. 2007/7/12, Bryan O'Sullivan [EMAIL PROTECTED]: Daniil Elovkov wrote: Yes, thanks. But the emphasis was on Solaris. I don't quite understand what is the common way to access databases on Solaris. Is it odbc? ODBC is a standard, fairly portable database interface. Since HDBC has ODBC bindings, it can in principle talk to any database that provides an ODBC interface. b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Newbie question about tuples
Hi, I have a couple of questions about tuples. Q1) Is it possible to treat a tuple of N elements in a generic way? So instead of writing functions like lift1 e1, lift2 (e1,e2), lift3 (e1,e2,e3) just one function liftN that works on tuples of any length? Q2) (Maybe related to Q1) Can I convert a tuple of length N to a heterogeneous list (using forall aka existentially quantified types) and vice versa? Q3) Suppose I want to declare an instance of Num on all tuple types having (Num instances) as elements; is this possible? I tried instance Num a = Num (a,a) where . but this fails I also tried instance Num a = Num ((,) a a) where . but that also fails. I can of course create a new type like newtype Num a = Vector2 a = Vector2 (a,a) and then create an instance for Vector2, but I was wondering if it would be possible without introducing a new type. Thanks, Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question about tuples
Hi Peter, 2007/7/12, peterv [EMAIL PROTECTED]: Q1) Is it possible to treat a tuple of N elements in a generic way? So instead of writing functions like lift1 e1, lift2 (e1,e2), lift3 (e1,e2,e3) just one function liftN that works on tuples of any length? Q2) (Maybe related to Q1) Can I convert a tuple of length N to a heterogeneous list (using forall aka existentially quantified types) and vice versa? Not in the standard libraries. I've been using a home-grown module for this sort of thing: http://antti-juhani.kaijanaho.fi/darcs/fenserve/fendata/TupleUtils.hs Q3) Suppose I want to declare an instance of Num on all tuple types having (Num instances) as elements; is this possible? I tried instance Num a = Num (a,a) where . but this fails This is illegal in Haskell 98, but should work in GHC if you use -fglasgow-exts. - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Wed, 2007-07-11 at 20:10 +0100, Andrew Coppin wrote: When I tell the editor to save UTF-8, it inserts some weird BOM character at the start of the file - and thus, any attempt at programatically processing that file instantly fails. :-( While BOMs (Byte Order Mark) are pretty irrelevant to byte-oriented encodings like UTF-8, I think programs that fail on their presence can be considered buggy. -k ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unicode support (Was: Type system madness)
On Thursday 12 July 2007, Henning Thielemann wrote: On Thu, 12 Jul 2007, Jonathan Cast wrote: On Thursday 12 July 2007, Henning Thielemann wrote: On Tue, 10 Jul 2007, Albert Y. C. Lai wrote: Andrew Coppin wrote: Wait... I thought Unicode was still an experimental prototype? Since when does it work in the real world?? That myth is as old as Haskell is an experimental prototype. Old as in that's an old one. Windows has been well supporting Unicode since 2000. That is pretty much of the real world. The only reason you see α as the Greek letter alpha and not scrambled code is that I send it as Unicode and your Windows and Thunderbird also support Unicode and therefore they display it to you properly. I don't see a greek letter alpha here, but scrambled code in 'pine' here. There's your problem right there. Get either a terminal or a mail program that knows UTF-8. I do now understand how well supported is meant. If a program doesn't support UTF-8/Unicode, that's not the problem of Unicode, but the problem of the program and its users. If we restrict the range of considered applications to those which support UTF-8 then UTF-8 is globally supported. This leads me to an idea: We declare exclusively Haskell programs being real programs then we can safely claim that Haskell is the only language, where real programs can be written in. :-] The last release of Pine came out 28 September 2005; the last release to add new features came out 10 May 2004; the last time the major version number was bumped was 8 July 1998. I can appreciate clinging to old, comfortable software; it took quite a bit to get me to abandon nmh. But I did it, because that software simply doesn't work on the modern internet. A certain level of seriousness is required when making software choices, after all. And some software is just too old to be taken seriously. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] money type ?
Good day all, my budding ledger program could not balance transactions exactly because of rounding error with Double. I *think* I got it working better with Rational (it was late). Another suggestion from #haskell was to multiply all money by 100. I'm tracking multiple currencies/commodities with varying precision so this gets a bit more complicated. Is there a type or library out there that's good for representing money and other quantities while avoiding rounding errors ? Best - Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[6]: [Haskell-cafe] Toy compression algorithms [was: A very edgy language]
G'day. Quoting Bulat Ziganshin [EMAIL PROTECTED]: well, ppm differs from simple order-0 coder in that it uses previous symbols to calculate probability. lzw differs from order-0 coder with flat static probabilities in that it encodes a whole word each time. LZW doesn't have the concept of a word at all. Both PPM and LZW build up contexts as they go by starting with one context for each symbol in the input alphabet, and by extending contexts with single symbols as they are found. (Conceptually; the algorithms are slightly different, but they do the same job.) The difference has to do, almost completely, with coding. LZW uses a degenerate model to decide what the next input symbol is. It assumes that all seen contexts are equally likely, and hence uses a binary code to encode them. (A binary code represents the numbers 0 to k-1 using k codewords each of which is (log k) bits in length.) PPM uses a different coding scheme, using the observed frequency of each context to drive an arithmetic coder. there is nothing common between ppm and lzw except for this basic order-0 model, so i don't see any reasons to call lzw a sort of ppm. There are a lot of differences between PPM and LZW, but they're based around the same principle: Build contexts based on what you've seen so far, and use that to predict what the next symbol should be. it will be more fair to say that lzw is order-0 coder with static flat probabilities, you agree? That's the _coding_ phase, sure. All known text compression algorithms basically work by building a model of the text, to try to predict the next symbol, and then using that to drive a coder which represents what was actually found using some bit representation. PPM and LZW use very different coders, but their models are quite similar. you said about algorithm that efficiently encodes english words using huffman codes. is such algorithm really exists? Ask Google about word-based huffman. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] IDE for Haskell (Was: function unique)
On Wed, 11 Jul 2007, Steve Schafer wrote: On Wed, 11 Jul 2007 22:39:27 +0200, you wrote: In C#, when you call a function you type ( and instantly you get a popup box telling you what the name of the first argument is, then when you've written the first argument and hit , you get the name (and type) of the second argument. That's not a feature of C# itself, but rather a feature of the development environment you're using. You can write C# code in NotePad, and I will guarantee you that you won't see any such popups. ;) There do exist various development environments for Haskell, but I don't think any of them are particularly popular. Since you can write Plugins for Eclipse in Haskell, things become interesting: http://leiffrenzel.de/eclipse/cohatoe/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange results when trying to create large Bool arrays.
On Wed, 2007-07-11 at 10:55 -0700, Bryan O'Sullivan wrote: In a similar vein, I was initially perplexed when I found that an expression like this produces garbage instead of an error: read 111 :: Int I have not seen a lot of interest expressed in fixing this sort of misbehaviour, which jars a little with the usual emphasis on stringency and testing. I'd really like to have errors on overflow, at least as an option, even if it is costly in terms of performance. Is there a Trac ticket or something for this? -k ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] money type ?
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Simon Michael Is there a type or library out there that's good for representing money and other quantities while avoiding rounding errors ? I think Data.Fixed would be a good choice: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Fixed.ht ml I don't know /exactly/ how you'd go about adding a Money data type; I guess you'd have something like: data E2 = E2 instance HasResolution E2 where resolution _ = 100 type Money = Fixed E2 Alistair * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] money type ?
From: Brandon S. Allbery KF8NH [mailto:[EMAIL PROTECTED] I was playing with that when your message came in: mress:5003 Z$ cat foo.hs import Data.Fixed data E2 = E2 instance HasResolution E2 where resolution _ = 100 type Money = Fixed E2 ... *Main :m +Data.List *Main Data.List let l = [1.25 :: Money,2.00,4.46,12.80,1.15,6.00] in sum l / genericLength l 4.61 That what you want? Yes... I'm now wondering how one would read Money values. There's a Show instance for Fixed, but no Read. Could use: readMoney :: String - Money readMoney s = let d :: Double; d = read s in realToFrac d ... but is there a better way? Note that readMoney is a bit dumb: *Main readMoney 3.14 3.14 Alistair * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: money type ?
simon: Great - indeed, sum [1.85, 5.95, -7.80] 8.881784197001252e-16 sum [1.85::Money, 5.95, -7.80] 0.00 I'm not yet sure these will do the best thing in all arithmetic, but it seems to be the right thing for now. Yes, I will need to read these also. Perhaps first reading the integer and decimal digits as separate integers will help. I'm still exploring the number types. Roman Leschinskiy tells me that there are C (or C++?) libraries for locale-specific money handling, where given precisions are mandated in particular countries, below which you must round. Perhaps we should have a binding to this. Anyway, sorting out how money is supposed to be represented in Haskell, and documenting it, seems a very useful thing. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
On Thursday 12 July 2007 04:40, Andrew Coppin wrote: I once sat down and tried to read about Category Theory. I got almost nowhere though; I cannot for the life of my figure out how the definition of category is actually different from the definition of set. Or how a functor is any different than a function. Or... actually, none of it made sense. Iiuc, Set is just one type of category; and the morphisms of the category Set are indeed functions. But morphisms in other categories need not be functions; in the category Rel, for example, the morphisms are not functions but binary relations. A functor is something that maps functions in one category to functions in another category. In other words, functors point from one or more functions in one category to the equivalent functions in another category. Perhaps they could be regarded as 'meta-functions'. Hope that helps, Alexis. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Defaulting to Rational [was: Number overflow]
Donald Bruce Stewart wrote: should Rational, or something similar be used instead, given that Doubles and Float are broken for a lot of basic things (like Eq and Ord), much as we default to Integer already. The issues raised regarding Rational was that you can unexpectedly build up large precision, and performance in general, of course. Well, non-broken Eq and Ord very much depend on large precision. In a sense, the instances of Eq and Ord for floating point numbers are wrong. What about rolling new classes for approximate equality and ordering? class ApproxEq a where (≈) :: a - a - Bool -- almost equal to class ApproxOrd a where :: a - a - Bool -- really less than :: a - a - Bool -- really greater than together with phantom-epsilon data Eps10 newtype Floating e = F Double instance ApproxEq (Floating Eps10) where x ≈ y = abs (x-y) 1e-10 Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Functional dependencies *not* part of the next Haskell standard?
On Thu, 12 Jul 2007, peterv wrote: I tried to do something in CAL that I could not solve without functional dependencies. In their support forum, it got mentioned that func.deps propably won't make into the next Haskell standard... Any comments on that? Now, the thing I tried to solve was: data Vector2 a = Num a = V2 a a class Vector a n | a - n where dot :: a - a - n instance Num a = Vector (Vector2 a) a where dot (V2 x1 y1) (V2 x2 y2) = x1 * x2 + y1 * y2 test1 = dot (V2 1.0 2.0) (V2 3.0 4.0) class Vector v where dot :: Num a = v a - v a - a instance Vector Vector2 where dot (V2 x1 y1) (V2 x2 y2) = x1 * x2 + y1 * y2 This will work satisfyingly if you don't plan a larger type class hierarchy. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Defaulting to Rational [was: Number overflow]
On Thu, 12 Jul 2007, Jon Fairbairn wrote:
Now, a proper exact real type is doubtless very inefficient,
but wouldn't it be possible to define something that had a
fairly efficient head, and a lazy tail? So you'd have, say
data Real = R {big::(Ratio !Int !Int), small:: More_Precision}
for some exact real representation More_Precision such that
R a b represents the number (a+b) (It might be better to use
something shorter than Int for the Ratio so that it takes
less space). For any rational arithmetic that fits in the
big part, the small part would be zero (and therefore
small!).
This would give exact answers for the sort of arithmetic you
list above, but could still be an instance of Floating etc.
Interesting approach. Somehow similar to making Integer a sum of Int and
BigInt. Indeed, I have used transcendent arithmetic on Doubles to speedup
computations for real numbers. However real numbers cannot be checked for
equality. This can be also considered an advantage, because using (==) for
floating point numbers is most oftenly a bug. I think that this hybrid
type is nice and could be used by default. But it should not replace
native floating point types, since they have guaranteed speed in favor of
not guaranteed precision. And we need a correct implementation.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[8]: [Haskell-cafe] Toy compression algorithms [was: A very edgy language]
Hello ajb, Thursday, July 12, 2007, 12:16:22 PM, you wrote: well, ppm differs from simple order-0 coder in that it uses previous symbols to calculate probability. lzw differs from order-0 coder with flat static probabilities in that it encodes a whole word each time. LZW doesn't have the concept of a word at all. in this case why you proposes to encode lzw words with a huffman codes? :) Both PPM and LZW build up contexts as they go by starting with one context for each symbol in the input alphabet, and by extending contexts with single symbols as they are found. (Conceptually; the algorithms are slightly different, but they do the same job.) The difference has to do, almost completely, with coding. LZW uses a degenerate model to decide what the next input symbol is. It assumes that all seen contexts are equally likely, and hence uses a binary code to encode them. (A binary code represents the numbers 0 to k-1 using k codewords each of which is (log k) bits in length.) oops. ppm build tree of contexts and use context to encode one char. lzw builds dictionary of words and encode word in empty context. encoding in empty context is equal to order-0 coder while prediction by partial matching by definition is order-N, N0 encoding. so lzw can't be considered as degenerate case of ppm although programming techniques (building tree of words/contexts) are pretty close it will be more fair to say that lzw is order-0 coder with static flat probabilities, you agree? That's the _coding_ phase, sure. you are right. so lzw is just dictionary-based transformation which replaces some words with special codes while ppm replaces chars with their probabilities. i hope you will agree that ppm with flat codes will be totally useless you said about algorithm that efficiently encodes english words using huffman codes. is such algorithm really exists? Ask Google about word-based huffman. about which particular algorithm you said? Moffat? -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: money type ?
Donald Bruce Stewart wrote: Roman Leschinskiy tells me that there are C (or C++?) libraries for locale-specific money handling, where given precisions are mandated in particular countries, below which you must round. Perhaps we should have a binding to this. IIRC, the rules in the EU were that operations on money have to be done with 3 decimal digits and then rounded to 2. That is, 0.01 / 2 = 0.01 (0.005 rounded to 2 decimal digits). I may be mistaken, though. What I'm fairly sure of is that required precision and rounding policies differ from country to country. Getting it right is *much* harder than it looks. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: money type ?
Donald Bruce Stewart wrote: simon: Great - indeed, sum [1.85, 5.95, -7.80] 8.881784197001252e-16 sum [1.85::Money, 5.95, -7.80] 0.00 I'm not yet sure these will do the best thing in all arithmetic, but it seems to be the right thing for now. Yes, I will need to read these also. Perhaps first reading the integer and decimal digits as separate integers will help. I'm still exploring the number types. Roman Leschinskiy tells me that there are C (or C++?) libraries for locale-specific money handling, where given precisions are mandated in particular countries, below which you must round. Perhaps we should have a binding to this. Anyway, sorting out how money is supposed to be represented in Haskell, and documenting it, seems a very useful thing. -- Don It is funny that this thread is going on alongside the Defaulting to Rational thread. There are separate issues with Money: (1) Never using Double and Float to avoid representation errors. (2) Provide the correct rounding at the correct moment. For (1) you can use Data.Ratio or a pair Data.Seq of digits in base-10 before and after the decimal point. For (2) you (2.a) you do not always want to round at each step of a calculation and (2.b) do not always want the same precision. Example of (2.a) The 'sum' works, but what about an average price of 100 items? If you total then divide it might work, but if you divide like : 0.32 / 100.00 is 0.00 then you have lost track of the money. Example of (2.b) I have several catalogs that I order from that list prices (in £ or $) to higher than normal precision, e.g. $ 0.7525, since they are often bought in large quantities, such as electrical components. And exchange rates are also often quoted in higher than normal precision. The Right Thing for storing the value is probably a Data.Ratio or a Data.Sequence of digits in base-10. One might also store Currency with a phantom type to prevent ($10 + £10) from compiling: newtype Money cc = Money (Data.Ratio) -- Exact, and no bias toward base 10 class Currency a where unit :: a -- Smallest physical amount, e.g. $ 0.01 nearest :: a - a -- Round to nearest multiple of unit symbol :: String description :: String Then the localization (l10n) is specified by a dummy type: data USD data GBP I am no l10n expert, but I could also see: instance Show (Money USD) where ... instance Show (Money GBP) where ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[8]: [Haskell-cafe] Toy compression algorithms [was: A very edgy language]
Hello ajb, Thursday, July 12, 2007, 12:16:22 PM, you wrote: well, ppm differs from simple order-0 coder in that it uses previous symbols to calculate probability. lzw differs from order-0 coder with flat static probabilities in that it encodes a whole word each time. oh, i just recalled that flat distribution conventionally called order -1 model. so starting from non-compressible order -1 model, lzw and ppm goes into opposite direction: * ppm uses several previous chars to predict one next character * lz77/78 predicts (in the order -1 model) several next chars at once if you interested, there are many algorithms combining both approaches: lzrw5/rolz, lzp, lzcb, lzma -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[8]: [Haskell-cafe] Toy compression algorithms [was: A very edgy language]
On 7/12/07, Bulat Ziganshin [EMAIL PROTECTED] wrote: about which particular algorithm you said? Moffat? Well, both Andrew and I has Alistair Moffat as a lecturer in our time. So, surely. :-) If my memory serves me, you'll find Alistair has published work on quite a number of algorithms, some of which are symbol based (0, 1 or higher order), and others which are word based. cheers, T. -- Dr Thomas Conway [EMAIL PROTECTED] Silence is the perfectest herald of joy: I were but little happy, if I could say how much. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Defaulting to Rational [was: Number overflow]
Henning Thielemann [EMAIL PROTECTED] writes:
On Thu, 12 Jul 2007, Jon Fairbairn wrote:
Now, a proper exact real type is doubtless very inefficient,
but wouldn't it be possible to define something that had a
fairly efficient head, and a lazy tail? So you'd have, say
data Real = R {big::(Ratio !Int !Int), small:: More_Precision}
Interesting approach.
But flawed as I put it: the big part can't express big
numbers! The big part needs to be either Rational (and the
precision of that part limited during arithmetic) or
BigFloat where
Data BigFloat = BF {mantissa:: Int, exponent:: Integer}
(ie limited precision, but unbounded magnitude). If we were
to use BigFloat the base would need to be a power of ten to
get the desired results for things like Don's example)
Somehow similar to making Integer a sum of Int and
BigInt. Indeed, I have used transcendent arithmetic on
Doubles to speedup computations for real numbers. However
real numbers cannot be checked for equality. This can be
also considered an advantage, because using (==) for
floating point numbers is most oftenly a bug.
Agreed. That should be part of the change to the numeric
hierarchy.
I think that this hybrid type is nice and could be used by
default. But it should not replace native floating point
types, since they have guaranteed speed in favor of not
guaranteed precision. And we need a correct
implementation.
Absolutely!
--
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] Strange results when trying to create large Bool arrays.
Ketil Malde wrote: I'd really like to have errors on overflow, at least as an option, even if it is costly in terms of performance. Is there a Trac ticket or something for this? Not that I know of. I filed a Trac ticket against ByteString's readInt function before I noticed that read has the same problem, and it was closed because read does the same thing. I've been reluctant to pop my head over the parapet since. CPUs generally don't trap on integer overflow, so generating the additional tests and jumps necessary to handle this would be a bit involved, and would certainly cost a few percent in performance. There's also overflow in truncation and sign conversions to worry about, e.g. Word32 - Word16, Word32 - Int (on 32-bit systems), etc. On the other hand, integer overflows have long been a popular attack vector for getting programs to misbehave in the exploit community. If you Google for ia32 integer overflow or i386 integer overflow, the first several *pages* of results in each case consist entirely of security advisories. Haskell's FFI makes it as vulnerable as the libraries it interfaces to. Here's a cute-looking paper entitled Efficient and accurate detection of integer-based attacks. http://www.cs.cmu.edu/~dbrumley/pubs/integer-ndss-07.pdf b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Functional dependencies *not* part of the next Haskell standard?
instance Vector Vector2 where dot (V2 x1 y1) (V2 x2 y2) = x1 * x2 + y1 * y2 Amazing, so simple it is, Yoda would say ;) I did not realize one could perform partial application on types when declaring instances (I mean not specifying the type of Vector2 in instance Vector Vector2). Now regarding these funcdeps, are they ill as the rumor goes? Thanks, Peter -Original Message- From: Henning Thielemann [mailto:[EMAIL PROTECTED] Sent: Thursday, July 12, 2007 11:44 AM To: peterv Cc: Haskell-Cafe@haskell.org Subject: Re: [Haskell-cafe] Functional dependencies *not* part of the next Haskell standard? On Thu, 12 Jul 2007, peterv wrote: I tried to do something in CAL that I could not solve without functional dependencies. In their support forum, it got mentioned that func.deps propably won't make into the next Haskell standard... Any comments on that? Now, the thing I tried to solve was: data Vector2 a = Num a = V2 a a class Vector a n | a - n where dot :: a - a - n instance Num a = Vector (Vector2 a) a where dot (V2 x1 y1) (V2 x2 y2) = x1 * x2 + y1 * y2 test1 = dot (V2 1.0 2.0) (V2 3.0 4.0) class Vector v where dot :: Num a = v a - v a - a instance Vector Vector2 where dot (V2 x1 y1) (V2 x2 y2) = x1 * x2 + y1 * y2 This will work satisfyingly if you don't plan a larger type class hierarchy. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Functional dependencies *not* part of the next Haskell standard?
peterv wrote: instance Vector Vector2 where dot (V2 x1 y1) (V2 x2 y2) = x1 * x2 + y1 * y2 Amazing, so simple it is, Yoda would say ;) I did not realize one could perform partial application on types when declaring instances (I mean not specifying the type of Vector2 in instance Vector Vector2). Now regarding these funcdeps, are they ill as the rumor goes? I don't think there is any danger of them being removed and not replaced. The functionality is useful. Associated Types is widely viewed as a successor/replacement, but no complete implementation exists yet: http://haskell.org/haskellwiki/GHC/Indexed_types I'm sure FDs are here for a while yet. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Functional dependencies *not* part of the next Haskell standard?
2007/7/12, peterv [EMAIL PROTECTED]: Amazing, so simple it is, Yoda would say ;) I did not realize one could perform partial application on types when declaring instances (I mean not specifying the type of Vector2 in instance Vector Vector2). You ought to meditate on the type class 'Monad,' then, which was the motivating example for allowing these kinds of classes in standard Haskell ;-) All the best, - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Haskell monads for newbies (was Functional dependencies *not* part of the next Haskell standard?)
Thanks for the advice. I did not really deeply investigate the monad type classes yet... It looks like its gonna take a long time for me to learn Haskell. I'm not sure if my long history of imperative and object-oriented programming has something to do with it. Reading Haskell books like SOE is one thing, but writing software in Haskell is really difficult for me. Not only do I miss the spoiled OO programmer IDEs with all their candy and code completion and assistants, but I also get the feeling that although similar programs in Haskell or typically N times shorter than their imp/OO counterparts, it would take *me* at least N^2 longer to write them ;) (now I must admit I had the same feeling when switching from 680x0 assembler to C++, but let's say N*2 longer instread of N^2...) Is this true for Haskell in general? I mean how long do experienced Haskell developers spent writing code to get it right (excluding minor bugs and performance issues)? Or do they write down Haskell fluently? Regarding those monads, I read a lot of stuff about these beast, trying to get a high-level understanding about them (and apparently I'm not the only newby who struggled with that ;), but after having read You Could Have Invented Monads! and then reading http://research.microsoft.com/~simonpj/papers/marktoberdorf, it all became much clearer. Those pictures really helped... Monads were very confusing because I first looked at Concurrent Clean (it comes with an IDE and games! :), and that language uses a simple uniqueness typing approach where the world or state is explicitly passed as an object, and where the compiler garantees monadic usage of that object (warning: that was a lot of fuzzy talk from a newbie trying to look impressive ;) -Original Message- From: Benja Fallenstein [mailto:[EMAIL PROTECTED] Sent: Thursday, July 12, 2007 3:11 PM To: peterv Cc: Henning Thielemann; Haskell-Cafe@haskell.org Subject: Re: [Haskell-cafe] Functional dependencies *not* part of the next Haskell standard? 2007/7/12, peterv [EMAIL PROTECTED]: Amazing, so simple it is, Yoda would say ;) I did not realize one could perform partial application on types when declaring instances (I mean not specifying the type of Vector2 in instance Vector Vector2). You ought to meditate on the type class 'Monad,' then, which was the motivating example for allowing these kinds of classes in standard Haskell ;-) All the best, - Benja ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: money type ?
Is there a type or library out there that's good for representing money and other quantities while avoiding rounding errors ? Disclaimer: I'm pretty much a beginner at Haskell. Hacked something together a while ago for handling amounts and currencies. It let's you specify the precision of each currency and stores the value as a scaled Integer value. Haven't gotten around to implementing arithmetics yet but by using the Integer values for calculations you sidestep the issues you run into with Reals. module Currency where type Value = Integer data (Currency c) = Amount c = Amount Value c toAmount :: (Real a, Currency c) = a - c - (Amount c) toAmount v c = Amount (round $ realToFrac $ v * (10 ^ (currencyPrecision c))) c class Currency c where currencyFormat :: (Num a) = c - a - String currencyRoundingUnit :: (Fractional a) = (Amount c) - a currencyPrecision :: (Num a) = c - a instance (Currency c) = Show (Amount c) where show a@(Amount _ c) = currencyFormat c $ amountRound a fromAmount :: (Fractional a, Currency c) = (Amount c) - a fromAmount (Amount v c) = (fromInteger v) / (10 ^ (currencyPrecision c)) amountRound :: (Fractional a, Real a, Currency c) = (Amount c) - a amountRound a@(Amount _ c) = realToFrac $ integer + (steps * unit) where total = fromAmount a integer = fromInteger $ truncate $ realToFrac total fraction = total - integer unit = currencyRoundingUnit a steps = fromInteger $ round $ fraction / unit data SEK = SEK instance Currency SEK where currencyFormat _ v = show v ++ kr currencyRoundingUnit _ = 0.5 currencyPrecision _ = 4 data USD = USD instance Currency USD where currencyFormat _ v = $ ++ show v currencyRoundingUnit _ = 0.001 currencyPrecision _ = 4 class ExchangeRate c1 c2 where exchangeRate :: (Fractional a) = c1 - c2 - a amountConvert :: (Currency c1, Currency c2, ExchangeRate c1 c2) = Amount c1 - c2 - Amount c2 amountConvert (Amount v c1) c2 = Amount (round $ (fromInteger v) * (exchangeRate c1 c2)) c2 instance ExchangeRate SEK USD where exchangeRate _ _ = 0.14285 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unresolved overloading
On 12/07/07, Crediné Menezes [EMAIL PROTECTED] wrote: I have written this code in Haskell which gives an unresolved overloading error. g x = [2] ++ [3,5..truncate(sqrt x)] p n= fp n (g n) fp n [ ]= True fp n (x:xs) = if (mod n x) == 0 then False else fp n xs when I submit g 103 I get: [2,3,5,7,9] :: [Integer] when I submit: fp 103 (g 103) I get True :: Bool But when I submit : p 103 I get ERROR - Unresolved overloading *** Type : (RealFrac a, Floating a, Integral a) = Bool *** Expression : p 103 I know why, there is no type that is at the same time: RealFrac, Floating and Integral; but I don´t know how to solve. What kind of type casting or type definition can I use to fix the error? This one's quite subtle, but as usual getting the inferred types from GHCi helps immensely: Prelude :t p p :: (Integral a, Floating a, RealFrac a) = a - Bool Prelude :t fp fp :: (Integral a) = a - [a] - Bool Prelude :t g g :: (Integral t, RealFrac a, Floating a) = a - [t] The function that doesn't work is the one that calls the other two, namely p. It doesn't work, but the separate invocation of fp 103 (g 103) does work. So let's look at that one further: Prelude :t \x y - fp x (g y) \x y - fp x (g y) :: (RealFrac a1, Floating a1, Integral a) = a - a1 - Bool Prelude :t \x - fp x (g x) \x - fp x (g x) :: (RealFrac a, Floating a, Integral a) = a - Bool The first type signature is for the one that worked, and the second is for the definition used in the function p. They're different. So the problem is turning one into the other. In fact, turning (RealFrac a, Floating a) into (Integral a). Which is what truncate should do: Prelude :t \x - fp (truncate x) (g x) \x - fp (truncate x) (g x) :: (RealFrac a, Floating a) = a - Bool I hope that helps! ;-) Cheers, Dougal. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Defaulting to Rational [was: Number overflow]
Bryan O'Sullivan wrote: apfelmus wrote: In a sense, the instances of Eq and Ord for floating point numbers are wrong. What about rolling new classes for approximate equality and ordering? class ApproxEq a where (≈) :: a - a - Bool -- almost equal to The problems with this approach are generally worse than those with Eq, whose shortcomings are at least well defined and widely understood. What I wanted to do is to capture common patterns x - y = epsilon abs (x - y) = epsilon for comparing floating point numbers in nice functions x y = x - y = epsilon x ≈ y = abs (x - y) = epsilon This way, one could simply use and ≈ with floating point numbers and be assured without much thinking that the resulting code is more or less robust. But I guess that there are too many variants of these patterns and that thinking is always required. You need to choose an epsilon of the right magnitude for the numbers you're working with, and the epsilon is likely to be domain-specific. In case the epsilon is problem specific but static, one can use phantom types. Also, since these aren't equivalence relations, ApproxEq has the weird property that a ≈ b and b ≈ c does not imply a ≈ c; ApproxOrd suffers from the same problem. Yes. But that's intended and the very nature of robustly comparing Doubles and Floats :( Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Defaulting to Rational [was: Number overflow]
On Thu, 12 Jul 2007, Jon Fairbairn wrote:
Henning Thielemann [EMAIL PROTECTED] writes:
On Thu, 12 Jul 2007, Jon Fairbairn wrote:
Now, a proper exact real type is doubtless very inefficient,
but wouldn't it be possible to define something that had a
fairly efficient head, and a lazy tail? So you'd have, say
data Real = R {big::(Ratio !Int !Int), small:: More_Precision}
Interesting approach.
But flawed as I put it: the big part can't express big
numbers! The big part needs to be either Rational (and the
precision of that part limited during arithmetic) or
BigFloat where
Data BigFloat = BF {mantissa:: Int, exponent:: Integer}
(ie limited precision, but unbounded magnitude). If we were
to use BigFloat the base would need to be a power of ten to
get the desired results for things like Don's example)
People will be confused, that 'sin pi' won't lead to a result since the
correct result is zero and it will need forever to normalize that number.
They will be confused, that the result of 'sqrt 2 ^ 2' cannot be shown in
usual decimal notation, since the formatting algorithm cannot decide
between starting with 2. and 1.. However 'round (sqrt 2 ^ 2)' will
work as expected.
In short, the Real number type will leed to all difficulties known from
computable reals.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Floating phi, round and even Fibonnaci numbers
You are welcome. Are you talking about http://projecteuler.net/ ? I have been experimenting with various ways of learning Haskell, tackling an interesting set of mathematical problems sounds good. I am. It's turned out to be quite a fun approach and the one that seems to be the most effective, at least for me. On Thursday 12 July 2007 07:50:42 you wrote: Brian, You are welcome. Are you talking about http://projecteuler.net/ ? I have been experimenting with various ways of learning Haskell, tackling an interesting set of mathematical problems sounds good. Best Regards, Robert On Thursday 12 July 2007 00:06, Brian L. Troutwine wrote: Hello Robert, Thanks for the comments. The lazy list with Double phi embedded does indeed begin to deviate, at the 81st Fibonacci number, if I'm not mistaken. Another fellow in this thread calculated the deviation points for Double, Float and CReal. By way of further explanation, I'm writing up various approaches and solutions to the problems posed at Project Euler, discussing the various defects to each approach, comparing the runtimes of solutions and, hopefully, deriving interesting tidbits of math along the way. The project was begun to improve my Haskell ability by exercising it in as many ways on a single idea as possible. I'd not thought of the algorithm you pointed out in SICP and will now happily include it. Thanks. Brian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Haskell monads for newbies (was Functional dependencies *not* part of the next Haskell standard?)
On Thu, 2007-07-12 at 16:01 +0200, peterv wrote: Thanks for the advice. I did not really deeply investigate the monad type classes yet... It looks like its gonna take a long time for me to learn Haskell. I'm not sure if my long history of imperative and object-oriented programming has something to do with it. Reading Haskell books like SOE is one thing, but writing software in Haskell is really difficult for me. Not only do I miss the spoiled OO programmer IDEs with all their candy and code completion and assistants, but I also get the feeling that although similar programs in Haskell or typically N times shorter than their imp/OO counterparts, it would take *me* at least N^2 longer to write them ;) (now I must admit I had the same feeling when switching from 680x0 assembler to C++, but let's say N*2 longer instread of N^2...) Is this true for Haskell in general? I mean how long do experienced Haskell developers spent writing code to get it right (excluding minor bugs and performance issues)? Or do they write down Haskell fluently? Skilled Haskell programmers write Haskell fluently, but I'd say that that still tends to require more thought per line on average than a typical imperative language. A single line of Haskell tends to do a heck of a lot more than a single line of mainstream imperative languages. Usually, though, once you get a nice base encoding your domain concepts, things move faster. The more code you write the -less- thinking you should need to do relative to imperative languages. Haskell code complexity grows (much) slower with size as compared to most imperative languages. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unresolved overloading
g x = [2] ++ [3,5..truncate(sqrt x)]
p n= fp n (g n)
fp n [ ]= True
fp n (x:xs) = if (mod n x) == 0 then False else fp n xs
ERROR - Unresolved overloading
*** Type : (RealFrac a, Floating a, Integral a) = Bool
*** Expression : p 103
I know why, there is no type that is at the same time: RealFrac,
Floating and Integral; but I don´t know how to solve.
What kind of type casting or type definition can I use to fix the error?
this can be turned into a nice small example for many things are a
right, and many things that are wrong with haskell numeric programs
(cf. http://www.haskell.org/haskellwiki/Generic_numeric_type ).
not only are the typical type errors confusing, and give little help
with fixing the issue (deliberately highlighting unresolved choices
rather than choosing arbitrary defaults, but not even suggesting
possible conversions with pros and cons [*]), but placating the
type system in various ways is not sufficient to guarantee useability,
or intended results, and seemingly simple rewrites may require
type system extensions to remain simple.
first, note that the definitions typecheck even though it would
be difficult to find a correct way of using them. next, consider
the variations appended below (using different conversions,
or breaking the strong connection introduced by the lambda-
bound 'n' in the original 'p0'). again, this typechecks, and can
indeed be used, but that is no guarantee that the variants are
equivalent, or do what was intended, or even work for other
use cases. for fun, try changing '103' to '103.5' (and no, you
can't abstract that to a where-clause unless you rely on
'no-monomorphism-restriction'), then comment out the lines
in main that start raising errors one by one, then run the
remaining lines and enjoy the result. then consider whether
this is indeed an intended use case.
i'm all for safe, explicit coercions rather than unsafe defaults.
but typechecking definitions is not sufficient to guarantee
either useability or correctness here, and type errors give little
help in clarifying intentions and correcting code. in other words,
there is something wrong in this part of haskell, even below
the concerns that usually lead to alternative numerical preludes.
i'm not at all sure to what extent this can be improved, but
when the topic comes up, good examples are usually hard
to come by, so i just wanted to record this one here for the
mailing-list archives.
claus
[*] sometimes i wonder whether there should be a
WrongNum type, which would imply all the usual
default conversions of scripting languages, but would
generate warnings at each dubious usage site (about
comparing Doubles, or losing precision, or possible
overflows, ..).
that way, beginners might at least get something running
that they could then improve until the warnings are gone,
avoiding the blank-page effect. instead of saying i have
no idea what to do here, the system would say i'm
defaulting to Double here, but that might not be a good
idea, so please confirm this decision explicitly in the code,
or i'm applying this implicit conversion here, but this has
semantic consequences, so you probably want to choose
this or a related conversion explicitly in your code..
-- code variations
{-# OPTIONS_GHC -fno-monomorphism-restriction #-}
{-# OPTIONS_GHC -fglasgow-exts #-}
g x = [2] ++ [3,5..truncate(sqrt x)]
p0 n = fp n (g n)
p1a n = fp (truncate n) (g n)
p1b n = fp (round n) (g n)
p1c n = fp n (g $ fromIntegral n)
p2 n n' = fp n (g n')
p3 :: (forall a. Num a = a) - Bool
p3 n = fp n (g n)
fp n [ ] = True
fp n (x:xs) = if (mod n x) == 0 then False else fp n xs
main = do
-- print $ p0 103 -- original, with type error
print $ p1a 103
print $ p1b 103
print $ p1c 103
print $ p2 103 103
print $ let x = 103 in p2 x x -- requires no-monomorphism-restriction
print $ let x _ = 103 in p2 (x ()) (x ())
print $ p3 103 -- requires glasgow-exts
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Looking for final year project - using Haskell, or another functional language
Building on what Hugh was getting at, beyond better opengl bindings, I'd be interested in what a modern real-time graphics engine would look like in Haskell; not a game engine, just a very flexible and well made universal graphics engine. I think there's already a lot of ground work already broken in with a practical example of Yampa via Frag, http://aegisknight.org/papers/Renaissance%202005.pdf and http://conal.net/papers/Vertigo/ for purely functional programming of shaders, etc. At the same time, however, there's still a decent amount of work to be explored outside that core with the: * Representation of objects - internal scene graph description and optimization for different types of scenes such as indoor (bsp?), landscapes (octree?) as well as issues wrt a scene or collection of scenes' actual definition. * Perhaps questions relating to collections of objects (hierarchical issues). * Procedural texture and model generation - some interesting work with Pan and derivatives, but certainly nothing incorporated into a 3d engine afaik. That being said, it's important to be able to design it separately besides just having the engine render it, but the popular demoscene (http://www.werkkzeug.com/), professional (http://www.profxengine.com/), and open source (http://www.fxgen.org/) tools all use artist oriented design methods (linking literal function boxes with arrows or stacking them upon each other) and thus are inherently crippled in functionality (and they become incomprehensible with any large size). A proper DSL incorporating some of Pan's features with the larger math libraries of the 3 examples above would allow a superior tool by simply combining [text editor of your choice] and a small app using the engine's procedural generation libraries to compile your MaterialDescriptionLanguage code and provide a preview window. * Somewhat related matters such as plugin based texture rendering (ie rendering a video to texture via external video decoding plugin). * Automatically generated LOD meshes and detecting when to apply them optimally. Haven't personally read anything on this, but a quick search on citeseer gives a large number of promising papers. Beyond the graphics aspect there are also somewhat related networking issues (simulation visualizers, multiplayer games) if you're more interested in that. * Animation - I know little about this. (I'm told) Yampa could be of great use, but I'm not sure how it ties in with standard animation techniques with key frames, IK bones, and whatnot. * Effects such as particle systems, post processing, and cloth simulation seem like a great place to exploit the easy concurrency inherent to purity (see Particle animation and rendering using data parallel computation for a start), although post processing would be very simple if you incorporated a good shader DSL similar to vertigo as noted above. * Ability to query the scene for integration with other code for object picking, that is, translating 2d-3d to figure out what the user clicked, for apps, AI if used with a simulation or game of sorts (ie accurate response to shadows cast by other actors), etc. You might be able to prevent this from forcing the rendering to pause, but nothing comes to mind. AFAIK, if STM retried your query you would get the next frame's data (or later), which may still be ok, but the delay might be visible to the user. * Resource management for large asset collections. The real trick here is you need to stay real-time and so lazy methods simply won't work. I assume you could apply a good deal of techniques from preemptive/speculative evaluation and garbage collection. If you did something with scene management above you could do a static analysis of all the scenes that need to be processed before the user is willing to wait (ie game-level, simulation-large time chunk?) to optimize when you perform the loads/clears. Dynamically generated data might pose a few extra difficulties. Games such as Halo have hard coded hallways and elevators as times for the graphics engine to load data, but I think a general heuristic for figuring out something similar is feasible with 1-2 passes over a (quasi?)4D scene graph (add [Tree] of the data required to render a collection of scenes over time). Just a few *very* rough ideas I'm thinking of at the moment; certainly more (and more depth) to consider. I apologize for the archaic formatting, I'll try to tex/wiki up a formal list of questions soon. Hope you enjoy whichever project you end up choosing, Joseph Re From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Hugh Perkins Sent: Tuesday, July 10, 2007 4:46 PM To: wp; haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Looking for final year project - using Haskell,or another functional language rpc layer, like .Net Remoting or ICE (but preferably without needing configuration/interface files) Course, if you know what you're
Re: [Haskell-cafe] money type ?
At Thu, 12 Jul 2007 00:42:46 -0700, Simon Michael wrote: Good day all, my budding ledger program could not balance transactions exactly because of rounding error with Double. I *think* I got it working better with Rational (it was late). Another suggestion from #haskell was to multiply all money by 100. I'm tracking multiple currencies/commodities with varying precision so this gets a bit more complicated. Is there a type or library out there that's good for representing money and other quantities while avoiding rounding errors ? Almost. I have a mostly complete Decimal library for Haskell available at: http://www.n-heptane.com/nhlab/repos/Decimal/ It aims to meet the same goals the Python Money PEP: http://www.python.org/dev/peps/pep-0327/ Most of the implementation details are described in this standard: http://www2.hursley.ibm.com/decimal/ Currently there are two very significant bugs: 1. the rounding algorithm is completely wrong 2. In the division routine, I explicitly limit the number of digits after the decimal point to 9 places. Using the Decimal library you can then implement a Money type similar to what is show in: http://www.n-heptane.com/nhlab/repos/Decimal/Money.hs essentially, you declare a phantom data type like: data Money currency = Money Decimal which you can then parameterize by different types of currency data Dollar = Dollar data Yen = Yen fiveDollars :: Money Dollar fiveDollars = 5 fiveYen :: Money Yen fiveYen = 5 because the types are different, you won't be able to accidently charge someone 5 yen instead of 5 dollars :) However, you can still write currency agnostic functions: doubleMyIncome :: Money c - Money c doubleMyIncome income = income * 2.0 So, the decimal library is almost, but not quite, usable. Fixing the two (known) problems is not that hard, I just have not had the time. Also, the library really needs a good test suite before it can be considered suitable for an accounting program ;) Fortunately, the python library already has a good test suite that can copied. I believe the spec at IBM also includes a bunch of examples that could be interegrated into a test suite. The library includes the beginnings of a test suite, but it is not very complete. I am definitely willing to give guidance and assistance if you, or someone else, wants to help finish up the library. j. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Simple newbie question - Int and Integer
So what the hell is the difference between them? Int and Integer. They aren't synonyms clearly. What's going on? Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos more. http://mobile.yahoo.com/go?refer=1GNXIC___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] CGI test
Hugh Perkins wrote: Here you go: module SimpleCgiServer where import IO import Char import Network import Control.Monad import System.Process listensocket = 2000 main = withSocketsDo $ do socket - listenOn (PortNumber listensocket) mapM_ (\_ - handleconnection socket) (iterate (id) ()) sClose socket handleconnection socket = do (handle,hostname,portnumber) - accept socket putStrLn (show(hostname) ++ ++ show(portnumber)) hSetBuffering handle LineBuffering line - hGetLine handle let filename = drop( length(GET /) ) line htmltoreturn - runprocess filename hPutStr handle htmltoreturn runprocess filename = do (stdin,stdout,stderr,processhandle) - runInteractiveCommand filename waitForProcess processhandle contents - hGetContents stdout return contents Thanks for trying - but that doesn't actually work. (For starters, you need to prepend the HTTP status code to the data from the CGI script...) Actually, as it turns out, the script I want to test needs to accept POST data, and the parsing is really quite complicated, and I want it to not crash out if I type the URL wrong, and... Basically, the more I look at this, the more I realise that it really truely *is* going to be faster to just use a real web server. I thought I could just implement a tiny subset of it to get a working system, but it turns out the subset I need isn't so tiny... Sorry guys. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
Albert Y. C. Lai wrote: Andrew Coppin wrote: When I tell the editor to save UTF-8, it inserts some weird BOM character at the start of the file - and thus, any attempt at programatically processing that file instantly fails. :-( I know Windows Notepad puts a BOM at the beginning of UTF-8 files. http://www.vex.net/~trebla/w.htm is written out by Notepad and has the beginning BOM. Firefox and IE display it just fine. Windows Notepad, GNOME gedit, Emacs, Vim, and Eclipse are also very graceful about it. If you rename it to w.lhs, GHC reads it as a fine Haskell source file, as I sneaked in a little Haskell hello-world as an HTML comment, e.g., runghc w.lhs does wonder. So much for BOM foiling any processing. Any more FUD to debunk? Wanna hear something about purely functional languages incapacitated for I/O? Static typing leading to excessive type declarations? Automatic garbage collection irrelevant to the real world? Let me put it this way: It makes all my Tcl scripts stop working, and it makes my Haskell-based processor go nuts too... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple newbie question - Int and Integer
On Thu, Jul 12, 2007 at 10:58:38AM -0700, Gregory Propf wrote: So what the hell is the difference between them? Int and Integer. They aren't synonyms clearly. What's going on? [EMAIL PROTECTED]:/usr/local/src/ghcbuild$ ghci Loading package base ... linking ... done. ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | |GHC Interactive, version 6.7.20070612, for Haskell 98. / /_\\/ __ / /___| |http://www.haskell.org/ghc/ \/\/ /_/\/|_|Type :? for help. Prelude 1 :: Integer 1 Prelude 1 :: Int -727379968 Prelude Int is fifteen times faster, but vulnerable to overflow errors. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] better error expression in IO function
Brandon S. Allbery KF8NH wrote: On Jul 11, 2007, at 15:57 , brad clawsie wrote: i know the Either type can be used in such a case(?), but i've had some problem locating a satisfactory example (if this is indeed appropriate) You might want to look at MonadError (Control.Monad.Error), more specifically ErrorT layered on top of IO. I think *I* might want to spend some time reading about that... (Throwing and catching exceptions is just fiddly.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Toy compression algorithms
Thomas Conway wrote: On 7/12/07, Andrew Coppin [EMAIL PROTECTED] wrote: Yes - but making it use a non-flat model opens a whole Pandora's Box of fiddly programming. ;-) This could just about be Rule No 1 of haskell programming: if it's fiddly, then you haven't thought about the problem hard enough. Corollary No 1 is Any Expression requiring more than 80 columns is fiddly. :-) I say this in jest, but it is ha ha, only serious. LOL! Probably... The idea behind PPM is very simple and intuitive. But working out all the probabilities such that they always sum to 100% is surprisingly hard. :-( ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Lazy Lists and IO
Derek Elkins wrote: On Wed, 2007-07-11 at 22:33 +0200, Chaddaï Fouché wrote: 2007/7/11, Andrew Coppin [EMAIL PROTECTED]: Ouch! That's gotta sting... I wasn't aware that this function was so leathal. I use it constantly all the time... It isn't that lethal usually. It's only because he was using it on an infinite stream that it hurt so much... If you use it on a normal stdin or a hGetContents on a file it will be fine (though you will lose the advantage of its laziness, for example constant memory treatment). Nevertheless, length is a function you should rarely use. Amen. (I believe the Wiki mentions this concept somewhere... Maybe we should rename it unsafeLength? No, OK, how about... um... slowLength?) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
Bernie Pope wrote: On 12/07/2007, at 4:43 AM, Andrew Coppin wrote: Bernie Pope wrote: This reminds me of a little joke that Conor McBride had in a post a while ago: unJust :: Maybe wmd - wmd Oh, very good! I must write that down somewhere... I tell it to my Haskell students each semester and it usually gets a giggle. I also ask them why is it possible to write jokes in Haskell's types, which often leads to some interesting discussions about logic and the nature of jokes etc. I told it to the guys on the POV-Ray forum. Sadly, I think most of them have by now set up filters to delete all posts containing words such as Haskell... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple newbie question - Int and Integer
To be more precise, Int represents a machine-sized integer value, so it is limited in size but doing math with Int values translates directly into math on the processor. Integer can store integer values of arbitrary size, which is useful sometimes but is of course a lot slower, since the pieces of an Integer value have to be stored in some sort of list, and specialized code is used to do arithmetic with Integers by operating on the pieces and combining the results. How have you been learning Haskell? I'm guessing this is probably covered in most tutorials. -Brent On 7/12/07, Gregory Propf [EMAIL PROTECTED] wrote: So what the hell is the difference between them? Int and Integer. They aren't synonyms clearly. What's going on? -- Don't be flakey. Get Yahoo! Mail for Mobilehttp://us.rd.yahoo.com/evt=43909/*http://mobile.yahoo.com/mailand always stay connectedhttp://us.rd.yahoo.com/evt=43909/*http://mobile.yahoo.com/mailto friends. ___ 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] Newbie question about tuples
peterv wrote: Hi, I have a couple of questions about tuples. Q1) Is it possible to treat a tuple of N elements in a generic way? So instead of writing functions like lift1 e1, lift2 (e1,e2), lift3 (e1,e2,e3) just one function liftN that works on tuples of any length? The only thing the libraries provide, as far as I can tell, is the fact that tuples are all Functors. (In other words, you can apply some function to all the elements to get a new tuple.) I think that's about it. I doubt you can use that to define lifting functions... Q2) (Maybe related to Q1) Can I convert a tuple of length N to a heterogeneous list (using forall aka existentially quantified types) and vice versa? I think you're going to need to play with type classes to do that. Q3) Suppose I want to declare an instance of Num on all tuple types having (Num instances) as elements; is this possible? I tried instance Num a = Num (a,a) where . but this fails I also tried instance Num a = Num ((,) a a) where . but that also fails. I tried to do this a while ago and couldn't figure out how. :-( ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
Alexis Hazell wrote: On Thursday 12 July 2007 04:40, Andrew Coppin wrote: I once sat down and tried to read about Category Theory. I got almost nowhere though; I cannot for the life of my figure out how the definition of category is actually different from the definition of set. Or how a functor is any different than a function. Or... actually, none of it made sense. Iiuc, Set is just one type of category; and the morphisms of the category Set are indeed functions. But morphisms in other categories need not be functions; in the category Rel, for example, the morphisms are not functions but binary relations. A functor is something that maps functions in one category to functions in another category. In other words, functors point from one or more functions in one category to the equivalent functions in another category. Perhaps they could be regarded as 'meta-functions'. Hope that helps, It helps a little... I'm still puzzled as to what makes the other categories so magical that they cannot be considered sets. I'm also a little puzzled that a binary relation isn't considered to be a function... From the above, it seems that functors are in fact structure-preserving mappings somewhat like the various morphisms found in group theory. (I remember isomorphism and homomorphism, but there are really far too many morphisms to remember!) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple newbie question - Int and Integer
Gregory Propf wrote: So what the hell is the difference between them? Int and Integer. They aren't synonyms clearly. What's going on? Int = 32-bit integer. Integer = arbitrary precision integer. (See also Data.Integer and Data.Word, which provide signed and unsigned integers of other sizes.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Lazy Lists and IO
Nevertheless, length is a function you should rarely use. Amen. (I believe the Wiki mentions this concept somewhere... Maybe we should rename it unsafeLength? No, OK, how about... um... slowLength?) It isn't actually slow... how about beSureYouReallyWantIntBeforeUsingThisLength? =) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Lazy Lists and IO
Brent Yorgey wrote: Nevertheless, length is a function you should rarely use. Amen. (I believe the Wiki mentions this concept somewhere... Maybe we should rename it unsafeLength? No, OK, how about... um... slowLength?) It isn't actually slow... how about beSureYouReallyWantIntBeforeUsingThisLength? =) O RLY? length [1..] Takes almost *forever* on my machine. ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
Stefan O'Rear wrote: On Thu, Jul 12, 2007 at 07:19:07PM +0100, Andrew Coppin wrote: I'm still puzzled as to what makes the other categories so magical that they cannot be considered sets. I'm also a little puzzled that a binary relation isn't considered to be a function... From the above, it seems that functors are in fact structure-preserving mappings somewhat like the various morphisms found in group theory. (I remember isomorphism and homomorphism, but there are really far too many morphisms to remember!) Many categories have more structure than just sets and functions. For instance, in the category of groups, arrows must be homomorphisms. What the heck is an arrow when it's at home? Some categories don't naturally correspond to sets - consider eg the category of naturals, where there is a unique arrow from a to b iff a ≤ b. ...um... Binary relations are more general then functions, since they can be partial and multiple-valued. What's a partial relation? indeed, it is possible to form the category of small categories with functors for arrows. (Small means that there is a set of objects involved; eg Set is not small because there is no set of all sets (see Russel's paradox) but Nat is small.) OK, see, RIGHT THERE! That's the kind of sentence that I read and three of my cognative processes dump sort with an unexpected out of neural capacity exception. o_O ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple newbie question - Int and Integer
On Thu, Jul 12, 2007 at 07:39:09PM +0100, Andrew Coppin wrote: Gregory Propf wrote: So what the hell is the difference between them? Int and Integer. They aren't synonyms clearly. What's going on? Int = 32-bit integer. Int = 30 bits with undefined overflow behavior That undefined gives implementations the freedom to use bigger representations if convenient. GHC: 31, 32 or 64 bits (from source code) Hugs: 32 bits (only tested on a 32 bit computer) YHC: 32 or 64 bits (from source code) JHC: Buggy (maxBound :: Int is negative) Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple newbie question - Int and Integer
Stefan O'Rear wrote: On Thu, Jul 12, 2007 at 07:39:09PM +0100, Andrew Coppin wrote: Int = 32-bit integer. Int = 30 bits with undefined overflow behavior That undefined gives implementations the freedom to use bigger representations if convenient. Personally, my rule of thumb is this: Int = some number Integer = some *big* number Int32 (or whatever) = I actually want it exactly THIS size. So I just use Int when I don't really care what size the integer is - mainly becuase *everything* seems to use Int and it saves on explicit type conversions all over the place. (I'm not actually too sure that Int *should* be used all over the place - but it'll never be changed, so...) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question about tuples
On Thu, 12 Jul 2007, Andrew Coppin wrote: peterv wrote: Q3) Suppose I want to declare an instance of Num on all tuple types having (Num instances) as elements; is this possible? I tried instance Num a = Num (a,a) where . but this fails I also tried instance Num a = Num ((,) a a) where . but that also fails. I tried to do this a while ago and couldn't figure out how. :-( The new approach of peterv using data Vector2 a = Vector2 a a is more sane. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Very freaky
Alexis Hazell wrote: On Thursday 12 July 2007 04:40, Andrew Coppin wrote: I once sat down and tried to read about Category Theory. I got almost nowhere though; I cannot for the life of my figure out how the definition of category is actually different from the definition of set. Or how a functor is any different than a function. Or... actually, none of it made sense. Iiuc, Set is just one type of category; and the morphisms of the category Set are indeed functions. But morphisms in other categories need not be functions; in the category Rel, for example, the morphisms are not functions but binary relations. A functor is something that maps functions in one category to functions in another category. In other words, functors point from one or more functions in one category to the equivalent functions in another category. Perhaps they could be regarded as 'meta-functions'. Hope that helps, It helps a little... I'm still puzzled as to what makes the other categories so magical that they cannot be considered sets. Another example: a partially ordered set is a category. The objects are the elements and there is an arrow between two objects a b if a = b. An element isn't (necessarily) a set. Nothing magical here. A functor is then an order preserving function (homomorphism). This question has come up more than once so it may be worth a wiki page if anyone has time. I'm also a little puzzled that a binary relation isn't considered to be a function... That's the definition of a function: a restricted relation in which there is at most one range element for a given domain element - see any book on set theory e.g. Halmos. From the above, it seems that functors are in fact structure-preserving mappings somewhat like the various morphisms found in group theory. (I remember isomorphism and homomorphism, but there are really far too many morphisms to remember!) Sometimes but clearly the forgetful functor doesn't. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Lazy Lists and IO
On Thu, 12 Jul 2007, Andrew Coppin wrote: (I believe the Wiki mentions this concept somewhere... Maybe we should rename it unsafeLength? No, OK, how about... um... slowLength?) http://www.haskell.org/haskellwiki/Things_to_avoid#Don.27t_ask_for_the_length_of_a_list_when_you_don.27t_need_it http://www.haskell.org/haskellwiki/Peano_numbers ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
AC I'm still puzzled as to what makes the other categories so magical AC that they cannot be considered sets. They are just too big. The set of all sets can't exist, you know. That's news. How come the set of all sets doesn't exist? Well, you mentioned that you have some knowledge of group theory, so let me give you three examples of adjoint functors (don't worry, it won't hurt) - two from the group theory and one related to Haskell. 1) Consider the category Set of all sets - it's objects are sets and it's morphisms (=arrows) are functions between sets. Also, there is a category Grp of groups - with groups as objects and homomorphisms as morphisms. Then, the trivial mapping G: Grp - Set, which maps each group to it's base set (and each homomorphisms to itself - as a function from one base set to another) is a functor (it is called forgetting functor, I guess, since it forgets the group structure). There is a very natural functor F: Set - Grp. Namely, F maps each set X to the free group, with generators corresponding to elements of X. By definition, each function f:X-H, where H is a group, can be extended to the homomorphism f*:F(X)-H. That means that there is a natural bijection between functions X-H (more precisely, from X to G(H), since these functions aren't related to the group structure on H) and homomorphisms F(X)-H: Set(X,G(H)) ~ Grp(F(X),H) Here by Grp(H1,H2) I denote the set of morphisms (=homomorphisms) from H1 to H2; the same notation is used for Set. That means exactly that F is LEFT ADJOINT to G (or, equivalently, G is right adjoint to F). Their composition GF is a monad on the category Set. GF(X) is the set of all elements of the free group, generated by X. For a in X, return(x) is an element of the free group, corresponding to x. And if we have a map X-GF(Y) and an element of GF(X), we can remember that GF(Y) carries some group structure, so our map is in fact a map from X to some group, which extends to a homomorphism from F(X) to F(Y), which is a map from GF(X) to GF(Y), which maps our chosen element of GF(X) to an element of GF(Y) - that gives us (=). That almost made sense most of the way through... but... ooouch... x_x 2) There is a category Ab of abelian groups (and homomorphisms). Of course, there is a trivial functor G: Ab - Grp, which maps each abelian group to itself. There is also a functor F: Grp - Ab; it maps each group H to it's abelianization: F(H) = H/[H,H]. F is also left adjoint to G: there is a bijection between homomorphisms H - A, where A is abelian, and homomorphisms H/[H,H] - A. Again, there composition GF: Grp - Grp is a monad (on Grp this time). There are many other constructions that happen to be adjoint functors; and that is a kind of generalization that makes mathematics so useful and exciting. These constructions include all kinds of free structures - free modules, algebras etc.; discrete and codiscrete topological spaces, and many others. 3) Let X be a set. I'll denote here the set of all functions from X to Y by X-Y, and the product XxY (small x stands here for the times sign) by (X,Y), sticking to the Haskell notation. Then the functor (X -): Set - Set which maps each set Y to the set X-Y, is right adjoint to the functor (,X), mapping each set Y to (Y,X): there is a bijection between functions from Z to (X-Y) and functions from (Z,X) to Y. This bijection is called currying. The composition of this functors is - as always - monad: it maps Y to X-(Y,X). And this is a kind of monad we are familiar with: it's the State monad. Summarizing, we have the following: State monad exists because of currying. Again... that almost makes some sort of sense... but this is REALLY making my head hurt! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
On 7/12/07, Andrew Coppin [EMAIL PROTECTED] wrote: How come the set of all sets doesn't exist? http://www.google.com/search?q=set+of+all+sets leads to http://en.wikipedia.org/wiki/Set_of_all_sets which has the answer, I think. -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Lazy Lists and IO
On Thursday 12 July 2007, Andrew Coppin wrote:
Jonathan Cast wrote:
On Wednesday 11 July 2007, Chaddaï Fouché wrote:
Is there something I misunderstood in the exchange ?
Yeah. The reference to the lazy natural type, which is:
data Nat
= Zero
| Succ Nat
deriving (Eq, Ord, Read, Show)
instance Num Nat where
fromInteger 0 = Zero
fromInteger (n + 1) = Succ (fromInteger n)
etc.
then genericLength xn n does exactly what Andrew wants, when n :: Nat.
Wow.
Show me a simple problem, and some Haskeller somewhere will find a
completely unexpected way to solve it... LOL!
OTOH, doesn't that just mean that Nat is itself a degenerate list, and
genericList is just converting one list to another, and the Ord instance
for Nat is doing the short-cut stuff?
Yes. Nat ~ [()], where ~ means `is isomorphic to'. But Nat is also the
obvious way to encode Peano arithmetic in Haskell, so this is a deep thought,
not a shallow one.
(Properly speaking, the set of total values of Nat is the set of natural
numbers + infinity (infinity = x where x = Succ x), and the set of total
lists of type [alpha] is
sum (n :: Nat). f :: {m :: Nat | m n} - alpha
where f and n are total. sum is a dependent sum, which is just a product, and
the only total function with co-domain () is const () (well, and (`seq` ()),
but they're equal on total arguments), so that type is just
sum (n :: Nat^inf). {const ()}
which is isomorphic to Nat^inf. But you can see that this is a deep thought,
not a shallow one. . .)
Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question about tuples
peterv wrote: Hi, I have a couple of questions about tuples. Q1) Is it possible to treat a tuple of N elements in a generic way? So instead of writing functions like lift1 e1, lift2 (e1,e2), lift3 (e1,e2,e3) just one function liftN that works on tuples of any length? If you have instances of Data across the board, you should be able to do this with gmap, gfoldl, etc. (See Data.Generics). Short of that, you'd have a hard time writing the type of liftN. Q2) (Maybe related to Q1) Can I convert a tuple of length N to a heterogeneous list (using forall aka existentially quantified types) and vice versa? Use Data.Dynamic.Dynamic instead of explicit existentially quantified types, and it should come from gfoldl pretty readily. snip Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Lazy Lists and IO
Jonathan Cast wrote: On Thursday 12 July 2007, Andrew Coppin wrote: Wow. Show me a simple problem, and some Haskeller somewhere will find a completely unexpected way to solve it... LOL! OTOH, doesn't that just mean that Nat is itself a degenerate list, and genericList is just converting one list to another, and the Ord instance for Nat is doing the short-cut stuff? Yes. Nat ~ [()], where ~ means `is isomorphic to'. But Nat is also the obvious way to encode Peano arithmetic in Haskell, so this is a deep thought, not a shallow one. That thought was not lost on me. ;-) I was just thinking that in mundane machine terms, we're not doing anything especially remarkable here... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Number overflow
Of course you should be able to specify what types you want. But it would be nice if the default was correct rather than fast. On 7/12/07, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Thomas, Thursday, July 12, 2007, 3:14:57 AM, you wrote: The differences between Int and Integer operations are mostly constant factors. well, i will be unlucky if in my real-world program Integers would be used instead of Ints. defaulting provides a great way to solve this dilemma, so good-for-anyone approach may be: default defaulting to Integer instead of Int, and use (Num a) instead of Int in all standard functions such as length. with jhc-like automatic specialization feature this should provide enough speed -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ 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] Type system madness
On Thu, Jul 12, 2007 at 07:01:31PM +0100, Andrew Coppin wrote: Let me put it this way: It makes all my Tcl scripts stop working, and it makes my Haskell-based processor go nuts too... Given that (IIRC) the BOM is just a valid unicode non-breaking space, your scripts really ought to cope... Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Numbers : [Haskell-cafe] Number overflow
Out of curiosity, what ever happened to the proposal a while back to refactor the Num class etc so that the operations would be grouped according to what abstract algebra notions they correspond to? My understanding was that doing this would make haskell numerics much more sensible. Eg array indexing could be done by any type that is isomorphic to natural numbers etc. cheers, -Carter - Original Message From: Lennart Augustsson [EMAIL PROTECTED] To: Bulat Ziganshin [EMAIL PROTECTED] Cc: haskell-cafe@haskell.org Sent: Thursday, July 12, 2007 4:14:31 PM Subject: Re: Re[2]: [Haskell-cafe] Number overflow Of course you should be able to specify what types you want. But it would be nice if the default was correct rather than fast. On 7/12/07, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Thomas, Thursday, July 12, 2007, 3:14:57 AM, you wrote: The differences between Int and Integer operations are mostly constant factors. well, i will be unlucky if in my real-world program Integers would be used instead of Ints. defaulting provides a great way to solve this dilemma, so good-for-anyone approach may be: default defaulting to Integer instead of Int, and use (Num a) instead of Int in all standard functions such as length. with jhc-like automatic specialization feature this should provide enough speed -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Very freaky
They are just too big. The set of all sets can't exist, you know. That's news. It was news to Frege. How come the set of all sets doesn't exist? Russell's paradox - see e.g. Halmos: Naive Set Theory. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Thu, Jul 12, 2007 at 09:24:24PM +0100, Philip Armstrong wrote: On Thu, Jul 12, 2007 at 07:01:31PM +0100, Andrew Coppin wrote: Let me put it this way: It makes all my Tcl scripts stop working, and it makes my Haskell-based processor go nuts too... Given that (IIRC) the BOM is just a valid unicode non-breaking space, your scripts really ought to cope... Oh wait, is the problem that the scripts are expecting ascii, and are breaking on the non-breaking space? That makes a certain amount of (annoying) sense. Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Thu, 12 Jul 2007 21:24:24 +0100, you wrote: Given that (IIRC) the BOM is just a valid unicode non-breaking space, your scripts really ought to cope... Choking on the BOM is probably just a symptom of a deeper problem. My bet is that removing the BOM would simply delay the failure until the first non-ASCII character was encountered. 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] Very freaky
On Thu, 12 Jul 2007 20:36:47 +0100, you wrote: How come the set of all sets doesn't exist? In naive set theory, the existence of the set of all sets leads to a logical paradox. Specifically, the set of all sets would have to contain as a member the set of all sets that are not members of themselves. Look up Russell's Paradox in Wikipedia. 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] Very freaky
On 7/12/07, Andrew Coppin [EMAIL PROTECTED] wrote:
Stefan O'Rear wrote:
On Thu, Jul 12, 2007 at 07:19:07PM +0100, Andrew Coppin wrote:
I'm still puzzled as to what makes the other categories so magical that
they cannot be considered sets.
I thought I'd dive in with a comment to explain why category theory is
an important subject and why it often crops up in Haskell programming.
The key thing is this: in many branches of mathematics people draw
what are known as commutative diagrams:
http://mathworld.wolfram.com/CommutativeDiagram.html
So what do these diagrams represent? The letters at the 'vertices'
(known as objects) often represent sets and the arrows represent
functions. But in different branches of mathematics the same diagrams
appear with the objects and arrows having a quite different
interpretation. For example you could use a diagram like 1 - 2 to
mean 12. Or you could use X - Y to mean X implies Y. Or in {1,2} -
{4,5,6} the arrow might mean containment and so on. But here's a
remarkable fact: you can often take a definition in one branch of
mathematics and write it diagrammatically. You can then reinterpret
that diagram in a different branch of mathematics as different
definition. Sometimes the new definition isn't interesting, but often
it is. So now you can define things in multiple branches of
mathematics at the same time. It gets better. Statements of theorem
can also sometimes be written in purely diagrammatic language so a
theorem that holds in one branch of mathematics turns out to be an
interesting theorem in another. Sometimes the entire proof can be
written diagrammatically meaning you can solve problems in different
branches of mathematics at the same time. This whole
'multidisciplinary' subject is known as Category Theory.
To a good approximation (and there is a certain amount of choice over
which approximation you pick) Haskell also forms a category. The
objects are types and the arrows are functions. But as I've also
hinted above, objects can represent propositions and arrows can
represent implication. So that suggests theorems about logic might
carry over to theorems about Haskell. They do, as has been mentioned
in another thread. But that's a special case of a much wider
phenomenon where constructions in different parts of mathematics can
feed into Haskell.
So knowing category theory can help you to bring to bear mathematical
knowledge from other fields when writing Haskell code. A big example
of that payoff has been the notion of a monad. But there are many
more.
It also works the other way too. As you acquire a grasp of Haskell you
get insight into other parts of mathematics and computer science, even
if you don't yet know it! Haskell has certainly helped me this way.
(And I should confess that this is one of my primary motivations for
learning it.)
--
Dan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
Felipe Almeida Lessa wrote: On 7/12/07, Andrew Coppin [EMAIL PROTECTED] wrote: How come the set of all sets doesn't exist? http://www.google.com/search?q=set+of+all+sets leads to http://en.wikipedia.org/wiki/Set_of_all_sets which has the answer, I think. Ouch. Clearly, set theory is way more complicated than people make out. (I always thought a set was just a collection of objects...) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Wed, Jul 11, 2007 at 10:31:36PM +0200, Hugh Perkins wrote: Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work: It's slightly worse than that: unix uniq only eliminates *consecutive* identical lines from its input. If you want to eliminate all duplicates, you have to pipe your input through sort first. testunique :: Eq a = [a] - [a] testunique list = testunique' list [] where testunique' :: Eq a = [a] - [a] - [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar | x `elem` elementssofar = (testunique' elementssofar xs) | otherwise = x : ( testunique' xs (x:elementssofar)) I suspect the author upthread had something more like this in mind: uniq :: Eq a = [a] - [a] uniq [] = [] uniq (x:xs) = x : filter (x/=) (uniq2 xs) Obviously a true 'unique' function has to traverse the entire list before it creates any output, as has been pointed out upthread. Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Thu, Jul 12, 2007 at 04:58:43PM -0400, Steve Schafer wrote: On Thu, 12 Jul 2007 21:24:24 +0100, you wrote: Given that (IIRC) the BOM is just a valid unicode non-breaking space, your scripts really ought to cope... Choking on the BOM is probably just a symptom of a deeper problem. My bet is that removing the BOM would simply delay the failure until the first non-ASCII character was encountered. Indeed. However, I can imagine that the author might well want to use unicode characters in string literals and comments, where they would be entirely inocuous (since a utf-8 string is a valid ascii string) but the BOM at the beginning of the file breaks things. Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Numbers : [Haskell-cafe] Number overflow
Carter T Schonwald wrote: Out of curiosity, what ever happened to the proposal a while back to refactor the Num class etc so that the operations would be grouped according to what abstract algebra notions they correspond to? The numeric prelude proposals have a wiki page: http://www.haskell.org/haskellwiki/Mathematical_prelude_discussion I think it's one of those things that doesn't have enough people itching over it for the collective mind to scratch. b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Philip Armstrong wrote: On Wed, Jul 11, 2007 at 10:31:36PM +0200, Hugh Perkins wrote: Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work: It's slightly worse than that: unix uniq only eliminates *consecutive* identical lines from its input. If you want to eliminate all duplicates, you have to pipe your input through sort first. testunique :: Eq a = [a] - [a] testunique list = testunique' list [] where testunique' :: Eq a = [a] - [a] - [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar | x `elem` elementssofar = (testunique' elementssofar xs) | otherwise = x : ( testunique' xs (x:elementssofar)) I suspect the author upthread had something more like this in mind: uniq :: Eq a = [a] - [a] uniq [] = [] uniq (x:xs) = x : filter (x/=) (uniq2 xs) Obviously a true 'unique' function has to traverse the entire list before it creates any output, as has been pointed out upthread. Phil Close. Actually, the author upstream (i.e. me) had in mind: uniq :: Eq a = [a] - [a] uniq [] = [] uniq (x:xs) = x : uniq (filter (/= x) xs) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] HDBC-ODBC build/install problem.
Hi, I am trying to make HaskellDB work with HDBC-ODBC. I did builds of HDBC/HDBC-ODBC. But when I am building HaskellDB-HDBC-ODBC, I get the following message. -- [1 of 1] Compiling Database.HaskellDB.HDBC.ODBC ( Database/HaskellDB/HDBC/ODBC.hs, dist\build/Database/HaskellDB/HDBC/ODBC.o ) C:\Program Files\Haskell\HDBC-odbc-1.1.2.0\ghc-6.6.1/Database/HDBC/ODBC/Connection.hi Declaration for connectODBC: Failed to load interface for `Database.HDBC.ODBC.ConnectionImpl': Use -v to see a list of the files searched for. Cannot continue after interface file error -- From this, I know the problem is the linkage between Database.HDBC.ODBC.Connection and Database.HDBC.ODBC.ConnectionImple. (Also I looked at the code to see the reference.) I did a little further investigation. I looked at the package registry area (C:\Program Files\Haskell\HDBC-odbc-1.1.2.0\ghc-6.6.1\Database\HDBC\ODBC) and notice that ConnectionImpl.hi is not there. I went back to the build directory and did find ConnectoinImpl.hi and ConnectionImpl.o. It seems like runghc Setup.hs install, did not install ConnectionImpl.hi. I looked into the file named .installed-pkg-config and I saw this: exposed-modules: Database.HDBC.ODBC hidden-modules: Database.HDBC.ODBC.Connection Database.HDBC.ODBC.Statement Database.HDBC.ODBC.Types Database.HDBC.ODBC.Utils Database.HDBC.ODBC.TypeConv import-dirs: C:\\Program Files\\Haskell\\HDBC-odbc-1.1.2.0\\ghc-6.6.1 library-dirs: C:\\Program Files\\Haskell\\HDBC-odbc-1.1.2.0\\ghc-6.6.1 hs-libraries: HSHDBC-odbc-1.1.2.0 extra-libraries: odbc32 -- No mention of ConnectionImple.hi. It looks like the setup up script did not install ConnectionImpl.hi. Did ConnectionImpl.o get bound into libHSHDBC-odbc-1.1.2.0.a even though ConnectionImpl.hi did not get successfully installed? Does anyone know why the install target does not install ConnectionImpl.hi and how I can get around this problem? (Where is the odbc32 to be found anyways?) Here are a few things I did try which did NOT work: 1. Copy ConnectionImpl.hi over manually. HaskellDB-HDBC-ODBC builds, but at runtime there is a link error. 2. Manually alter .installed-pkg-config to add ConnectionImpl.hi as hidden module. Please comment on why these would not work ( I will learn from this.) Help would be appreciated. Edward Ing ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions: unique :: Eq a = [a] - [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = [] This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first! Dan Dan Weston wrote: Close. Actually, the author upstream (i.e. me) had in mind: uniq :: Eq a = [a] - [a] uniq [] = [] uniq (x:xs) = x : uniq (filter (/= x) xs) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Thursday 12 July 2007, Dan Weston wrote: Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions: unique :: Eq a = [a] - [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = [] This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first! Actually, it would (well, sort of). GHC expends a good deal of effort looking for cases where pattern-matching is mutually-exclusive, and flattens it out to unique xn' = case xn' of [] - [] x : xn - x : unique (filter (/= x) xn) where each branch is equally efficient. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Sets and Universe. Was : Very freaky
Andrew Coppin: How come the set of all sets doesn't exist? ... Felipe Almeida Lessa cites a relevant page Ouch. Clearly, set theory is way more complicated than people make out. (I always thought a set was just a collection of objects...) You are right. A set is a collection of objects, nothing more, provided you know what is a collection, what is an object, and what is the meaning of the verb is. Since this is a café chat, I'll tell you a Zen story. A young apprentice thinks that an apple is just an apple. But then, he starts studying. One day he gets his enlightment, and learns that an apple is a terribly complicated entity. There are concrete apples, there is also an idea of an apple, a universal apple. He knows then that his apple is a symbol which hides inside the secret of the structure of our knowledge about things. He feels humble facing his apple, and yet happy that he could grasp some of its mysteries. The question what is an apple is an infinite source of other questions which lead him to the Wisdom. Seeral years later he becomes a Master. Now, he sees clearly that an apple holds also the knowledge about the structuration of the Unverse. His apple allows him to ask questions about, say, limit of things: where this apple begins? What does it mean inside? How to distinguish an apple from a non-apple? Can we ask where there are two identical apples? ... When the Master gets older, he sees also that apples hold the secrets of life and death. They symbolize - if one wants to see it - the Eternal Ring of perpetuation of things. You must destroy your apple in order to let grow new ones. ... et caetera. ++ Finally, our hero becomes a Great Master, a true one. He looks at the universe below him, and he sees, as clearly as never before, that an apple is just an apple... Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On 7/12/07, Dan Weston [EMAIL PROTECTED] wrote: Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions: unique :: Eq a = [a] - [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = [] This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first! Of course GHC detects that the cases are mutually exclusive. The code above desugars into a single definition of unique with a case expression on its argument. In Core, case expressions have at most one alternative for each data constructor of the type of the scrutinee, and since each alternative corresponds to a different top-level data constructor, alternatives are mutually exclusive. As for point (b), it hardly matters, since GHC will rearrange case alternatives at will (and I don't think the order of alternatives has any operational meaning anyway.) If you want to see this for yourself, try running GHC with the -ddump-simpl flag on a simple example (like the one above). Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt What doesn't kill you, makes you stronger -- or puts you on a talk show. --Carrie Fisher ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Numbers : Number overflow
On 2007-07-12, Bryan O'Sullivan [EMAIL PROTECTED] wrote: Carter T Schonwald wrote: Out of curiosity, what ever happened to the proposal a while back to refactor the Num class etc so that the operations would be grouped according to what abstract algebra notions they correspond to? The numeric prelude proposals have a wiki page: http://www.haskell.org/haskellwiki/Mathematical_prelude_discussion I think it's one of those things that doesn't have enough people itching over it for the collective mind to scratch. Well, that, and people are busy, and how to do some things depends on which of MPTC, Fundeps, AT, etc. make it into Haskell'. I mean, it's obvious it needs to be dealt with, and most everybody agrees on the general shape of things, the big concerns are with how much extra stuff beyond the basics should be defined by Haskell' rather than just enabled by a better numeric hierarchy. -- Aaron Denney -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Tim Chevalier wrote: On 7/12/07, Jonathan Cast [EMAIL PROTECTED] wrote: No. Of course not. Before making wild guesses about how GHC is implementing your code, read (and understand[1]) the STG paper: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gzpub=34 In this particular case, reading the simplifier paper would probably be more relevant: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/comp-by-trans.ps.gzpub=18 Or even just understanding the syntax of Core, really. [1] Understanding the STG paper is not a requirement to using Haskell, just to making wild (incorrect) guesses about how the compiler's going to treat your code. But, of course, making wild (incorrect) guesses about how the compiler's going to treat your code is not a requirement to using Haskell. Amen! Cheers, Tim I realize now that it was inappropriate to pose a question to this list before I knew the answer! :( Anyway, it turned out that the two ghc -ddump-simpl outputs were in fact identical, but only after identifier renaming. It would be very useful to have a tool that takes two core files and attempts to rename identifiers from the second to match the first. Is there already such a smart-diff tool out there? Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Looking for final year project - using Haskell, or another functional language
Building on what Hugh was getting at, beyond better opengl bindings, i'm curious: just what do you think is missing in haskell's opengl binding? just be sure to ignore http://www.haskell.org/HOpenGL/ , which should be moved to the wiki or to /dev/null. instead, look at the implementation, mailing list and and api docs (which need to be read side-by-side with the specs): http://darcs.haskell.org/packages/OpenGL http://www.haskell.org/mailman/listinfo/hopengl http://www.haskell.org/ghc/docs/latest/html/libraries/OpenGL/Graphics-Rendering-OpenGL-GL.html the mailing list has occasional progress info like this http://www.haskell.org/pipermail/hopengl/2006-November.txt Implement the entire opengl 1.3 interface specifications in Haskell. http://www.haskell.org/ghc/docs/latest/html/libraries/OpenGL/Graphics-Rendering-OpenGL-GL-BasicTypes.html This module corresponds to section 2.3 (GL Command Sytax) of the OpenGL 2.1 specs. claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
On Jul 12, 2007, at 17:11 , Andrew Coppin wrote: Felipe Almeida Lessa wrote: On 7/12/07, Andrew Coppin [EMAIL PROTECTED] wrote: How come the set of all sets doesn't exist? http://www.google.com/search?q=set+of+all+sets leads to http://en.wikipedia.org/wiki/Set_of_all_sets which has the answer, I think. Ouch. Clearly, set theory is way more complicated than people make out. (I always thought a set was just a collection of objects...) You might want to look over some of the introductory set theory stuff on the Good Math, Bad Math blog: http://scienceblogs.com/goodmath/ -- 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: Re[8]: [Haskell-cafe] Toy compression algorithms [was: A very edgy language]
G'day all. Quoting Bulat Ziganshin [EMAIL PROTECTED]: in this case why you proposes to encode lzw words with a huffman codes? :) I don't. :-) oops. ppm build tree of contexts and use context to encode one char. lzw builds dictionary of words and encode word in empty context. As you noted later, the dictionary of words in LZW is also tree- structured. Words, as you call them, are built by extending words with single characters, in pretty much exactly the same way that PPM contexts are built by extending contexts with single characters. The main difference is this: To encode a word in PPM, you encode the conditional probability that it takes to get to the end of the word from the start of the word. It looks like you're encoding single characters (and, programmatically, you are), but because of the way that arithmetic coding works, it's mathematically equivalent to encoding the probability of finding the word as a whole. You're just decomposing the probability of finding the word into the probabilities of finding the individual input symbols along the way. Does that make sense? you are right. so lzw is just dictionary-based transformation which replaces some words with special codes while ppm replaces chars with their probabilities. i hope you will agree that ppm with flat codes will be totally useless Absolutely. But augmenting LZW with probabilities to allow for arithmetic coding wouldn't be so dumb, if it weren't for the fact that a) we already have more efficient compression algorithms, and b) it'd destroy the main benefit of LZW (which is that it's effective on slow CPUs with small memories; perfect for 80s-era micros and 8-bit embedded systems). about which particular algorithm you said? Moffat? Yes, though if your local university library has a copy, Managing Gigabytes might be a better introduction to the topic. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[4]: [Haskell-cafe] In-place modification
I wrote [student code in Java twice the size of C code, 150 times slower]. On 12 Jul 2007, at 7:04 pm, Bulat Ziganshin wrote: using student's work, it's easy to proof that Basic is faster than assembler (and haskell is as fast and memory-efficient as C, citing haskell-cafe) This completely ignores everything else I wrote. The first point is that IT WAS NOT THE STUDENT'S FAULT. The performance bottleneck was ENTIRELY in code provided by Sun. And the second point of my message, which has also been ignored, is that languages are NOT the sole determiner of productivity c, but libraries also. My post was not about Java-the-language, but about java.io the library, and about the fact that libraries can have far more effect than anything the compiler does. So no, using the form of my argument, it is NOT possible to prove anything about Haskell -vs- C. It is ONLY possible to make claims about Haskell *libraries* -vs- C *libraries*. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
andrewcoppin: Ketil Malde wrote: On Wed, 2007-07-11 at 20:10 +0100, Andrew Coppin wrote: When I tell the editor to save UTF-8, it inserts some weird BOM character at the start of the file - and thus, any attempt at programatically processing that file instantly fails. :-( While BOMs (Byte Order Mark) are pretty irrelevant to byte-oriented encodings like UTF-8, I think programs that fail on their presence can be considered buggy. Yay! Haskell's text I/O system is buggy. :-P By the way Andrew, have you noticed that you're generating 50% of the traffic on this list? Perhaps we can work a bit more on improving the signal/noise ratio. My inbox can only take so much of this... ;) -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Functional dependencies *not* part of the next Haskell standard?
jules: peterv wrote: instance Vector Vector2 where dot (V2 x1 y1) (V2 x2 y2) = x1 * x2 + y1 * y2 Amazing, so simple it is, Yoda would say ;) I did not realize one could perform partial application on types when declaring instances (I mean not specifying the type of Vector2 in instance Vector Vector2). Now regarding these funcdeps, are they ill as the rumor goes? I don't think there is any danger of them being removed and not replaced. The functionality is useful. Associated Types is widely viewed as a successor/replacement, but no complete implementation exists yet: http://haskell.org/haskellwiki/GHC/Indexed_types I think the implementation is some 90% complete though, in GHC head. Certainly you can write many associated types programs already -- the missing part is finishing off associated type synonyms, iirc. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type system madness
On Jul 12, 2007, at 20:48 , Donald Bruce Stewart wrote: By the way Andrew, have you noticed that you're generating 50% of the traffic on this list? Perhaps we can work a bit more on improving the signal/noise ratio. My inbox can only take so much of this... ;) I can blather more, if you'd like (Hey, this mailing list is more interesting than 85% of the non-spam in my inbox :) -- 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] Looking for final year project - using Haskell, or another functional language
just be sure to ignore http://www.haskell.org/HOpenGL/ , which should be moved to the wiki or to /dev/null. sorry for the basic question: why is hopengl so bad? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Looking for final year project - using Haskell, or another functional language
On Fri, Jul 13, 2007 at 02:31:58AM +0100, wp wrote: just be sure to ignore http://www.haskell.org/HOpenGL/ , which should be moved to the wiki or to /dev/null. sorry for the basic question: why is hopengl so bad? HOpenGL, the library, isn't bad at all. It's the website that's absolutely horrible. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very freaky
Cale Gibbard wrote: On 10/07/07, Andrew Coppin [EMAIL PROTECTED] wrote: Stefan O'Rear wrote: Another good example: foo :: ∀ pred : Nat → Prop . (∀ n:Nat . pred n → pred (n + 1)) → pred 0 → ∀ n : Nat . pred n x_x Which you can read as For all statements about natural numbers, if the statement applies to 0, and if it applies to a number it applies to the next number, then it applies to all numbers.. IE, mathematical induction. ...and to think the idea of mathematical symbols is to make things *clearer*... As someone with a background in mathematics, I'd say that the idea of mathematical symbols is to make things more concise, and easier to manipulate mechanically. I'm not entirely certain that their intent is to make things clearer, though often they can make things more precise (which is a bit of a double edged sword when it comes to clarity). I quite often try to avoid symbols as much as possible, only switching to formulas when the argument I'm making is very mechanical or computational. After all, in most circumstances, the reader is going to have to translate the symbols back into concepts and images in their head, and usually natural language is a little farther along in that process, making things easier to read. I always have some beef with the common perception expressed in some of the above. I suppose I can speak concretely by listing again the three different presentations appearing above and comparing them. (A) ∀ pred : Nat → Prop . pred 0 → (∀ n:Nat . pred n → pred (n + 1)) → ∀ n : Nat . pred n (B) For all statements about natural numbers, ifthe statement applies to 0, and if it applies to a number it applies to the next number, then it applies to all numbers. (C) Mathematical induction I have re-formatted (A) and (B) to be fair, i.e., they both receive nice formatting, and both formatting are more or less equivalent, dispelling such myths as formal logic is unorganized or English is unorganized. I have formatted them to be equally well-organized. (C) is the clearest to those people who have already learned it and haven't lost it. I grant you that if you talk to a carefully selected audience, you just say (C) and leave it at that. But if you need to explain (C), saying (C) again just won't do. Most people claim (B) is clearer than (A) when it comes to explaining (C). One unfair factor at work is that most people have spent 10 years learning English; if they have also spent 10 years learning symbols, we would have a fairer comparison. Someone who know C but not Haskell is bound to say that C is clearer than Haskell; we who know both languages know better. (B) is less clear than (A) on several counts, and they are all caused by well-known unclarity problems in most natural languages such as English. if it applies to a number it applies to the next number is unclear about whether a number is quantified by ∀ or ∃. It could be fixed but I think I know why the author didn't and most people wouldn't. If we actually try to insert every or all somewhere there, the whole of (B) sounds strange. Part of the strangeness is due to the lack of scope delimiters: Later in (B) there is another all numbers coming up, and two all numbers too close to each other is confusing. You need scope delimiters to separate them. English provides just a handful of pronouns: I, we, you, he, she, it, they, this, that, these, those. The amount is further decimated when you make mathematical statements (pure or applied). Any statement that needs to refer to multiple subjects must run into juggle trouble. In (B), fortunately 95% of the time is spent around one single predicate, so you can just get by with it. You can't pull the same trick if you are to explain something else that brings up two predicates and three numbers. To this end, an unlimited supply of variables is a great invention from formal logic. (I am already using this invention by designating certain objects as (A), (B), (C) and thereby referring to them as such. There is no more tractible way.) Of course with the use of variables comes again the issue of scope delimiters. Actually even pronouns can be helped by scope delimiters. English badly lacks and needs scope delimiters. Quantifiers need them, variables need them, and here is one more: nested conditionals such as (B): if if X then Y then Z X implies Y implies Z are unparsible. Perhaps you can insert a few commas (as in (B)) or alternate between the if then form and the implies form to help just this case: if X implies Y then Z but it doesn't scale. It also proves to be fragile as we insert actual X, Y, Z: if it applies to a number implies it applies to the next number then it applies to all numbers Now, (B) is actually parsible, but that's only because I formatted it thoughtfully. Formatting is a form of scope delimiting, and that solves the problem. But
Re: [Haskell-cafe] Re: Defaulting to Rational [was: Number overflow]
On 13 Jul 2007, at 2:58 am, apfelmus wrote: What I wanted to do is to capture common patterns x - y = epsilon abs (x - y) = epsilon for comparing floating point numbers in nice functions x y = x - y = epsilon x ≈ y = abs (x - y) = epsilon See Knuth, The Art of Computer Programming, Volume 2, Semi-Numerical algorithms, for a suitable set of predicates and axioms they satisfy. However, they depend on epsilon (or APL's []CT, comparison tolerance). I once implemented the four predicates Knuth discussed in Quintus Prolog (library(fuzzy)). As far as I know, nobody ever used it. I had plans for making the code faster if anybody cared, but no-one did. I suspect these functions would be no more useful in Haskell: anyone who knew enough to use them would know enough not to. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
