Re: [Haskell-cafe] Haskell with all the safeties off
On Sep 7, 2012 2:00 AM, Edward Z. Yang ezyang ezy...@mit.edu@ezy...@mit.edu mit.edu ezy...@mit.edu wrote: Haskell already does this, to some extent, in the design of imprecise exceptions. But note that bottom *does* have well defined behavior, so these optimizations are not very desirable. They're not *usually* desirable, but when the code has been proven not to fall into bottom, there doesn't seem to be much point in ensuring that things will work right if it does. This sort of thing only really makes sense when using Haskell as a compiler target. Edward Excerpts from David Feuer's message of Thu Sep 06 19:35:43 -0400 2012: I have no plans to do such a thing anytime soon, but is there a way to tell GHC to allow nasal demons to fly if the program forces bottom? This mode of operation would seem to be a useful optimization when compiling a program produced by Coq or similar, enabling various transformations that can turn bottom into non-bottom, eliminating runtime checks in incomplete patterns, etc. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell with all the safeties off
I have no plans to do such a thing anytime soon, but is there a way to tell GHC to allow nasal demons to fly if the program forces bottom? This mode of operation would seem to be a useful optimization when compiling a program produced by Coq or similar, enabling various transformations that can turn bottom into non-bottom, eliminating runtime checks in incomplete patterns, etc. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] hstats median algorithm
I was thinking it should offer a randomized version (taking a generator), since randomized median algorithms provide the best expected performance. It could also offer a deterministic version using some variant of median-of-medians, intended for long lists. I guess it probably should retain the naive version for short lists. Some benchmarking would suggest a good cutoff. Has anyone come up with a better practical deterministic O(n) algorithm since median-of-medians? I saw a paper by Dorit Dor on reducing the number of comparisons to a bit under 3n, which also showed a lower bound of a bit over 2n, but the algorithm she gives strikes me as far too complex to be practical. On Sep 1, 2012 9:17 PM, Gershom Bazerman gersh...@gmail.com wrote: In my experience, doing much better than the naive algorithm for median is surprisingly hard, and involves a choice from a range of trade-offs. Did you have a particular better algorithm in mind? If you did, you could write it, and contact the package author with a patch. You also may be able to find something of use in Edward Kmett's order-statistics package: http://hackage.haskell.org/** package/order-statisticshttp://hackage.haskell.org/package/order-statistics Cheers, Gershom On 9/1/12 3:26 PM, David Feuer wrote: The median function in the hstats package uses a naive O(n log n) algorithm. Is there another package providing an O(n) option? If not, what would it take to get the package upgraded? __**_ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://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] hstats median algorithm
The median function in the hstats package uses a naive O(n log n) algorithm. Is there another package providing an O(n) option? If not, what would it take to get the package upgraded? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Platform Versioning Policy: upper bounds are not our friends
On Thu, Aug 16, 2012 at 9:53 AM, Felipe Almeida Lessa felipe.le...@gmail.com wrote: If you import qualified then adding functions will never break anything. If the language is changed (without possibility of breakage, I believe) so that names declared in a module shadow imported names, incompatibility can only arise if two different imports offer the same name, and it is actually used. David ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsing pragmas in a Haskell-like language
Where are pragmas treated like comments? On Aug 16, 2012 6:14 AM, Björn Peemöller b...@informatik.uni-kiel.de wrote: Dear cafe, I'm experimenting with extending the parser for a Haskell-like language by module pragmas. The parser is written using parser combinators. Currently, I adapted the lexer to ignore whitespace and comments, but create lexemes for both the pragma start and end (and the pragma's content, of course). While these lexemes are necessary for parsing the pragmas before the module header, they somehow should be ignored (treated like comments) afterwards. Could anyone give me a hint me how this behaviour (treat pragmas like comments) is achieved in GHC or in haskell-src-exts? Thanks in advance, Björn ___ 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] Data structure containing elements which are instances of the same type class
On Aug 15, 2012 3:21 AM, wren ng thornton w...@freegeek.org wrote: It's even easier than that. (forall a. P(a)) - Q = exists a. (P(a) - Q) Where P and Q are metatheoretic/schematic variables. This is just the usual thing about antecedents being in a negative position, and thus flipping as you move into/out of that position. Most of this conversation is going over my head. I can certainly see how exists a. (P(a)-Q) implies that (forall a. P(a))-Q. The opposite certainly doesn't hold in classical logic. What sort of logic are you folks working in? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data structure containing elements which are instances of the same type class
I understand this now, though I still don't understand the context. Thanks!
I managed to mix up implication with causation, to my great embarrassment.
On Aug 15, 2012 3:39 PM, Ryan Ingram ryani.s...@gmail.com wrote:
In classical logic A - B is the equivalent to ~A v B
(with ~ = not and v = or)
So
(forall a. P(a)) - Q
{implication = not-or}
~(forall a. P(a)) v Q
{forall a. X is equivalent to there does not exist a such that X doesn't
hold}
~(~exists a. ~P(a)) v Q
{double negation elimination}
(exists a. ~P(a)) v Q
{a is not free in Q}
exists a. (~P(a) v Q)
{implication = not-or}
exists a. (P(a) - Q)
These steps are all equivalencies, valid in both directions.
On Wed, Aug 15, 2012 at 9:32 AM, David Feuer david.fe...@gmail.comwrote:
On Aug 15, 2012 3:21 AM, wren ng thornton w...@freegeek.org wrote:
It's even easier than that.
(forall a. P(a)) - Q = exists a. (P(a) - Q)
Where P and Q are metatheoretic/schematic variables. This is just the
usual thing about antecedents being in a negative position, and thus
flipping as you move into/out of that position.
Most of this conversation is going over my head. I can certainly see how
exists a. (P(a)-Q) implies that (forall a. P(a))-Q. The opposite
certainly doesn't hold in classical logic. What sort of logic are you folks
working in?
___
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] createProcess running non-existent programs
In Unix, at least, check, then act is generally considered unwise: 1. Something can go wrong between checking and acting. 2. You might not be checking the right thing(s). In this case, the fact that the file exists is not useful if you don't have permission to execute it. You may not be able to determine whether you have the appropriate permissions without fairly deep manipulation of ACLs. 3. Even if the OS has the info at hand, making the system call(s) necessary to get it is not free. Various non-free things happen every time control passes between user-space and kernel-space. On Aug 13, 2012 4:17 AM, Andrew Cowie and...@operationaldynamics.com wrote: On Sun, 2012-08-12 at 23:18 -0700, Evan Laforge wrote: Yes, I ran into the same thing a while back. The problem is that the subprocess has already been forked off before it runs exec() and finds out the file doesn't exist. Given how astonishingly common it is to pass an invalid executable name and/or path, wouldn't it be worth doing a quick probe to see if the file exists before createProcess actually forks? [It's not like the effort the OS is going to do for the stat is going to be thrown away; whether that call pulls it up off of disk or the one after the fork that exec will do doesn't matter] AfC Sydney ___ 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] Data structure containing elements which are instances of the same type class
Has anyone used existential types to represent items on a schedule in a scheduled lazy data structure? On Aug 11, 2012 4:15 AM, o...@okmij.org wrote: data A = A deriving Show data B = B deriving Show data C = C deriving Show data Foo = forall a. Show a = MkFoo a (Int - Bool) instance Show Foo where show (MkFoo a f) = show a I'd like to point out that the only operation we can do on the first argument of MkFoo is to show to it. This is all we can ever do: we have no idea of its type but we know we can show it and get a String. Why not to apply show to start with (it won't be evaluated until required anyway)? Therefore, the data type Foo above is in all respects equivalent to data Foo = MkFoo String (Int - Bool) and no existentials are ever needed. The following article explains elimination of existentials in more detail, touching upon the original problem, of bringing different types into union. http://okmij.org/ftp/Computation/Existentials.html ___ 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] [Wadler 89] Philip Wadler. Theorems for free!: Can't get the same results in Haskell
It looks to me like Wadler made a typo. Even great minds like his slip up like that sometimes. However, I do have some comments below on your code. On Aug 9, 2012 8:53 PM, Stayvoid stayv...@gmail.com wrote: I tried to implement it in Haskell: (I'm a newbie. I guess it's possible to write a better version.) module Param where import Prelude The prelude is imported automatically. You only need to mention it as an import if you need to *avoid* importing some functions, or want some functions to be imported only qualified. This is done if you want to use a name that clashes with one in the prelude. You'll see things like import Prelude hiding (foldl',foldl, foldr) import Prelude qualified as P in a module implementing a data structure that supports folds. odds :: [Int] - [Int] odds [] = [] This is a very awkward approach. There's no reason to have a special case for the one-element list, and certainly no reason to use ++ to add a single element to the front of a list. You should do the work in the (x:xs) case instead: odds [] = [] odds (x:xs) | odd x = x : odds xs | otherwise = odds xs In fact, there's a function called filter that captures this pattern, so you can even write: odds = filter odd odds [x] = if odd x then [x] else [] odds (x:xs) = if odds [x] == [] then odds xs else [x] ++ odds xs inc :: [Int] - [Int] inc [] = error Empty list inc [x] = [succ x] inc (x:xs) = inc [x] ++ inc xs Again, this is bizarre. You should be writing: inc [] = [] inc (x:xs) = succ x : inc xs Again, there is a function that captures this pattern, so you can shorten it to inc = map succ Looks fine: *Param odds [1,2,3] [1,3] *Param inc [1,2,3] [2,3,4] But my results differ from the paper's: *Param inc (odds [1,2,3]) [2,4] *Param odds (inc [1,2,3]) [3] I doubt that there is an error in the paper. I don't. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fwd: 'let' keyword optional in do notation?
-- Forwarded message -- From: David Feuer david.fe...@gmail.com Date: Wed, Aug 8, 2012 at 12:22 PM Subject: Re: [Haskell-cafe] 'let' keyword optional in do notation? To: Martijn Schrage mart...@oblomov.com Changing scoping rules based on whether things are right next to each other? No thanks. On Wed, Aug 8, 2012 at 11:44 AM, Martijn Schrage mart...@oblomov.com wrote: On 08-08-12 17:27, Ertugrul Söylemez wrote: Vo Minh Thu not...@gmail.com wrote: This is not a parsing problem, but a scoping one: try to run this program: main = do let x = y y = 5 let a = b let b = 6 print (x, y, a, b) Cheers, Thu Martijn has actually covered this question: Where each sequence of let-less bindings is put in a separate binding group. I'm no parsing wizard, but I couldn't come up with any situations in which this would cause ambiguity. To me, the let-less version is easier on the eyes, more consistent with - bindings, and also makes it less of a hassle to move stuff around. To make it more clear, this is the transformation I propose: do ...-- not a let-less binding x1 = exp1 -- \ .. -- only let-less bindings xn = expn -- / ...-- not a let-less binding becomes do ... let x1 = exp1 .. xn = expn ... So main = do x = y y = 5 a = b b = 6 print (x, y, a, b) would put everything in the same binding group and compile successfully. To get Thu's example, you would write main = do x = y y = 5 let a = b let b = 6 print (x, y, a, b) The last let could even be left out. Cheers, Martijn The suggestion seems sound to me, and the additional 'let' can really be annoying in cases where you have a lot of 'let' bindings among very few monadic actions. My current way to deal with this is to move the stuff to separate computations, but it's certainly not a nice solution: myComp = c = f where f x = ... where a = ... b = ... Greets Ertugrul ___ 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
Re: [Haskell-cafe] Fwd: 'let' keyword optional in do notation?
Is it really so bad to use an explicit let when you need mutually recursive bindings? On Aug 8, 2012 1:51 PM, Martijn Schrage mart...@oblomov.com wrote: On 08-08-12 19:01, Simon Hengel wrote: On Wed, Aug 08, 2012 at 12:22:39PM -0400, David Feuer wrote: Changing scoping rules based on whether things are right next to each other? No thanks. Would expanding each let-less binding to a separate let feel more sound to you? That was actually my first idea, but then two declarations at the same level will not be in the same binding group, so do x = y y = 1 would not compile. This would create a difference with all the other places where bindings may appear. However, having scope depend on things being next to each other (or rather, not having anything in between) is not new. Template Haskell declaration splices already cause separate binding groups for top-level declarations. Moreover, the new scope rule only holds for let-less bindings. If you use explicit lets nothing changes. -- Martijn ___ 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] mutable arrays of tuples
So I was thinking about a mutable array of tuples, but to avoid allocating tuples to modify their fields, I guess I really want an immutable array of tuples of STRefs. Just how much less efficient is this than a plain mutable array? might it even make sense to use parallel mutable arrays? The thought of that is disgusting to me, but at least one of the arrays could likely be made unboxed... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sorting efficiency
Unfortunately, I doubt it can. That algorithm reduces the number of
comparisons a good bit, but the asymptotic complexity of its other
operations remains the same, with apparently bad constant factors
(according to the article). Also, that article describes the algorithm
in terms of sorting [a+b| a-A, b-A], whereas I'm actually dealing
(in the more substantial phase) with [a+b | a-A, b-B], where B is
much larger than A. Using the merging approach I described in my last
email, I can reduce the complexity from mn log(mn) in the naive
algorithm to mn log (min {m,n}). Since m=100 and n~=10,000, I should
be able to get nearly double the speed of the naive approach, as long
as my multi-merge is fast enough.
On Sun, Aug 5, 2012 at 3:59 AM, Heinrich Hördegen
hoerde...@funktional.info wrote:
Hi David,
can this help you?
http://www.scribd.com/doc/81029312/5/Sorting-pairwise-sums
Heinrich
Am 04.08.2012 20:47, schrieb David Feuer:
I realized my algorithm is insane. The correct way to sort [a*b|a-A,
b-B] is clearly to sort A and B, then for each a in A construct
either map (a*) B or map (a*) (reverse B), depending on the sign of a,
then merge all these results together with a merge that collapses
duplicates. I was multiplying and then sorting, which is way worse.
The same (modulo sign) goes for adding lists.
On Aug 4, 2012 1:55 PM, Clark Gaebel cgae...@uwaterloo.ca [6]
wrote:
Its generally not advisable to use Data.List for
performance-sensitive parts of an application.
Try using Data.Vector instead:
http://hackage.haskell.org/package/vector [4]
On Sat, Aug 4, 2012 at 11:23 AM, David Feuer david.fe...@gmail.com
[5] wrote:
Im writing a toy program (for a SPOJ problem--see
https://www.spoj.pl/problems/ABCDEF/ [1] ) and the profiler says
my
performance problem is that Im spending too much time sorting. Im
using Data.List.sort on [Int32] (its a 32-bit architecture).
Others,
using other languages, have managed to solve the problem within
the
time limit using the same approach Ive taken (I believe), but
mine is
taking too long. Any suggestions? Do I need to do something
insane
like sorting in an STUArray?
David Feuer
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org [2]
http://www.haskell.org/mailman/listinfo/haskell-cafe [3]
Links:
--
[1] https://www.spoj.pl/problems/ABCDEF/
[2] mailto:Haskell-Cafe@haskell.org
[3] http://www.haskell.org/mailman/listinfo/haskell-cafe
[4] http://hackage.haskell.org/package/vector
[5] mailto:david.fe...@gmail.com
[6] mailto:cgae...@uwaterloo.ca
___
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] Sorting efficiency
Where by nearly double, of course, I really mean nearly triple.
I'm a little tired.
David
On Sun, Aug 5, 2012 at 5:37 AM, David Feuer david.fe...@gmail.com wrote:
Unfortunately, I doubt it can. That algorithm reduces the number of
comparisons a good bit, but the asymptotic complexity of its other
operations remains the same, with apparently bad constant factors
(according to the article). Also, that article describes the algorithm
in terms of sorting [a+b| a-A, b-A], whereas I'm actually dealing
(in the more substantial phase) with [a+b | a-A, b-B], where B is
much larger than A. Using the merging approach I described in my last
email, I can reduce the complexity from mn log(mn) in the naive
algorithm to mn log (min {m,n}). Since m=100 and n~=10,000, I should
be able to get nearly double the speed of the naive approach, as long
as my multi-merge is fast enough.
On Sun, Aug 5, 2012 at 3:59 AM, Heinrich Hördegen
hoerde...@funktional.info wrote:
Hi David,
can this help you?
http://www.scribd.com/doc/81029312/5/Sorting-pairwise-sums
Heinrich
Am 04.08.2012 20:47, schrieb David Feuer:
I realized my algorithm is insane. The correct way to sort [a*b|a-A,
b-B] is clearly to sort A and B, then for each a in A construct
either map (a*) B or map (a*) (reverse B), depending on the sign of a,
then merge all these results together with a merge that collapses
duplicates. I was multiplying and then sorting, which is way worse.
The same (modulo sign) goes for adding lists.
On Aug 4, 2012 1:55 PM, Clark Gaebel cgae...@uwaterloo.ca [6]
wrote:
Its generally not advisable to use Data.List for
performance-sensitive parts of an application.
Try using Data.Vector instead:
http://hackage.haskell.org/package/vector [4]
On Sat, Aug 4, 2012 at 11:23 AM, David Feuer david.fe...@gmail.com
[5] wrote:
Im writing a toy program (for a SPOJ problem--see
https://www.spoj.pl/problems/ABCDEF/ [1] ) and the profiler says
my
performance problem is that Im spending too much time sorting. Im
using Data.List.sort on [Int32] (its a 32-bit architecture).
Others,
using other languages, have managed to solve the problem within
the
time limit using the same approach Ive taken (I believe), but
mine is
taking too long. Any suggestions? Do I need to do something
insane
like sorting in an STUArray?
David Feuer
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org [2]
http://www.haskell.org/mailman/listinfo/haskell-cafe [3]
Links:
--
[1] https://www.spoj.pl/problems/ABCDEF/
[2] mailto:Haskell-Cafe@haskell.org
[3] http://www.haskell.org/mailman/listinfo/haskell-cafe
[4] http://hackage.haskell.org/package/vector
[5] mailto:david.fe...@gmail.com
[6] mailto:cgae...@uwaterloo.ca
___
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] Sorting efficiency
I'm writing a toy program (for a SPOJ problem--see https://www.spoj.pl/problems/ABCDEF/ ) and the profiler says my performance problem is that I'm spending too much time sorting. I'm using Data.List.sort on [Int32] (it's a 32-bit architecture). Others, using other languages, have managed to solve the problem within the time limit using the same approach I've taken (I believe), but mine is taking too long. Any suggestions? Do I need to do something insane like sorting in an STUArray? David Feuer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Sorting efficiency
I realized my algorithm is insane. The correct way to sort [a*b|a-A, b-B] is clearly to sort A and B, then for each a in A construct either map (a*) B or map (a*) (reverse B), depending on the sign of a, then merge all these results together with a merge that collapses duplicates. I was multiplying and then sorting, which is way worse. The same (modulo sign) goes for adding lists. On Aug 4, 2012 1:55 PM, Clark Gaebel cgae...@uwaterloo.ca wrote: It's generally not advisable to use Data.List for performance-sensitive parts of an application. Try using Data.Vector instead: http://hackage.haskell.org/package/vector On Sat, Aug 4, 2012 at 11:23 AM, David Feuer david.fe...@gmail.comwrote: I'm writing a toy program (for a SPOJ problem--see https://www.spoj.pl/problems/ABCDEF/ ) and the profiler says my performance problem is that I'm spending too much time sorting. I'm using Data.List.sort on [Int32] (it's a 32-bit architecture). Others, using other languages, have managed to solve the problem within the time limit using the same approach I've taken (I believe), but mine is taking too long. Any suggestions? Do I need to do something insane like sorting in an STUArray? David Feuer ___ 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: Constructing Cases
Use an array. Don't remember for sure, but I think something like q = array (0, max (map fst list)) list f = (q!!) will probably work. On Fri, May 24, 2002, Carl McTague wrote: Hi there, is there a simple way to carry out the following type of conversion? Suppose I have a list (finite) of (value,image) pairs such as: list = [(0,1),(1,0)] From this I want to generate a function f 0 = 1 f 1 = 0 Is there a way to do this? Note, I don't want to define a function that searches through the list each time it is invoked, I want to generate the function once and have it be as fast as the pattern-matcher can make it. So, I'm looking for a function g :: [(a,b)] - a - b Is this simple to do? Thanks, Carl ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- Night. An owl flies o'er rooftops. The moon sheds its soft light upon the trees. David Feuer ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: composeList
On Sun, May 12, 2002, Emre Tezel wrote: Hi all, I recently bought Simon Thompson's Haskell book. I have been doing the exercises while I read on. There are couple questions that I can not solve. Any help would be greatly appreciated. I got stuck on this question in Chapter 10. Define a function composeList which composes a list of functions into a single function. What is the type of composeList? I naively tried the following but the hugs compiler complained about the inferred type not being generic enough. composeList :: [(a - b)] - (c - b) composeList [] = id composeList (x:xs) = x . (composeList xs) The type signature is wrong. It indicates that for any a,b,c, and d, composeList takes a list of (a-b) and produces a (c-b). So for example, that would mean that if I gave it [(+3), (*4), (-5)] it would be able to produce something of type (Maybe String - Int). This is of course totally wrong. You're going to have to restrict it some more . The first thing to note is that a=c: if you give it a list of functions that take Floats, it's going to give back a function that takes a float. So that restricts it to [a - b] - (a - b). Now look at the function itself: composeList (x:xs) = x . (composeList xs) Now in order for f . g to make any sense, f must take values of the type that g returns! So if x has type p - q, (composeList xs) must have type r - p. But since x is in xs, xs must have type [p - q], so (composeList xs) has type p - q. So r - p = p - q. This implies immediately that p = q = r. So the type of composeList is restricted all the way down to [a - a] - (a - a). This can also be written [a - a] - a - a. This may seem disappointing, but it is made necessary by the type safety of Haskell, which requires that all the elements of a list have the same type. You can do a lot better in Glasgow Haskell: data Fun a b = forall c . Comp (c - b) (Fun a c) | End (a - b) compose :: Fun a b - a - b --GHC needs this type signature --to compile the program, but --I don't understand why. --Any tips? compose (End f) = f compose (Comp f l) = f . compose l f::Int - Float f x = fromIntegral x g::String - Int g = read h::Int - String h x = take x 123456789 main = do putStrLn hello! print $ compose (End (\x - Foo!)) 3 print $ compose (Comp f (Comp g (End h))) 4 -- Night. An owl flies o'er rooftops. The moon sheds its soft light upon the trees. David Feuer ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: composeList
See comments below. On Sun, May 12, 2002, David Feuer wrote: On Sun, May 12, 2002, Emre Tezel wrote: Hi all, I recently bought Simon Thompson's Haskell book. I have been doing the exercises while I read on. There are couple questions that I can not solve. Any help would be greatly appreciated. I got stuck on this question in Chapter 10. Define a function composeList which composes a list of functions into a single function. What is the type of composeList? I naively tried the following but the hugs compiler complained about the inferred type not being generic enough. composeList :: [(a - b)] - (c - b) composeList [] = id composeList (x:xs) = x . (composeList xs) snip You can do a lot better in Glasgow Haskell: data Fun a b = forall c . Comp (c - b) (Fun a c) | End (a - b) compose :: Fun a b - a - b --GHC needs this type signature --to compile the program, but --I don't understand why. --Any tips? compose (End f) = f compose (Comp f l) = f . compose l Well, I figured out why the type signature is necessary (polymorphic recursion), but I don't understand the error message I got from GHC: cc.hs:5: Inferred type is less polymorphic than expected Quantified type variable `c' escapes When checking a pattern that binds f :: c - b l :: Fun a c In the definition of `compose': compose (Comp f l) = f . (compose l) What makes it think that `c' escapes? This message had me staring at the code the wrong way for quite a while before I decided to add a type signature and see if that gave me any more useful information. f::Int - Float f x = fromIntegral x g::String - Int g = read h::Int - String h x = take x 123456789 main = do putStrLn hello! print $ compose (End (\x - Foo!)) 3 print $ compose (Comp f (Comp g (End h))) 4 -- Night. An owl flies o'er rooftops. The moon sheds its soft light upon the trees. David Feuer ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: if (++) were left associative ?
On Sun, Apr 07, 2002, Konst Sushenko wrote: Hello, this is probably embarrassing, but I just realised that I do not understand why list concatenation operation takes quadratic time if it is associated from left to right (see e.g. 'The Haskell School of Expression' by Hudak, p. 335): cat1 = (++) cat2 = (++) ( [1,2] `cat1` [3,4] ) `cat2` [5,6] My understanding is that cat2 is invoked before cat1, and as soon as the first element of cat1 is available, cat2 starts building its own result. cat2 does not need to wait until the whole list is emitted by cat1, does it? Where is quadratic time complexity? Suppose we define listseq [] x = x listseq (a:b) x = listseq b x l = [1..n] inter = foldl (++) [] (map (:[]) foo) final = listseq inter inter Then inter will be the result of concatenating [1],[2],[3],... from left to right. One meaningful question is: how long will it take to calculate final? This is (I believe) called the _shared cost_ of inter (while inter does not actually do any significant work, it produces a chain of suspensions that together do quite a bit I'm not sure if the way they are chained still allows this to be considered the shared cost, but I'm not sure). 1. How long does it take to calculate final ? Well, let's try it for n = 4: inter = foldl (++) [] [[1],[2],[3],[4]] = foldl (++) ([]++[1]) [[2],[3],[4]] = foldl (++) [1] [[2],[3],[4]] = foldl (++) ([1]++[2]) [[3],[4]] = foldl (++) [1,2] [[3],[4]] = foldl (++) ([1,2]++[3]) [[4]] = foldl (++) [1,2,3] [[4]] = foldl (++) ([1,2,3]++[4]) [] = foldl (++) [1,2,3,4] [] = [1,2,3,4] Note that in successive iterations, the following are calculated: []++[1] [1]++[2] [1,2]++[3] [1,2,3]++[4] Since l1++l2 takes order length(l1), each concatenation takes more time than the previous one (linearly), so the total time for all of them is quadratic. David Feuer ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Date Sorting...
On Fri, Mar 08, 2002, Ketil Z. Malde wrote: I don't think it's either functional nor imperative by itself. The question is how you structure it, do you say something like buffer x list y x = readFile ... y = parse x quickSort y print y (which would be imperative), or do you say something like print (quickSort (parse (readFile ...))) Unfortunately, this is wrong. You'd have to do something more like readFile ... = print . sort . parse which would be functional. Note that the only really imperative part is the sorting, which actually changes the content of y for the following part of the program. A functional implementation wouldn't destroy y, but create a new list with the elements from y in sorted order. yah. I'm not sure if that made things clearer :-) (If you really want to implement it, look at the Prelude for some help, some of the things you wish to do is pretty standard fare. And sorting is perhaps made easier if you rearrange the list of dates a bit?) Sorting is probably easiest if you use the standard sort function. I'm still kind of interested in whether anyone has done work on which purely-functional sorts are efficient, and particularly which ones are efficient in GHC. David Feuer ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Graphs
On Sat, Feb 23, 2002, Jan-Willem Maessen wrote: David Feuer [EMAIL PROTECTED] writes: I seem to remember an article about functional graph algorithms using extra-lazy arrays. Anyone know if these arrays have appeared in any mainstream implementation? I assume you're referring to this paper by Thomas Johnsson: Yes indeed. Thank you. David Feuer ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Graphs
I seem to remember an article about functional graph algorithms using extra-lazy arrays. Anyone know if these arrays have appeared in any mainstream implementation? David Feuer ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: syntax...(strings/interpolation/here docs)
From: Joe [EMAIL PROTECTED] Does anybody with their elbows in the code think variable interpolation and/or multi-line strings are good/doable ideas? Can't say I have my elbows in the code, but I think that multi-line strings could be useful. I'm not sure what I think about variable interpolation... I imagine it would make the language somewhat more difficult to parse. What would this be like, anyway? Something like foo $(bar) baz = foo++bar++baz ? And then you'd have to have some sort of quoting rule, for dollar signs followed by parens... I guess you'd probably want some variant that automatically applies show... Would this be the sort of change one could make without a lot of previous familiarity with the implementation of Hugs/Ghc? You'd certainly need to be familiar with how to specify syntax, and how to write a parser. It would be a *signifigant* boon to those of us trying to get haskell into organizations by using it as maintainable perl/sh, and Haskell is not a maintainable perl/sh. It is not a good language for simple shell scripts, and is not good for string processing either. Have you tried Scsh? Or Python? I don't think that supporting string hacking is a major goal for Haskell. generally make an already delightful language more delightful. This message has been brought to you by the letter alpha and the number pi. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
unification
Has anyone written an efficient purely-functional implementation of unification (for type checking)? If not, what makes it difficult to solve the problem in that way? David Feuer This message has been brought to you by the letter alpha and the number pi. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Q about haskell-report
From: Cagdas Ozgenc [EMAIL PROTECTED] Greetings. In section 4.1 of Haskell Report for 98: It is indicated that (-) has kind * - *- * and t1 - t2 is equivalent to type (-) t1 t2 Does this make (-) a type constructor? Is this an attempt to unify functions and data types? (-) is indeed a type constructor. I was as surprised as you were when I discovered today that it is even possible to make (-) an instance of a class (e.g., Arrow). I can't really answer your last question. This message has been brought to you by the letter alpha and the number pi. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: unification
From: Thomas Hallgren [EMAIL PROTECTED] David Feuer wrote: Has anyone written an efficient purely-functional implementation of unification (for type checking)? Well, if you have ever used hbc or nhc, you have used type checkers containing purely functional implementations of unification. Purely functional unification can be efficient enough for practical purposes... Thank you for this information. However, it does not quite satisfy my curiosity: are these purely functional type checkers as efficient (big-O) as imperative ones? And if not, why not? David Feuer This message has been brought to you by the letter alpha and the number pi. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
more parsing paper
The paper I am reading uses the following in an instance declaration for parsers: p = f = Parser (\cs - concat [parse (f a) cs' | (a,cs') - parse p cs]) Isn't this the same as p = f = Parser (\cs - [(a',cs'') | (a,cs') - parse p cs, (a',cs'') - parse (f a) cs']) ? If so, any guesses why they chose the more obscure form? ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
modules, classes, instances
Well, I've been doing some more stupid thinking, and I've decided that I
am not satisfied with the module system in haskell, or the way it deals
with namespaces. It seems to me that there are four kinds of things
that need to be dealt with: classes, instances, types, values, and
possibly some kind of ML-style structures/functors.
I see no good reason not to treat a class declaration similarly to the
way Haskell treats modules. For example, if I have a class
class A x where
f1::...
f2::...
I would like to access the functions by writing
A.f1, A.f2, etc. There should, however, be some way to unqualify the
names, the way ML allows structures to be opened.
Of course, this can be done in Haskell by putting the class declaration
inside a module, but doing so can be annoying, and I think this style
clearly attaches the method to the class it belongs to. It thereby lets
you have a List l=List.empty::l and also a Bag b=Bag.empty::b
automatically.
Then there are types and instance declarations. I have the strange
feeling that they go together. So I'm thinking it might be good to have
some kind of type/instance module that can export types and instances.
I can't understand why it is that instance declarations can't contain
nested declarations other than the required ones. I think it would be
nice if they could contain other declarations, as modules can. Also,
instances could be imported (not just as part of a module, but
separately)
ML-style structures/functors. For everything else.
Finally: I want nested modules!!! They probably couldn't be compiled
separately, but they'd provide some namespace control.
--
/Times-Bold 40 selectfont/n{moveto}def/m{gsave true charpath clip 72
400 n 300 -4 1{dup 160 300 3 -1 roll 0 360 arc 300 div 1 1 sethsbcolor
fill}for grestore 0 -60 rmoveto}def 72 500 n(This message has been)m
(brought to you by the)m(letter alpha and the number pi.)m(David Feuer)
m([EMAIL PROTECTED])m showpage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: (no subject)
uma kompella wrote:
hi
i am new to haskell and am having a problem to write
function which takes a boolean expression and returns
a truthvalue stating whether or not it is a tautology.
Can anyone please help me??
Thanks a lot
uma
I assume this is your homework. It is better to say so explicitly.
Think about this: what does it mean for an expression to be a
tautology? Can you think of an a way to check this? Once you've come
up with a way to check this, it should be quite easy to write it in
Haskell.
--
/Times-Bold 40 selectfont/n{moveto}def/m{gsave true charpath clip 72
400 n 300 -4 1{dup 160 300 3 -1 roll 0 360 arc 300 div 1 1 sethsbcolor
fill}for grestore 0 -60 rmoveto}def 72 500 n(This message has been)m
(brought to you by the)m(letter alpha and the number pi.)m(David Feuer)
m([EMAIL PROTECTED])m showpage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: instance declarations
Marcin 'Qrczak' Kowalczyk wrote:
There is another problem: even if we created a syntax to name them,
if they would not be exported by default then current programs would
have to be changed.
Well, the default could be to export, unless explicitly hidden. If it
_is_ exported, you could have the option to write it explicitly, or just
have it go by default.
Perhaps in the future it will be possible to specify the interface
of a Haskell module more formally, with types of exported values
for example. Then we should remember about instances and solve both
problems simultaneously.
I guess that may be true... It could be really useful to have a tool to
take a source file and automagically make an approximate header for
it...
--
/Times-Bold 40 selectfont/n{moveto}def/m{gsave true charpath clip 72
400 n 300 -4 1{dup 160 300 3 -1 roll 0 360 arc 300 div 1 1 sethsbcolor
fill}for grestore 0 -60 rmoveto}def 72 500 n(This message has been)m
(brought to you by the)m(letter alpha and the number pi.)m(David Feuer)
m([EMAIL PROTECTED])m showpage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: instance declarations
(sorry to mess up mail threading, but I couldn't properly reply to the message the way I'm using email right now--broken mail clients) Recently, however, there has been some interest in using named instance declarations in other ways, so perhaps we will see features like this creeping into future versions of the language. In what kinds of ways? Sounds interesting. [Of course, there is a way of naming instance declarations with the current Haskell syntax, although it is a little verbose, and would require more work on the implementers part than simple matching of strings. The syntax I'm thinking of would look something like the following: module M(C(..), instance C Int, instance C a = C [a]) where ... This is the sort of thing I was thinking too. But I would probably want to extend that to classes and types. For instance module M (class Eq a=C a (...), type A, instance C A, instance C a = C [a]) where ... If I am not mistaken, this would allow separation of the type namespace from the typeclass namespace, and would make it obvious whether the thing being exported is a type or a class. It could also potentially allow the context(s) for class and instance declarations to be more restrictive in the header or in imports than in the module body. The latter could perhaps allow resolution of overlapping instances at import time, by restricting the instances to the point of non-overlap. I'm not sure that the former would actually be useful. Hmmm speaking of overlapping instances... Would there be a practical way to add negation (of classes and possibly even types) to the context syntax? This would let you say instance (Integral a) = C (T a) where ... instance (not Integral a, Real a) = C (T a) where ... instance (not Num a) = C (T a) where ... It would also seem nice to be able to say instance (Integral a, not a Int) = C a where and instance C Int where . but this seems even more questionable. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
cond and match
I'm wondering why Haskell doesn't support Scheme-like cond statements or a pattern matching predicate. cond c1-v1 c2-v2 or possibly cond | c1 - v1 | c2 - v2 ... would translate as case () of _ | c1 - v1 | c2 - v2 | also, it seems that a match predicate could occasionally be useful match p v would mean case v of p - True _ - False ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
