Re: ANNOUNCE: GHC version 6.10.1 - MacOS installer
Jason Dagit: On Wed, Nov 5, 2008 at 5:36 PM, Manuel M T Chakravarty [EMAIL PROTECTED] wrote: Ian Lynagh: On Tue, Nov 04, 2008 at 09:02:12PM -0500, Brandon S. Allbery KF8NH wrote: On 2008 Nov 4, at 20:26, Jason Dagit wrote: On Tue, Nov 4, 2008 at 4:26 PM, Manuel M T Chakravarty [EMAIL PROTECTED] wrote: Are you sure it does deinstall the 6.8 compiler? After installing 6.10, there should be a 608/ and a 610/ directory. This certainly happens on my Mac and I am not aware of an option to change that behaviour. I expect if you used the OSX installer then /Library/Receipts is screwing you (it wipes the old files listed in the .bom file). Try finding and removing the receipt directory and bom file before installing. The only file I can see that looks relevant is /Library/Receipts/boms/ org.haskell.glasgowHaskellCompiler.ghc.pkg.bom Wouldn't removing it make uninstall impossible? In fact, if you did manage to get 2 versions installed, how would /Library/Frameworks/GHC.framework/Tools/Uninstaller know which version to uninstall? Wouldn't it only know how to uninstall the version it came with? I'd suggest that the overlapping file Uninstaller could be why the older version gets removed, but that wouldn't explain why Manuel can install both at once. A current limitation of the MacOS package system is that it does not support uninstalling of packages; cf http://developer.apple.com/documentation/DeveloperTools/Conceptual/SoftwareDistribution/Managed_Installs/chapter_5_section_7.html#/ /apple_ref/doc/uid/1145i-CH6-DontLinkElementID_29 This is not a big drama on MacOS, as MacOS encourages the distribution of software packages as bundles: http://developer.apple.com/documentation/CoreFoundation/Conceptual/CFBundles/CFBundles.html This essentially means that instead of sprinkling files all over the file system (as is common in other OSes), MacOS applications and frameworks (Mac-speak for libraries) are kept in a single directory. Uninstalling then means doing an rm -rf on that directory. Unfortunately, some applications (including GHC and Apple's Xcode IDE) can't be entirely contained in a single directory. In the case of GHC, we want symlinks in /usr/bin. The established way of uninstalling such applications is by supplying an Uninstaller script, just as I did for GHC. (Apple does the same for Xcode.) The purpose of the Uninstaller script is too completely remove GHC.framework from a machine - not just to remove one version. In fact, if more than one version of GHC is installed, the Uninstaller will refuse to run and require the manual removal of all versions, but the current (easily achieved by a rm -rf /Library/Frameworks/ GHC.framework/Versions/version). The main feature of the Uninstaller script is to get rid of all symlinks pointing into GHC.framework. The framework itself is just deleted by a rm -rf as expected. (It also removes the above mentioned receipt file.) So, to directly answer the above questions: * The package manger (which uses the receipts) can't uninstall and the uninstaller script doesn't need the receipt. So, even after deleteing the receibt, you can still uninstall. * The Uninstaller can uninstall any version (at least as long as no symlinks are put into new directories outside of the bundle that the Uninstaller doesn't know about). Is there an update on this thread? I would still like to have my cake and eat it too, meaning ghc 6.8.3 and ghc 6.10.1. As far as I know the installer hasn't been updated and if I try again I will lose my copy of 6.8.3. Sorry, but for the moment, my (rather limited knowledge) of the MacOS packaging system is exhausted, and currently I don't have the time to search the web or experiment to try to learn more. It would be helpful to have the input of somebody who has more experience with MacOS packages. Manuel___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
language features in 6.10.1
The GHC team writes The (Interactive) Glasgow Haskell Compiler -- version 6.10.1 [..] There have been a number of significant changes since the last major release, including: * Some new language features have been implemented: * Record syntax: wild-card patterns, punning, and field disambiguation * Generalised quasi-quotes * Generalised list comprehensions * View patterns [..] Please, where and in what chapters these 4 language features are documented? Thank you in advance for help, - Serge Mechveliani [EMAIL PROTECTED] ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: language features in 6.10.1
Serge D. Mechveliani wrote: The GHC team writes The (Interactive) Glasgow Haskell Compiler -- version 6.10.1 [..] There have been a number of significant changes since the last major release, including: * Some new language features have been implemented: * Record syntax: wild-card patterns, punning, and field disambiguation * Generalised quasi-quotes * Generalised list comprehensions * View patterns [..] Please, where and in what chapters these 4 language features are documented? Thank you in advance for help, Direct links to the docs are in the release notes: http://www.haskell.org/ghc/docs/latest/html/users_guide/release-6-10-1.html Cheers, Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unicode's greek lambda
Hi, Perhaps it would be possible to convince your text editor to display '\' as, let's say, bold lambda? Of course it would need to know which '\' mean lambdas. Best, Michał On Tue, 2008-11-18 at 18:00 +0900, Kazu Yamamoto wrote: Hello, When the -XUnicodeSyntax option is specified, GHC accepts some Unicode characters including left/right arrows. Unfortunately, the letter greek lambda cannot be used. Are there any technical reasons to not accept it? Regards, --Kazu ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unicode's greek lambda
Duncan Coutts wrote: On Tue, 2008-11-18 at 11:51 +, Ross Paterson wrote: On Tue, Nov 18, 2008 at 10:30:01AM +, Malcolm Wallace wrote: When the -XUnicodeSyntax option is specified, GHC accepts some Unicode characters including left/right arrows. Unfortunately, the letter greek lambda cannot be used. Are there any technical reasons to not accept it? The greek lambda is a normal lower-case alphabetic character - it can be used in identifier names. But it could be a reserved word synonymous with \. After all, \ can occur in operator symbols, but the operator \ is reserved. Presumably that would let you do (\ x - ...) but not (\x - ) since the \x would run together and lexically it would be one identifier. Exactly. Here's the relevant patch: Tue Jan 16 16:11:00 GMT 2007 Simon Marlow [EMAIL PROTECTED] * Remove special lambda unicode character, it didn't work anyway Since lambda is a lower-case letter, it's debatable whether we want to steal it to mean lambda in Haskell source. However if we did, then we would probably want to make it a special symbol, not just a reserved symbol, otherwise writing \x-... (using unicode characters of course) wouldn't work, because \x would be treated as a single identifier, you'd need a space. Cheers, Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unicode's greek lambda
On Wed, 19 Nov 2008, Simon Marlow wrote: Tue Jan 16 16:11:00 GMT 2007 Simon Marlow [EMAIL PROTECTED] * Remove special lambda unicode character, it didn't work anyway Since lambda is a lower-case letter, it's debatable whether we want to steal it to mean lambda in Haskell source. However if we did, then we would probably want to make it a special symbol, not just a reserved symbol, otherwise writing \x-... (using unicode characters of course) wouldn't work, because \x would be treated as a single identifier, you'd need a space. There are a number of mathematical lambdas in Unicode (distinct from teh Greek lambdas), but they are not in the basic multilingual plane and they are presumably not very easy to type :-) Tony. -- f.anthony.n.finch [EMAIL PROTECTED] http://dotat.at/ VIKING NORTH UTSIRE SOUTH UTSIRE: NORTHWESTERLY 6 TO GALE 8, OCCASIONALLY SEVERE GALE 9 IN VIKING AND SOUTH UTSIRE. VERY ROUGH, OCCASIONALLY HIGH. RAIN THEN SHOWERS, WINTRY LATER IN VIKING AND NORTH UTSIRE. MODERATE OR GOOD, OCCASIONALLY POOR. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: cross module optimization issues
| I'm compiling with -O2 -Wall. After looking at the Core output, I | think I've found the key difference. A function that is bound in a | where statement is different between the monolithic and split | sources. I have no idea why, though. I'll experiment with a few | different things to see if I can get this resolved. In general, splitting code across modules should not make programs less efficient -- as Don says, GHC does quite aggressive cross-module inlining. There is one exception, though. If a non-exported non-recursive function is called exactly once, then it is inlined *regardless of size*, because doing so does not cause code duplication. But if it's exported and is large, then its inlining is not exposed -- and even if it were it might not be inlined, because doing so duplicates its code an unknown number of times. You can change the threshold for (a) exposing and (b) using an inlining, with flags -funfolding-creation-threshold and -funfolding-use-threshold respectively. If you find there's something else going on then I'm all ears. Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
GHC 6.10.1 type puzzler
Here is an example illustrating a type problem I've having with GHC 6.10.1: module Main where newtype Box a = B a make :: a - Box a make x = B x val :: Box a - a val (B x) = x test1 :: Box a - a - [a] test1 box x = go box x where go :: Box a - a - [a] go b y = [(val b), y] test2 :: Box a - a - [a] test2 box x = go x where -- go :: a - [a] go y = [(val box), y] main :: IO () main = do print $ test1 (make 1) 2 If I uncomment the commented type declaration, I get the familiar error Couldn't match expected type `a1' against inferred type `a' On the other hand, the earlier code is identical except that it passes an extra argument, and GHC matches the types without complaint. This is a toy example to isolate the issue; in the actual code one wants a machine-checkable type declaration to help understand the function, which is local to save passing an argument. To the best of my understanding, I've given the correct type, but GHC won't make the inference to unify the type variables. I wonder if I found a GHC blind spot. However, it is far more likely that my understanding is faulty here. Any thoughts? Thanks, Dave ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC 6.10.1 type puzzler
test2 :: Box a - a - [a] test2 box x = go x where -- go :: a - [a] go y = [(val box), y] Couldn't match expected type `a1' against inferred type `a' You need to turn on {-# ScopedTypedVariables #-}. See http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#scoped-type-variables Your first example works without this extension, because the local definition 'go' is fully polymorphic. However, in the second example, the type variable 'a' in the signature of 'go' is not fully polymorphic - it must be exactly the _same_ 'a' as in the top-level signature. Regards, Malcolm ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: ANNOUNCE: GHC version 6.10.1 - EditLine / terminal incompatibility?
Would it be worth adding this hard-won lore somewhere on a Wiki where it can be found later? Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:glasgow-haskell-users- | [EMAIL PROTECTED] On Behalf Of Duncan Coutts | Sent: 07 November 2008 18:09 | To: GHC-users list | Cc: Philip K.F. Hölzenspies | Subject: Re: ANNOUNCE: GHC version 6.10.1 - EditLine / terminal incompatibility? | | On Fri, 2008-11-07 at 09:14 -0800, Judah Jacobson wrote: | On Fri, Nov 7, 2008 at 4:36 AM, Duncan Coutts | [EMAIL PROTECTED] wrote: | | I get some working and some non-working. Eg backspace, del, home, end | work, but the ctl-left/ctl-right to jump words does not. | | Does anyone know how libedit is supposed to be configured? readline | uses /etc/inputrc but libedit either does not or doesn't understand all | of it. | | /me wonders if it was really necessary to switch from readline | | Duncan | | You can configure libedit with a ~/.editrc file. | | http://www.manpagez.com/man/5/editrc/ | | Thanks Judah. | | To save everyone else having to read the man page and working out | through trial and error what the key escape codes are, add the following | to your ~/.editrc file. | | # mappings for Ctrl-left-arrow and Ctrl-right-arrow for word moving | bind \e[1;5D vi-prev-word | bind \e[1;5C vi-next-word | | (though from reading the readline /etc/inputrc it suggests that \e[5C | and \e[5D might be right on some systems) | | It's unfortunate that editline does not seem to support any | global /etc/editrc file which would enable distros to make it do the | right thing by default like they do for readline. | | Duncan | | ___ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC 6.10.1 type puzzler
Dave Bayer wrote: Here is an example illustrating a type problem I've having with GHC 6.10.1: module Main where newtype Box a = B a make :: a - Box a make x = B x val :: Box a - a val (B x) = x test1 :: Box a - a - [a] test1 box x = go box x where go :: Box a - a - [a] go b y = [(val b), y] test2 :: Box a - a - [a] test2 box x = go x where -- go :: a - [a] go y = [(val box), y] If you really want to specify the type for a local declaration, you'll have to turn on ScopedTypeVariables. Otherwise 'a' is test2 type signature and 'a' in go type signature mean different unrelated things. In test2 box remains with the first 'a', while go is with the second. There is need for unification. In the case of test1 go has all the variables. In other words, you get test1 :: forall p. Box p - p - [p] go :: forall q. Box q - q - [q] and you perfectly can call go with test1 arguments. On the other hand, test2 :: forall p. Box p - p - [p] go :: forall q. q - [q] and obviously there's a problem. Do this {-# LANGUAGE ScopedTypeVariables, PatternSignatures #-} test2 :: Box a - a - [a] test2 box (x::a) = go x-- here you say, that x :: a where go :: a - [a] -- here you mention the same a go y = [(val box), y] PatternSignatures appears to be needed for pattern x::a If I uncomment the commented type declaration, I get the familiar error Couldn't match expected type `a1' against inferred type `a' On the other hand, the earlier code is identical except that it passes an extra argument, and GHC matches the types without complaint. This is a toy example to isolate the issue; in the actual code one wants a machine-checkable type declaration to help understand the function, which is local to save passing an argument. To the best of my understanding, I've given the correct type, but GHC won't make the inference to unify the type variables. I wonder if I found a GHC blind spot. However, it is far more likely that my understanding is faulty here. Any thoughts? Thanks, Dave ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC 6.10.1 type puzzler
Dave Bayer [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.glasgow.user: test1 :: Box a - a - [a] test1 box x = go box x where go :: Box a - a - [a] go b y = [(val b), y] The type signature go :: Box a - a - [a] is equivalent to go :: Box b - b - [b] or go :: forall a. Box a - a - [a] or go :: forall b. Box b - b - [b] because the type variable a in the type signature for test1 does not scope over the type signature for go. Fortunately, go here does have that type. test2 :: Box a - a - [a] test2 box x = go x where -- go :: a - [a] go y = [(val box), y] Here go does not have the type forall a. a - [a]; it is not polymorphic enough. To write the signature for go inside test2, you need lexically scoped type variables: http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#scoped-type-variables -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2008-11-20 Universal Children's Day http://unicef.org/ 1948-12-10 Universal Declaration of Human Rights http://everyhumanhasrights.org ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC 6.10.1 type puzzler
Thanks all. Sorting this out for my actual code was a bit harder, but it worked. The manual sure wasn't kidding when it said Read this section carefully! Dave On Nov 19, 2008, at 12:12 PM, Malcolm Wallace wrote: You need to turn on {-# ScopedTypedVariables #-}. On Nov 19, 2008, at 12:15 PM, Daniil Elovkov wrote: If you really want to specify the type for a local declaration, you'll have to turn on ScopedTypeVariables. On Nov 19, 2008, at 12:29 PM, Chung-chieh Shan wrote: To write the signature for go inside test2, you need lexically scoped type variables: http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#scoped-type-variables ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: ANNOUNCE: GHC version 6.10.1 - EditLine / terminal incompatibility?
On Nov 19, 2008, at 6:25 PM, Simon Peyton-Jones wrote: Would it be worth adding this hard-won lore somewhere on a Wiki where it can be found later? Dear Simon, all, I don't think logging a specific option on the Wiki is particularly useful (maybe you would have a default editrc file), because, of course, everybody has their own particular wishes. For example, aside from the word-jumping Duncan suggested, I alway use zsh-like history searching, so I like: bind ^[[A ed-search-prev-history bind ^[[B ed-search-next-history Also, there are no de facto escape sequences, because special keys (like function and arrow keys) have different sequences on different terminals. A useful tip that may be useful to include in the wiki is an easy trick that will help you find out your terminals escape sequences. I usually just like to start an application that has no editline or readline capabilities and press the keys. Telnet is one of my favorite applications for this purpose. Something that I would personally very much enjoy is a clear and unmistakable warning from configure when editline is not found. After installing libedit-devel (my ghci-6.10.1 finally has comfortable editing now), I checked config.log; there's not even a mention of libedit capabilities. Maybe a general summary at the end of configure of all the optional capabilities that were or were not configured. As an inspiration, look at gtk2hs' configure output. Regards, Philip ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unicode's greek lambda
On Wed, 2008-11-19 at 15:01 +, Tony Finch wrote: On Wed, 19 Nov 2008, Simon Marlow wrote: Tue Jan 16 16:11:00 GMT 2007 Simon Marlow [EMAIL PROTECTED] * Remove special lambda unicode character, it didn't work anyway Since lambda is a lower-case letter, it's debatable whether we want to steal it to mean lambda in Haskell source. However if we did, then we would probably want to make it a special symbol, not just a reserved symbol, otherwise writing \x-... (using unicode characters of course) wouldn't work, because \x would be treated as a single identifier, you'd need a space. There are a number of mathematical lambdas in Unicode (distinct from teh Greek lambdas), but they are not in the basic multilingual plane and they are presumably not very easy to type :-) Do you know what they are? I couldn't find any other than the greek lambda λ and the latin lambda with stroke ƛ. Duncan ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unicode's greek lambda
On Wed, Nov 19, 2008 at 5:24 PM, Duncan Coutts [EMAIL PROTECTED] wrote: On Wed, 2008-11-19 at 15:01 +, Tony Finch wrote: On Wed, 19 Nov 2008, Simon Marlow wrote: Tue Jan 16 16:11:00 GMT 2007 Simon Marlow [EMAIL PROTECTED] * Remove special lambda unicode character, it didn't work anyway Since lambda is a lower-case letter, it's debatable whether we want to steal it to mean lambda in Haskell source. However if we did, then we would probably want to make it a special symbol, not just a reserved symbol, otherwise writing \x-... (using unicode characters of course) wouldn't work, because \x would be treated as a single identifier, you'd need a space. There are a number of mathematical lambdas in Unicode (distinct from teh Greek lambdas), but they are not in the basic multilingual plane and they are presumably not very easy to type :-) Do you know what they are? I couldn't find any other than the greek lambda λ and the latin lambda with stroke ƛ. They're listed under Mathematical Alphanumeric Symbols. http://www.unicode.org/charts/PDF/U1D400.pdf e.g., 1D6CC mathematical bold small lambda -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Lazy minimum
Compare these two lines in ghci (if you have at least 4 GB of memory): let a = replicate (2^26) 2 in minimum [[1],a,a] let a = replicate (2^26) 2 in minimum [a,a,[1]] The first finishes much faster than the second. This comes up for example in isomorphism testing of graphs embedded in surfaces, which is much easier than the general case: A choice of a directed edge determines a walk of the vertices and edges of the graph, from which the graph can be recovered. A minimal walk can be used to determine a canonical form for the graph, making for a nice Haskell one-liner: normal graph = unwalk $ minimum $ map (walk graph) $ edges graph However, this code suffers from the same issue as the toy ghci lines above. Even though the walks are lazy, the minimum function wastefully explores them. It's clear how to fix this, comparing lazy lists: Play rounds of Survivor, peeling off the heads of the lists at each iteration. One inevitably evaluates all of each minimal list, if there is more than one. This is familiar. For my example, the automorphisms of a graph show up in the complexity of any isomorphism algorithm; they manifest themselves here as the set of minimal walks. What I'm wondering, however, is if there is a way to code minimum efficiently in general, minimum :: Ord a = [a] - a where one knows absolutely nothing further about the type a, but one believes that lazy evaluation will run afoul of the above issue. It would seem that this would require compiler support, allowing code to access approximations to lazy data generalizing the head of a lazy list. I'm reminded of working with power series by working mod x^n for various n. Here, I'd like a bounded version of compare, that returned EQ for data that agreed to a specified lazy evaluation depth. Did I miss that class? Is there a construct in GHC that would allow me to write minimum efficiently for lazy data? ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Lazy minimum
On Wed, Nov 19, 2008 at 8:06 PM, Dave Bayer [EMAIL PROTECTED] wrote: What I'm wondering, however, is if there is a way to code minimum efficiently in general, minimum :: Ord a = [a] - a where one knows absolutely nothing further about the type a, but one believes that lazy evaluation will run afoul of the above issue. It would seem that this would require compiler support, allowing code to access approximations to lazy data generalizing the head of a lazy list. I'm reminded of working with power series by working mod x^n for various n. Here, I'd like a bounded version of compare, that returned EQ for data that agreed to a specified lazy evaluation depth. Did I miss that class? Is there a construct in GHC that would allow me to write minimum efficiently for lazy data? One possibility would be to add minimum and maximum to Ord with the appropriate default definitions, similar to Monoid's mconcat. -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Lazy minimum
On Wednesday 19 November 2008 11:38:07 pm David Menendez wrote: One possibility would be to add minimum and maximum to Ord with the appropriate default definitions, similar to Monoid's mconcat. This is probably the most sensible way. However, first seeing this, I wanted to see if I could do it with RULES, like so: -- this of course fails for Ords where a = b, b =a, but a and b are -- somehow distinguishable. min' :: Ord a = [a] - [a] - [a] min' as@(a:at) bs@(b:bt) | a b = as | b a = bs | otherwise = a : min' at bt -- arbitrary choice here minimum' :: Ord a = [[a]] - [a] minimum' = foldl1 min' {-# RULES min-list min = min' #-} {-# RULES minimum-list minimum = minimum' #-} However, trying this gives me complaints about how Ord a cannot be inferred from Ord [a], so min and minimum aren't providing the right information for min' and minimum'. Perhaps it's unreasonable to expect this to work? Anyhow, barring that problem, that's probably the best hope one has of inserting a fancy procedure for lazy data without reworking the core libraries. This also has the issue of not really solving the problem all the way down. For instance, I think: let a = replicate (2^20) 2 in minimum [[[a]], [[a]], [[1]]] still shows bad behavior. So you need an algorithm more clever than the one I've come up with. :) -- Dan ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Lazy minimum
On Thu, Nov 20, 2008 at 12:18 AM, Dan Doel [EMAIL PROTECTED] wrote: On Wednesday 19 November 2008 11:38:07 pm David Menendez wrote: One possibility would be to add minimum and maximum to Ord with the appropriate default definitions, similar to Monoid's mconcat. This is probably the most sensible way. Now that I've thought about it more, the problem is that min and max are insufficiently lazy for lists. Here's a list clone that has the desired properties: data List a = Nil | a : List a deriving (Show, Eq) instance Ord a = Ord (List a) where compare Nil Nil = EQ compare Nil _ = LT compare _ Nil = GT compare (a : as) (b : bs) = case compare a b of LT - LT EQ - compare as bs GT - GT min (a : as) (b : bs) = case compare a b of LT - a : as EQ - a : min as bs GT - b : bs min _ _ = Nil head' (a : as) = a head' _ = error head': empty List Thus, *Main head' $ min (2 : undefined) (2 : undefined) 2 *Main minimum [2 : undefined, 2 : undefined, 1 : Nil] 1 : Nil The tricky part is that derived instances of Ord do not make min (and max) lazy in this way, so you have to write your own. There are also possible space issues, since min a b will end up re-creating much of a or b if they share a large common prefix. snip This also has the issue of not really solving the problem all the way down. For instance, I think: let a = replicate (2^20) 2 in minimum [[[a]], [[a]], [[1]]] still shows bad behavior. So you need an algorithm more clever than the one I've come up with. :) Yeah, my solution falls down there, too. *Main minimum [(2 : undefined) : Nil, (2 : undefined) : Nil, (1 : Nil) : Nil] *** Exception: Prelude.undefined I don't know if there's a good, general solution here. -- Dave Menendez [EMAIL PROTECTED] http://www.eyrie.org/~zednenem/ ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users