[ ghc-Bugs-748490 ] -odir bug
Bugs item #748490, was opened at 2003-06-03 22:16 Message generated for change (Comment added) made by simonmar You can respond by visiting: https://sourceforge.net/tracker/?func=detailatid=108032aid=748490group_id=8032 Category: Compiler Group: 6.0 Status: Closed Resolution: Fixed Priority: 5 Submitted By: Nobody/Anonymous (nobody) Assigned to: Nobody/Anonymous (nobody) Summary: -odir bug Initial Comment: hello, there seems to be a problem when compiling modules using the hirarchical-namespace and using the -odir flag: (in A/A.hs) module A.A where import A.B (in A/B.hs) module A.B where ghc --make A.A -odir obj Chasing modules from: A.A Compiling A.B ( A/B.hs, obj/A/B.o ) Compiling A.A ( A/A.hs, obj/A/A.o ) ls obj A A.o B.o (the object files were put in obj instead of obj/A) since the compiler thinks that the files are in obj/A but they are actually in obj the files are recompiled all the time. bye iavor -- Comment By: Simon Marlow (simonmar) Date: 2003-06-05 10:30 Message: Logged In: YES user_id=48280 Fixed, thanks. The fix will be in 6.2. -- You can respond by visiting: https://sourceforge.net/tracker/?func=detailatid=108032aid=748490group_id=8032 ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
[ ghc-Bugs-742220 ] readFile problems
Bugs item #742220, was opened at 2003-05-23 09:22 Message generated for change (Comment added) made by simonmar You can respond by visiting: https://sourceforge.net/tracker/?func=detailatid=108032aid=742220group_id=8032 Category: None Group: None Status: Closed Resolution: None Priority: 5 Submitted By: Nobody/Anonymous (nobody) Assigned to: Nobody/Anonymous (nobody) Summary: readFile problems Initial Comment: Hello, We are two students from the University of Utrecht (the Netherlands) working on a project in Haskell. During work on the project, we encountered a problem with the 'readFile' IO Monad. readFile stops reading a file when it encounters ASCII character 26 (\SUB or \^Z - the escape character), as the following piece of coding shows. We've tested this with both the Hugs interpreter and the GHC compiler, but both encounter the same problem. Are there any known solutions for this? Regards, Richard Nieuwenhuis and Niels Reyngoud [EMAIL PROTECTED], [EMAIL PROTECTED] module Main where main = do let output = problemtext putStr output putStr \n\n writeFile outputfile.txt output text - readFile outputfile.txt putStr text problemtext :: String problemtext = strange\SUBstrange -- Comment By: Simon Marlow (simonmar) Date: 2003-06-05 10:33 Message: Logged In: YES user_id=48280 On Windows, the ^Z character is interpreted as end-of-file. To subvert this behaviour, you can put the file into Binary mode using GHC.Handle.hSetBinaryMode. (unfortunately this function isn't available form anywhere more stable, yet). -- You can respond by visiting: https://sourceforge.net/tracker/?func=detailatid=108032aid=742220group_id=8032 ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
[ ghc-Bugs-668705 ] hsc2hs broken under Win32
Bugs item #668705, was opened at 2003-01-15 20:12 Message generated for change (Comment added) made by simonmar You can respond by visiting: https://sourceforge.net/tracker/?func=detailatid=108032aid=668705group_id=8032 Category: None Group: 5.04.2 Status: Closed Resolution: Fixed Priority: 8 Submitted By: Antony Courtney (antonyc) Assigned to: Nobody/Anonymous (nobody) Summary: hsc2hs broken under Win32 Initial Comment: Hi, hsc2hs seems to be broken under Win32 with ghc 5.04.2. If I take a simple test program and attempt to compile it with hsc2hs, I get the following output: $ make -f Makefile.ghc-win32 hsc2hs Test.hsc Test_hsc_make.o(.text+0x2d8):Test_hsc_make.c: undefined reference to `_imp___iob ' Test_hsc_make.o(.text+0x305):Test_hsc_make.c: undefined reference to `_imp___iob ' Test_hsc_make.o(.text+0x31b):Test_hsc_make.c: undefined reference to `_imp___iob ' Test_hsc_make.o(.text+0x348):Test_hsc_make.c: undefined reference to `_imp___iob ' Test_hsc_make.o(.text+0x373):Test_hsc_make.c: undefined reference to `_imp___iob ' Test_hsc_make.o(.text+0x3a0):Test_hsc_make.c: more undefined references to `_imp ___iob' follow collect2: ld returned 1 exit status make: *** [Test.hs] Error 1 [EMAIL PROTECTED] ~/src/haskell/ffi/hsc2hs $ -- Comment By: Simon Marlow (simonmar) Date: 2003-06-05 10:35 Message: Logged In: YES user_id=48280 Submitter hasn't replied. We claim this is now fixed (works for me, anyhow). -- Comment By: Simon Marlow (simonmar) Date: 2003-03-25 10:48 Message: Logged In: YES user_id=48280 I think we allege that these problems were fixed in 5.04.3. Could you test and let us know, so I can close the bug? Thanks. -- Comment By: Simon Marlow (simonmar) Date: 2003-01-20 17:36 Message: Logged In: YES user_id=48280 Reopened; there appear to be some problems with hsc2hs in a standard Windows installation of GHC. What we've discovered: - By default, hsc2hs on windows uses ghc as the C compiler, and $(WhatGccIsCalled) as the linker, where $(WhatGccIsCalled) is set at build time and appears to be c:\mingw\bin\gcc on a system we tried it on, but might be set to gcc in the Windows installer distribution. - What we think ought to happen is that the default C compiler should be set to whatever GHC is installed with this version of hsc2hs, and the linker should also be set to the same thing, or at the least should point to the gcc installed along with your GHC. We don't have a suitable test framework set up to make this change now, but it ought to be addressed before the next release. -- Comment By: Antony Courtney (antonyc) Date: 2003-01-17 18:37 Message: Logged In: YES user_id=689194 If you look at the above output, you will see that it never gets as far as using any .c files that are compiled seperately. The link errors that are reported are directly from hsc2hs attempting to compile, link and execute the .c file it produces internally (which emits a Haskell source file). Nevertheless, it turns out that using the --ld=ghc option did the trick. Thanks for pointing me in the right direction. (GHCers: Is there some reason to use default values of cc and ld that are inconsistent?) -- Comment By: Sigbjorn Finne (sigbjorn) Date: 2003-01-17 17:11 Message: Logged In: YES user_id=232905 Yes, I did. Better make sure you also use 'ghc' as your 'gcc' if you're compiling up any .c files separately. -- Comment By: Antony Courtney (antonyc) Date: 2003-01-17 17:04 Message: Logged In: YES user_id=689194 Thanks for the suggestion, Sigbjorn, but did you actually try it? I get exactly the same output regardless of whether or not I use the --cc=ghc option. -- Comment By: Sigbjorn Finne (sigbjorn) Date: 2003-01-17 16:47 Message: Logged In: YES user_id=232905 C compiler mismatch; use hsc2hs with the option --cc=ghc for better results. -- You can respond by visiting: https://sourceforge.net/tracker/?func=detailatid=108032aid=668705group_id=8032 ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
[ ghc-Bugs-721511 ] Non-exhaustive patterns in ParseMonad.hs
Bugs item #721511, was opened at 2003-04-15 00:40 Message generated for change (Comment added) made by simonmar You can respond by visiting: https://sourceforge.net/tracker/?func=detailatid=108032aid=721511group_id=8032 Category: hslibs/hssource Group: 5.04.3 Status: Closed Resolution: Fixed Priority: 5 Submitted By: Bryn Keller (xoltar) Assigned to: Nobody/Anonymous (nobody) Summary: Non-exhaustive patterns in ParseMonad.hs Initial Comment: Running this code: import Language.Haskell.Parser import System.Environment (getArgs) parseFile s = do file - readFile s case parseModule file of ParseOk m - putStrLn Parsed! ParseFailed loc s - putStrLn $ Parse error at ++ (show loc) ++ : ++ s main = do [fileName] - getArgs parseFile fileName on this file (on Windows 2000) : --Right xs - print xs produces this error at runtime: Fail: Language/Haskell/ParseMonad.hs:143: Non-exhaustive patterns in lambda The original file to be parsed contained some other things too, but this one line turned out to be the cause of the problem. -- Comment By: Simon Marlow (simonmar) Date: 2003-06-05 10:40 Message: Logged In: YES user_id=48280 Fixed, thanks. (rev. 1.9 of Language/Haskell/Lexer.hs, the fix is in 6.0). -- Comment By: Nobody/Anonymous (nobody) Date: 2003-04-22 12:42 Message: Logged In: NO I'm guessing that this comment wasn't terminated with a newline. That's not legal Haskell (though one might argue that the Report is too restrictive here). The error is now flagged correctly. -- You can respond by visiting: https://sourceforge.net/tracker/?func=detailatid=108032aid=721511group_id=8032 ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: Haddock module description
Simon Marlow wrote: Haddock understands the style of module header that we're using for the hierarchical libraries. The module header is described in this document (see the section Reference Libraries-Coding Style-Module Header): http://www.haskell.org/hierarchical-modules/libraries/libraries.html 4.9. Coding style 4.9.1. Standard module header -- | -- Module : module module is the fully qualified module name of the module This haddock Module entry is annoying, since is may become inconsistent with the actual module name (following the Haskell keyword module). In fact I use: -- Module : $Header$ Cheers Christian ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Incorrect Mime Type for Mac OS Package
Hi, The Haskell Web Server claims that the .dmg file for the MacOS Package is of type text/plain; some browsers on MacOS (IE and Netscape) therefore try to display it as plain text instead of downloading it. Is anyone able to fix that somehow? Cheers, Wolfgang ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
update of ghc-6.0 rpms for Red Hat Linux 9
20030602()1145 Jens Petersen : I have built rpms of ghc-6.0 on Red Hat Linux 9. I didn't build the libraries with profiling this time, however the package includes the docs, the xlib binding from hslibs and hence green-card from cvs too (a number of patches/hacks were needed for this and they can be found in the nosrc rpm). : (Note the nosrc rpm doesn't include the ghc-6.0 tarball, you'll have to download that separately if you wish to rebuild the package.) I updated the packages to just a conventional build of ghc-6.0 (the xlib and green-card packaging in the first version had problems anyway). There shouldn't be any changes in the ghc-6.0 packaging itself, so unless you wish to get rid of the broken green-card and xlib in the first version there is no necessity to upgrade. You can download ghc-6.0-2.rhl9 from: http://haskell.org/~petersen/rpms/ghc/ Cheers, Jens ps If you wish to have the prof libs too next time I build, please let me know. I use them so rarely myself that I didn't bother to build them, but I don't mind doing so if there is demand. pps There is a rpm package of the alpha greencard-3.00 release in http://haskell.org/~petersen/greencard too. ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: update of ghc-6.0 rpms for Red Hat Linux 9
tor 2003-06-05 klockan 08.18 skrev Jens Petersen: ps If you wish to have the prof libs too next time I build, please let me know. I use them so rarely myself that I didn't bother to build them, but I don't mind doing so if there is demand. I think there may be a demand. I use profiling frequently, especially heap profiling. Some memory leaks are very hard to find otherwise, especially in code I haven't written myself. But don't bother building it just for me, I've already built an RPM myself from the included spec file. It worked flawlessly. Did you make any changes to it? Regards, Martin -- Martin Norbäck [EMAIL PROTECTED] Kapplandsgatan 40 +46 (0)708 26 33 60 S-414 78 GÖTEBORG http://www.dtek.chalmers.se/~d95mback/ SWEDEN OpenPGP ID: 3FA8580B ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Collecting values from Functors?
Ralf Hinze wrote: What happens if the tree contains additional integers to record, say, balancing information. The information a functor provides is vital here. Take as the simplest example newtype Weighted a = WithWeight (Int, a) Without the functor definition there is no way to distinguish the two Ints in Weighted Int. You are right in that gmapping is not generally aware of term components that relate to the parameter of a parameterised datatype. This has to do with the restricted structural induction and with the bias towards nominal type case. One can still recover `type distinctions' by pattern matching however. I elaborated the example like this: http://www.cs.vu.nl/boilerplate/testsuite/foldTree.hs (More generally, it is certainly debatable if the gmap combinators are in place for more fancy datatypes, e.g., nested datatypes. I mean that the design and use of these datatypes is normally an ingenious process as opposed to boilerplate programming in the sense of AST or document traversal.) Ralf L. -- Ralf Laemmel VU CWI, Amsterdam, The Netherlands http://www.cs.vu.nl/~ralf/ http://www.cwi.nl/~ralf/ ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: ANN: H98 FFI Addendum 1.0, Release Candidate 10
On Thu, Jun 05, 2003 at 09:25:11AM +0200, John Hughes wrote:
On Wed, 4 Jun 2003, Ross Paterson wrote:
+ \item[unsafePerformIO ::\ IO a - a]
+ Return the value resulting from executing the \code{IO} action.
+ This value should be independent of the environment;
+ otherwise, the system behaviour is undefined.
Rationale: to preserve equational reasoning, the crucial responsibility
of the programmer is to ensure that the action is deterministic. Without
that, all bets are off. The next paragraph deals with side effects:
If the \code{IO} computation wrapped in \code{unsafePerformIO} performs side
effects, then the relative order in which those side effects take place
(relative to the main \code{IO} trunk, or other calls to
\code{unsafePerformIO}) is indeterminate.
I suggest adding:
Moreover, the side effects may be performed several times or not
at all, depending on lazy evaluation and whether the compiler
unfolds an enclosing definition.
This seems to be a common gotcha which it would be wise to warn of.
Sure.
Having washed our hands of unsafePerformIO applied to non-deterministic
actions, we no longer need the third paragraph, which (though scary)
provides no useful guidance:
- Great care should be exercised in the use of this function. Not only
- because of the danger of introducing side effects, but also because
- \code{unsafePerformIO} may compromise typing, for example, when it is used
- in conjunction with polymorphic references.
Or maybe it would be better to provide some useful guidance? How about,
To preserve the soundness of the type system, the result of
unsafePerformIO should always have a monomorphic type. For
example,
listRef = unsafePerformIO (newIORef [])
is unsafe, while
listRef = unsafePerformIO (newIORef ([] :: [Int]))
is type safe. In the first case listRef is assigned type IORef
[a], which makes it possible to store a list of one type and fetch
it with a different type.
With the proposed description of unsafePerformIO, neither of these forms
would be meaningful, because they return an environment-dependent value.
I'm suggesting we draw the line there and not say anything about
uses of unsafePerformIO on the other side of it. That is, document
unsafePerformIO enough to serve the FFI, but stipulate limits to preserve
equational reasoning. Other uses of unsafePerformIO (e.g. for global
variables) are useful, but I don't think they belong in the FFI spec.
Maybe unsafePerformIO should have an addendum of its own.
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: ANN: H98 FFI Addendum 1.0, Release Candidate 10
That is, document unsafePerformIO enough to serve the FFI, but stipulate limits to preserve equational reasoning. I think this is very hard to do. When we use unsafePerformIO in the ffi, we are using the IO monad to sequence [un]marshalling side-effects. For example, peeking and poking foreign memory locations, allocating and freeing memory, etc. We might even be making remote procedure calls over a network (for example, COM could transparently do this) or creating a temporary file which is deleted after use. These side effects might only affect this process (fiddling with memory) or they might affect the operating system (using sbrk to allocate more memory) or they might affect the network (remote procedure calls). They are certainly visible outside the confines of the Haskell code. We have to construct a semantics which says 'if you only allow observations of the form insert your set of allowed observations here then unsafePerformIO is safe'. The problem is that people might reasonably disagree about what a reasonable set of observations are. Most people would want to exclude any modification of the filesystem or network but, for some applications, those are entirely reasonable things to access. -- Alastair Reid ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Collecting values from Functors?
On Thu, Jun 05, 2003 at 09:08:03AM +1200, Tom Pledger wrote: | I am sorry, I misunderstood the problem. You're too modest. :-) There *is* a solution in that direction. Yes, I knew I could use a State monad or a Writer monad, but I thought that it would be an overkill. Fold is more appropriate here. Here's my version of fmapM, which was inspired by something in Tim Sheard's paper Generic Unification via Two-Level Types and Parameterized Modules. import Control.Monad.State -- -- Functors through which monads may be lifted class Functor f = FunctorSeq f where fseq :: Monad m = f (m a) - m (f a) instance FunctorSeq [] where fseq = sequence instance FunctorSeq Maybe where fseq Nothing = return Nothing fseq (Just mx) = do x - mx; return (Just x) fmapM :: (Monad m, FunctorSeq f) = (a - m b) - f a - m (f b) fmapM f xs = fseq (fmap f xs) fseq2list :: (FunctorSeq f) = f a - [a] fseq2list fa = reverse (execState (fmapM (\a - modify (a:)) fa) []) I like this solution. The fseq function seems to be more general. Regards, Tom Regards, Tom :) -- .signature: Too many levels of symbolic links ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: forall quantifier
Ketil Z. Malde wrote: I have a function declared as: anova2 :: (Fractional c, Ord b) = [a-b] - (a-c) - [a] - [Anova1 c] where the first parameter is a list of classifiers. I could simplify it, I guess, to something like classify :: Eq b = [a-b] - [a] - [[[a]]] ^^^ Isn't this one list too many? classify cs xs = ... where for each classifying function in cs, I would get the xs partitioned accordingly. E.g. classify [fst,snd] [(1,0), (1,2), (2,0)] would yield [ [(1,0), (1,2)], [(2,0)] -- classified by `fst` , [(1,0), (2,0)], [(1,2)]] -- classified by `snd` Now, obviously, the problem is that fst and snd, being passed in a list, needs to be of the same type; this complicates classifying a list of type [(Int,Bool)], for instance?. What you'd need would be an existential type of the form classify :: [exists b. Eq b = a-b] - [a] - [[a]] Such a type is not available directly in Haskell, but only through an auxilary data type: data Classifier a = forall b. Eq b = Classifier (a - b) Using that you should be able to implement classify :: [Classifier a] - [a] - [[a]] Cheers, - Andreas -- Andreas Rossberg, [EMAIL PROTECTED] Computer games don't affect kids; I mean if Pac Man affected us as kids, we would all be running around in darkened rooms, munching magic pills, and listening to repetitive electronic music. - Kristian Wilson, Nintendo Inc. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: forall quantifier
I don't properly understand this either, but as it happens I was looking at this in the GHC user guide only yesterday... [[ : MkFoo :: forall a. a - (a - Bool) - Foo Nil :: Foo Notice that the type variable a in the type of MkFoo does not appear in the data type itself, which is plain Foo. For example, the following expression is fine: [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo] Here, (MkFoo 3 even) packages an integer with a function even that maps an integer to Bool; and MkFoo 'c' isUpper packages a character with a compatible function. These two things are each of type Foo and can be put in a list. : ]] -- http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html#EXISTENTIAL-QUANTIFICATION At 15:20 04/06/03 +0200, Ketil Z. Malde wrote: Hi, This is one of those topics everybody else seems to be familiar with, but which I don't quite understand, and can't seem to find any good information about. I have a function declared as: anova2 :: (Fractional c, Ord b) = [a-b] - (a-c) - [a] - [Anova1 c] where the first parameter is a list of classifiers. I could simplify it, I guess, to something like classify :: Eq b = [a-b] - [a] - [[[a]]] classify cs xs = ... where for each classifying function in cs, I would get the xs partitioned accordingly. E.g. classify [fst,snd] [(1,0), (1,2), (2,0)] would yield [ [(1,0), (1,2)], [(2,0)] -- classified by `fst` , [(1,0), (2,0)], [(1,2)]] -- classified by `snd` Now, obviously, the problem is that fst and snd, being passed in a list, needs to be of the same type; this complicates classifying a list of type [(Int,Bool)], for instance¹. I have a vague notion this is solvable using quantifiers (since I ever only use Eq operations on the type), but I'm not sure exactly how, I can't seem to find a good tutorial, and my Monte-Carlo programming approach doesn't seem to be leading anywhere :-) Can somebody suggest a solution, or a place to look? -kzm ¹ I guess I can convert Bool to Int (True-1, False-0), but it's not very appealing, IMHO. -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell --- Graham Klyne [EMAIL PROTECTED] PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: ANN: H98 FFI Addendum 1.0, Release Candidate 10
Ross Paterson [EMAIL PROTECTED] wrote,
On Fri, May 23, 2003 at 07:33:05AM +1000, Manuel M T Chakravarty wrote:
Dear Haskell Folks,
Release Candidate 10 of the H98 FFI Addendum 1.0 is now
available from
http://www.cse.unsw.edu.au/~chak/haskell/ffi/
I have an ideological objection. I think that the inclusion of
unsafePerformIO in an Addendum sends entirely the wrong signal. I know
it's needed for marshalling for otherwise pure functions that pass their
data through pointers. Very well, but the inclusion of unsafePerformIO
allows many more uses. At a stroke it removes many of the trickiest
design problems of Haskell, and we can't have that.
I propose that the Addendum say that it permits unsafePerformIO for that
purpose only, i.e. the IO calls it contains are restricted to foreign
calls and functions from Storable and Marshal*, these may only access
Ptr's inaccessable outside the unsafePerformIO, and no other visible
side effects are permitted.
Well, the text already says,
\item[unsafePerformIO ::\ IO a - a] Execute an \code{IO} action in place of a
pure computations. For the behaviour to be predictable, the IO computation
should be free of side effects and independent of its environment.
If the \code{IO} computation wrapped in \code{unsafePerformIO} performs side
effects, then the relative order in which those side effects take place
(relative to the main \code{IO} trunk, or other calls to
\code{unsafePerformIO}) is indeterminate.
Great care should be exercised in the use of this function. Not only
because of the danger of introducing side effects, but also because
\code{unsafePerformIO} may compromise typing, for example, when it is used
in conjunction with polymorphic references.
I think, the warning sign is clear. Especially in the
context of the FFI, anything more is a waste of paper IMHO.
After all, you can import any C function with a pure type,
which also allows you to wreck arbitrary havoc. We enable
the user to disguise arbitrary machine code as a Haskell
function of essentially arbitrary type. In comparison,
`unsafePerformIO' seems angelic.
Cheers,
Manuel
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: labelled fields
Steffen wrote
I need something like
data Type = TCon String {lmtc::Maybe String} ...
but this does not seem to be possible. Instead
I have to waste identifiers:
data Type = TCon {senseless::String,lmtc::Maybe String} ...
Why? Are there any formal reasons against the
above declaration?
Clearly it's arguable, since SML allows general record types.
My SML syntax is rusty but I think you could write:
datatype ty = ty string {lmtc : string option}
or indeed use {lmtc : string option} just like a type.
I don't think [EMAIL PROTECTED] is suitable for lengthy
discussions of the merits of SML versus Haskell or vice-versa,
so I will state my view and leave it at that:
(1) the Haskell approach costs you slightly more typing.
(2) on the other hand the error messages are slightly better,
since if you type TCon {sensless = foo} the compiler should
spot immediately that sensless has no place in a TCon, while
in ML the compiler will have to say something like Expecting a
{senseless :: String}, found a {sensless :: String}, which leaves
you to work out what it is about the context that requires a
{senseless :: String}
(3) the Haskell approach allows several constructors to have the
same field name, for example
data Ty1 =
TCon1 {lmtc :: Maybe String}
| TCon2 {lmtc :: Maybe String, extraField :: String}
and you then have a function lmtc :: Ty1 - Maybe String which works
for all constructors having the lmtc field.
(4) Haskell will fill in undefined fields, with values that give
error messages if you try to look at them.
Which you prefer is entirely up to you. None of the above points
are terribly important. I personally prefer the Haskell approach,
but not by much.
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: forall quantifier
On Wed, Jun 04, 2003 at 02:46:59PM +0200, [EMAIL PROTECTED] wrote: Now I want to print part of the record. What I would like to do is the following putStrLn $ concatMap show [a,c,d] !!! bang !!! So what I actually do is putStrLn $ concat [show a, show c, show d] Works, but a little bit clumsy, especially with long lists. Is there a nice solution? You can do something like this: infixr 5 +++ (+++) :: Show a = a - [String] - [String] a +++ l = show a : l concat $ a +++ b +++ c +++ [] Best regards, Tom -- .signature: Too many levels of symbolic links ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: forall quantifier
Yes, this would work, thanks. But let me extent my question: what if all the types would be in a class FakeClass which has function specialID :: a - ID and I would like to do foo $ map specialID [a,b,c,d] ? ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: forall quantifier
On Wed, Jun 04, 2003 at 04:43:10PM +0200, [EMAIL PROTECTED] wrote:
Yes, this would work, thanks.
But let me extent my question: what if all the types would be in a
class FakeClass which has function specialID :: a - ID and
I would like to do
foo $ map specialID [a,b,c,d]
?
Well, in Template Haskell you can do:
{-# OPTIONS -fglasgow-exts #-}
module B where
import Language.Haskell.THSyntax
data AnyShow = forall s. Show s = AnyShow s
instance Show AnyShow where
show (AnyShow s) = show s
metaMap :: ExpQ - ExpQ - ExpQ
metaMap qf ql = do
l - ql
case l of
Infix (Just x) (Con GHC.Base::) (Just xs) - do
let ys = metaMap qf (return xs)
[| ($qf $(return x) : $ys) |]
Con GHC.Base:[] - do
[| [] |]
ListExp xs - do
ys - sequence [ [| $qf $(return x) |] | x - xs ]
return $ ListExp ys
other - do
fail $ metaMap: unexpected syntax: ++ show other
and then:
map show $( metaMap [| AnyShow |] [| [1, 1.3, [1,2,3,4]] |]
and
map show $( metaMap [| AnyShow |] [| [1, 1.3, 'a'] |]
will work, but this won't
map show $( metaMap [| AnyShow |] [| [1, 1.3, 'a', [1,2,3,4]] |]
Is there a way to turn of typing within meta quotations?
Best regards,
Tom
--
.signature: Too many levels of symbolic links
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Collecting values from Functors?
I'm trying to figure if there's any way I can use (say) monads to collect values from a Functor. For example, suppose I have a tree of some values that supports fmap, is there any way I can use the fmap function to collect a list of all the node values? #g --- Graham Klyne [EMAIL PROTECTED] PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: Haddock module description
At 14:58 04/06/03 +0100, Simon Marlow wrote: Haddock understands the style of module header that we're using for the hierarchical libraries. The module header is described in this document (see the section Reference Libraries-Coding Style-Module Header): http://www.haskell.org/hierarchical-modules/libraries/libraries.html Great... just what I wanted. Thanks. #g --- Graham Klyne [EMAIL PROTECTED] PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef with a regular monad
Conjecture: It's impossible to implement RefMonad directly in Haskell
without making use of built-in ST or IO functionality and without unsafe or
potentially diverging code (such as unsafeCoerce).
Any takers?
If this is true or suspected to be true, any thoughts on whether a structure
besides Monad could encapsulate safe references in Haskell without core
language changes? My intuition is that no such structure exists in Haskell
with power and flexibility equivalant to RefMonad (support for references of
arbitrary types not limited by their context.)
If this is generally thought to be impossible in Haskell, what sort of
language extensions would be needed to make this work safely, meaning
without unsafe coercions? This seems like a hairy problem. Yet it gets to
the core question of whether Haskell's monads can really implement
imperative features (such as references) in a purely functional way, or are
just a means of sequentializing those imperative constructs that are built
into the runtime.
Any solutions I can think of require a dependent-typed heap structure, and
that all references be parameterized by the heap in which they exist.
-Tim
- Original Message -
From: Ashley Yakeley [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Wednesday, June 04, 2003 5:19 PM
Subject: Re: Typesafe MRef with a regular monad
In article [EMAIL PROTECTED],
[EMAIL PROTECTED] wrote:
Ashley Yakeley wrote:
] ] Is it possible to actually implement a working instance of RefMonad
in
] ] Haskell, without making use of a built-in monad like IO or ST?
] You certainly wouldn't be able to do this for any monad M which had:
] performM :: forall a. M a - a;
] ...because it wouldn't be type-safe: you'd be able to construct coerce
] :: a - b just as you can with unsafePerformIO.
Fortunately, that doesn't seem to be the case.
That's only because you've failed to do the difficult part: implement
newRef. Your monadic solution has a statically typed/sized store: I'd
say it doesn't properly count as a heap since you can't heap new stuff
on it.
The original problem was to create an instance of
class Monad m = RefMonad m r | m - r where
newRef :: a - m (r a)
readRef :: r a - m a
writeRef :: r a - a - m ()
without making use of IO or ST. Given some M and R that have
instance RefMonad M R
performM :: forall a. M a - a
one can write this:
coerce :: forall a b. a - b;
coerce a = let
{
ref = performM (newRef Nothing);
} in performM (do
{
writeRef ref (Just a);
mb - readRef ref;
case mb of {Just b - return b;};
});
--
Ashley Yakeley, Seattle WA
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef with a regular monad
On Wed, 04 Jun 2003 15:19:53 -0700
Ashley Yakeley [EMAIL PROTECTED] wrote:
In article [EMAIL PROTECTED],
[EMAIL PROTECTED] wrote:
Ashley Yakeley wrote:
] ] Is it possible to actually implement a working instance of
RefMonad in ] ] Haskell, without making use of a built-in monad like
IO or ST?
] You certainly wouldn't be able to do this for any monad M which
had:
] performM :: forall a. M a - a;
] ...because it wouldn't be type-safe: you'd be able to construct
coerce ] :: a - b just as you can with unsafePerformIO.
Fortunately, that doesn't seem to be the case.
That's only because you've failed to do the difficult part: implement
newRef. Your monadic solution has a statically typed/sized store: I'd
say it doesn't properly count as a heap since you can't heap new
stuff on it.
I agree, if I knew I'd have 5 components before I could just use a 5
tuple and a State monad. I'd have to look back over the other heap
stuff to see what it provides type-wise, but (at least the new monad
version) seems to miss the point.
The original problem was to create an instance of
class Monad m = RefMonad m r | m - r where
newRef :: a - m (r a)
readRef :: r a - m a
writeRef :: r a - a - m ()
without making use of IO or ST. Given some M and R that have
instance RefMonad M R
performM :: forall a. M a - a
M = (forall s.ST s)
R = STRef s
e.g. runST :: (forall s.ST s a) - a
you can use the same trick for your own RefMonad. I'm not sure if this
will work with RefMonad exactly. If ST/STRef can be made an instance of
RefMonad without any trouble though, then I believe it should work.
one can write this:
coerce :: forall a b. a - b;
coerce a = let
{
ref = performM (newRef Nothing);
} in performM (do
{
writeRef ref (Just a);
mb - readRef ref;
case mb of {Just b - return b;};
});
I was having fun with
coerce :: a - b
coerce x = unsafePerformIO (writeIORef ref x readIORef ref)
where ref = unsafePerformIO (newIORef undefined)
last night, some fun examples (using GHCi 5.04.3),
data Foo a = Bar | Baz a (Foo a)
coerce 5 :: Maybe Int == Nothing
coerce 'a' :: Int == 97
coerce [1..3] :: Foo Integer == (Baz 1 (Baz 2 (Baz 3 Bar)))
coerce [4] :: Maybe Integer == Just 4
I need to reread the GHC internals paper, I want to see if I can get one
like
(coerce something :: (sometype - someothertype)) someotherthing
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef with a regular monad
In article [EMAIL PROTECTED], Derek Elkins [EMAIL PROTECTED] wrote: M = (forall s.ST s) R = STRef s e.g. runST :: (forall s.ST s a) - a you can use the same trick for your own RefMonad. I'm not sure if this will work with RefMonad exactly. If ST/STRef can be made an instance of RefMonad without any trouble though, then I believe it should work. No, it won't work, fortunately ST is safe this way: newSTRef Nothing :: forall a s. ST s (STRef s (Maybe a)) runST (newSTRef Nothing) :: -- type error, s escapes. The type error occurs because forall s. ST s a cannot be matched with forall s. ST s E (for some type-expression E) if E contains s (which it does in this case). -- Ashley Yakeley, Seattle WA ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
ExtractableFunctors and Some HScheme Internals Explained
In article [EMAIL PROTECTED],
Tom Pledger [EMAIL PROTECTED] wrote:
Here's my version of fmapM, which was inspired by something in Tim
Sheard's paper Generic Unification via Two-Level Types and
Parameterized Modules.
Gosh well I came across something very similar completely independently:
class (Functor f) = ExtractableFunctor f where
{
fExtract :: forall g a. (FunctorApplyReturn g) =
f (g a) - g (f a);
};
See
http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/hbase/Source/HBase/Catego
ry/Functor.hs?rev=HEADcontent-type=text/vnd.viewcvs-markup
Btw FunctorApplyReturn is a larger class than Monad (should be a
superclass IMO, but I'm not yet ready to define my own Monad class in
HBase). In addition to fmap it has
return' :: a - f a
fApply :: f (a - b) - (f a - f b)
...from which one can derive liftF2. This makes fExtract more general
and thus ExtractableFunctor more demanding; but I expect most of the
types that are your FunctorSeq would also be ExtractableFunctor.
So I've been using ExtractableFunctors in HScheme to handle recursive
binding macro letrec:
data ZeroList a = MkZeroList;
data NextList t a = MkNextList a (t a);
These can be made ExtractableFunctors and allow lists where the type
indicates the length, for instance:
type List3 = NextList (NextList (NextList ZeroList));
I then use them to build up values of this type:
data MutualBindings f a v = forall t. (ExtractableFunctor t) =
MkMutualBindings (t (f a)) (forall r. f r - f (t v - r));
So here t is the list type. f is my clever SymbolExpression type, an
instance of my equally clever FunctorLambda class. a is basically m
SchemeObject where m is an appropriate Monad. v is a reference to a
SchemeObject (simplifying here a certain amount).
Think of the SymbolExpression type as encoding lambda-terms. You can do
things such as find its free variables, etc.
The first part of the MkMutualBindings is a list of expressions found in
the letrec head. The second part is a function that abstracts based on
the variables listed. For instance:
(letrec
((a b) (b 3) (c a))
(+ c 1)
)
Support for this kind of recursive binding is actually more than R5RS
requires, but I thought it worth trying after I discovered how to write
the fixed-point function mfix for my continuation-passing monad.
The head of the letrec is parsed to make a MutualBindings. The first
part of the MkMutualBindings would be essentially a List3 (above) of
expressions representing b, 3 and a. The second part would be an
abstracting function that turns a SymbolExpression of anything r to
a SymbolExpression of a function that depended on a list of three
references, by abstracting on the symbols a, b, and c.
You can kind of gloss it like this:
MkMutualBindings bindValues abstracter;
abstracter (f (* a b c)) = f (\a b c - (* ++ a ++ b ++ c ++ ))
Having constructed the MutualBindings, I then call
foo (fExtract (fmap abstracter bindValues)) (abstracter body)
foo is what I'm working on currently. I had an earlier version that
only worked with the pure functional flavour of HScheme; I'm now
generalising it with mfix.
It's all in CVS...
http://sourceforge.net/cvs/?group_id=47823
--
Ashley Yakeley, Seattle WA
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Collecting values from Functors?
Rather than using fmap, why not use gmap in GHC. Using an appropriate generic traversal scheme, say listify, all the code you write is the following expression: listify (const True) mytree :: [Int] if you are looking for all the Ints in mytree = Fork (Leaf 42) (Fork (Leaf 88) (Leaf 37)) So this would give you [42,88,37]. What happens if the tree contains additional integers to record, say, balancing information. The information a functor provides is vital here. Take as the simplest example newtype Weighted a = WithWeight (Int, a) Without the functor definition there is no way to distinguish the two Ints in Weighted Int. Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
[tim@epicgames.com: Fw: Typesafe MRef with a regular monad]
G'day all. On Wed, Jun 04, 2003 at 07:31:03PM -0500, Tim Sweeney wrote: Conjecture: It's impossible to implement RefMonad directly in Haskell without making use of built-in ST or IO functionality and without unsafe or potentially diverging code (such as unsafeCoerce). Any takers? WARNING: This is not rigorous. Take a prototypical simple state monad: type MyRefMon a = SomeState - (a. SomeState) type MyRef a = Int -- Could be anything other than Int, but -- the important point is that a is not -- mentioned on the RHS anywhere. where SomeState is abstract but concrete. Note that it has no type parameters. Let's also assume the existence of this function: myDeref :: MyRef a - MyRefMon a Again, we know nothing about its implementation (yet). Without loss of generality, and because a has no type constraints, myDeref is equivalent to a function of this type: myDeref' :: Int - SomeState - (a, SomeState) (This step I believe to be far too handwavy. I have no justification for the ability to drop the a parameter here except that Haskell semantics state that if a is not constrained, you can't do anything with it.) Intuitively, there is nothing in the above type signature which gives you any way to construct something of type a, therefore it must be bottom. The parametricity theorem (i.e. free theorem) can probaly be used to show this formally. The only ways I can think of to get over this within Haskell is to: - change the definition of MyRef so that it contains enough information to extract something of type a from SomeState, or - constrain the type (e.g. using Typeable). Cheers, Andrew Bromage ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Safe and sound STRef [Was Implementing RefMonads in Haskell without ST,IO]
Oleg, This is a very neat solution to providing coercion-free references in a local environment. I'm trying to generalize this to some sort of Monad-like typeclass, where there is a nice mapping from Monad's to this new and more powerful typeclass, so that one can combine typed references, IO, etc., into a single framework. It seems to me that your approach couldn't be generalized in this way in Haskell, because the type of the resulting reference-using computation depends on the precise set of heap operations performed there. So, for example, you couldn't do something like: .. a - newRef Int 123 b - if (some conditional) then (newRef Int) else (a) .. Because the heap types propagated out of the conditional's two branches differ. The only way I can see generalizing your technique to support this sort of thing requires a type system supporting both dependent types and subtyping. Think the reference monad as looking somewhat like the state monad; instead of a single piece of state, it propagates a dependent-typed pair of (heapTypeFunc,heapValueFunc) similar in spirit to your PList construct, with the type guaranteeing that any heap operation returns an output heapTypeFunc that's a contravariant extension of its input heapTypeFunc. Conjecture: Implementing type-safe (coercion-free), composable computations over typed references isn't possible in Haskell. By composable I mean that some operator similar in spirit to = on Monads can be implemented and that computations with differing effects can occur in if-branches. But then again, I had not thought the problem you solved using PList to be solveable in Haskell, and am very eager to be proven wrong! -Tim - Original Message - Back in September 2001, Koen Claessen wrote: ] Here is a little experiment I did a while ago. I was trying to isolate ] the capability of the ST monad to deal with different types at the ] same time I conjecture this functionality cannot be implemented ] in Haskell 98, nor in any of the known safe extensions of Haskell. Recently, Tim Sweeney wrote ] Is it possible to actually implement a working instance of RefMonad in ] Haskell, without making use of a built-in monad like IO or ST? The following code shows a safe and sound implementation of a polymorphic heap with references and updates. The heap is capable of storing of polymorphic, functional and IO values. All operations are *statically* checked. An attempt to alter a heap reference with a value of a mismatched type leads to a _compile-time_ error. Everything is implemented in Haskell98 + multiparameter classes with functional dependencies + overlapping instances. I suspect that the latter isn't strictly needed, but it's almost midnight. Most importantly, no IO or ST monad, no unsafePerformIO or unsafeCoerce, no existential types and no Dynamics are needed. It seems that the polymorphic updateable heap can be implemented safely. Although the code looks like a monadic code, the Monad class doesn't seem to be polymorphic enough to wrap our heap. Perhaps arrows will help. I'd like to remark first that the ST monad with polymorphic STRef can be implemented in Haskell98 + safe extensions _provided_ all the values question are in the class Show/Read. When we store values, we store their external representation. When we retrieve a value, we read it. Similarly for values in the Binary class. All such values are _safely_ coercible. The following code however does not make this assumption. In our heap below, we can even store polymorphic functions and IO values! First, the tags for values in our heap data Zero data Succ a class HeapTag a where tag_value:: a - Int instance HeapTag Zero where tag_value _ = 0 -- I just can't avoid the undefined arithmetics instance (HeapTag t) = HeapTag (Succ t) where tag_value _ = 1 + tag_value (undefined::t) The heap reference is the combination of the tag and the desired type. As we will see, the value of the second argument of the HeapRef doesn't actually matter -- only its type does. data HeapRef t a = HeapRef t a Our heap is implemented as a polymorphic associative list data Nil t v r = Nil data Cons t v r = Cons t v r class PList ntype ttype vtype cdrtype where cdr:: ntype ttype vtype cdrtype - cdrtype empty:: ntype ttype vtype cdrtype - Bool value:: ntype ttype vtype cdrtype - vtype tag:: ntype ttype vtype cdrtype - ttype instance PList Nil ttype vtype cdrtype where empty = const True instance (PList n t v r,HeapTag tag) = PList Cons tag vtype (n t v r) where empty = const False value (Cons t v r) = v tag (Cons t v r) = t cdr (Cons t v r) = r The following is the statically typed polymorphic heap itself: class Heap t v h | t h - v where fetch:: (HeapRef t v) - h - v alter:: (HeapRef t v) - v - h - h instance (HeapTag t,PList Cons t v r) = Heap t v (Cons t v r) where fetch _ p =
update of ghc-6.0 rpms for Red Hat Linux 9
20030602()1145 Jens Petersen : I have built rpms of ghc-6.0 on Red Hat Linux 9. I didn't build the libraries with profiling this time, however the package includes the docs, the xlib binding from hslibs and hence green-card from cvs too (a number of patches/hacks were needed for this and they can be found in the nosrc rpm). : (Note the nosrc rpm doesn't include the ghc-6.0 tarball, you'll have to download that separately if you wish to rebuild the package.) I updated the packages to just a conventional build of ghc-6.0 (the xlib and green-card packaging in the first version had problems anyway). There shouldn't be any changes in the ghc-6.0 packaging itself, so unless you wish to get rid of the broken green-card and xlib in the first version there is no necessity to upgrade. You can download ghc-6.0-2.rhl9 from: http://haskell.org/~petersen/rpms/ghc/ Cheers, Jens ps If you wish to have the prof libs too next time I build, please let me know. I use them so rarely myself that I didn't bother to build them, but I don't mind doing so if there is demand. pps There is a rpm package of the alpha greencard-3.00 release in http://haskell.org/~petersen/greencard too. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: powerset
Hi Graham,
On Wed, Jun 04, 2003 at 12:08:38PM +0100, Graham Klyne wrote:
I thought this may be a useful exercise to see how well I'm picking up on
functional programming idioms, so I offer the following for comment:
foldl (++) [] [ combinations n as | n - intRange 1 (length as) ]
By your use of the `intRange' function, I get the feeling you're still
thinking somewhat imperatively. (It's awfully reminiscent of a for-loop...)
Were you trying to write the function from some definition? (The set of all
subsets of X with size = |X| et c. You're looping over the size of the
subset, per se...?)
(Side note: I can think of few instances where you _need_ to deal with the
length of a list directly -- more often than not you can (and probably
should) let recursion take care of that. You can also write [1..length as]
rather than use the intRange function, which looks prettier. :-)
A key point is to try and think of how you can relate one case of the
problem to a simpler instance of the same problem, rather than tackling it
head on. Start by looking at the power set of a few small examples. The
power set of the empty set is the size 1 set consisting of the empty set:
pset [] = [ [] ]
and a couple more:
pset [a] = [ [a], [] ]
pset [b, a] = [ [b, a], [b], [a], [] ]
Notice how the `second half' of pset [b, a] is exactly pset [a]. Can you see
anything that would relate the sets [b, a], [b] to [a], []? (Yes! Chop off
the leading b! :) Let's try to generalise this:
Take a set X, and an element y not in X. Denoting the power set function by
P(), I hope you can see that P(X u {y}) certainly contains P(X). But no set
in (read: member of) P(X) has y as a member, and funnily enough, if we add y
to each element of P(X) we get missing bits of P(X u {y}).
(The fact that the size of the power set is 2^|X| should serve as a hint --
you want to double the size of your power set for each element in X.) So we
arrive at our solution:
pset [] = [ [] ]
pset (x:xs) = let ps = pset xs in map (x:) ps ++ ps
Or at least, this is what would be going through my head if I were trying to
write this. ^_^ Hope it helps a bit...
later,
/Liyang
--
.--| Liyang HU |--| http://nerv.cx/ |--| [EMAIL PROTECTED] |--| ICQ: 39391385 |--.
| :: This is not a signature. :: |
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: powerset
At 15:08 04/06/03 +0100, Liyang HU wrote: A key point is to try and think of how you can relate one case of the problem to a simpler instance of the same problem, rather than tackling it head on. I think that's a good idea to hang on to. Sometimes easier to say than to do, it seems. Thanks, #g --- Graham Klyne [EMAIL PROTECTED] PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: powerset
At 14:00 04/06/03 +0100, Keith Wansbrough wrote:
Looks fine, but you're right - the use of combinations is
inefficient. It's better to iterate over the elements, rather than
the length. Then as you add each element, you consider all the sets
you have so far, and either add the new element to each or not. This
doubles the number of sets. Hence:
powerset :: [a] - [[a]]
powerset [] = [[]]
powerset (x:xs) = xss ++ map (x:) xss
where xss = powerset xs
Neat!
It happens that for the application I have in mind, it is important to
generate shorter subsets first, as the required results are almost always
going to come from smaller subsets of a possibly large base set, and I'm
aiming to exploit lazy evaluation to keep things tractable.
Looking at your code, I'm wondering if it would be possible to use some
alternate form of composition instead of ++, and some auxiliary functions
to pull the results out in the short-to-long sequence.
I'm thinking in terms of building a list of trees..
[[
data NTree a = NTree { nthead::a, ntbody::[NTree a] }
instance Functor NTree where
fmap f (NTree h ts) = NTree (f h) (map (fmap f) ts)
powerset1 :: [a] - [NTree [a]]
powerset1 (x:xs) = (NTree [x] (map (fmap (x:)) xss)) : xss
where xss = powerset1 xs
powerset1 [] = []
listPowerset :: [NTree [a]] - [[a]]
listPowerset [] = []
listPowerset ts = (map nthead ts) ++
listPowerset bodylist
where
bodylist = concat $ filter (not . null) $ map ntbody ts
testN1 = listPowerset $ powerset1 [1,2,3,4]
testN2 = listPowerset $ powerset1 abcdefgh
]]
The list/tree structure looks something like this:
[1]
[2] [2,1]
[3] [3,1]
[3,2] [3,2,1]
[4] [4,1]
[4,2] [4,2,1]
[4,3] [4,3,1]
[4,3,2] [4,3,2,1]
etc.
The list function picks off the members by columns (w.r.t. to above diag)
Notice how important it is to include the empty set in the set of
subsets - it won't work at all if you omit it.
Yes, I noticed something similar in my original version.
I've chosen not include the empty subset in my results, but that's easily
adjusted.
This formulation is particularly nice because in memory, you *share*
all of the lists from the previous iteration, rather than making
copies.
I *think* my revised formulation achieves this.
[...]
My solution isn't perfect, though - the use of append (++) is
inefficient; if this could be avoided, it would be faster.
I didn't see any easy way to avoid (++) in my list readout, but I think I
can claim that the length of the leading list if never more than O(log N)
the tree size.
If I'm evaluating and using the list lazily, using a typical recursive
traversal pattern (like the powerset function itself), is there any cause
for the ++ to actually be evaluated? I suspect not, but can't be sure.
#g
---
Graham Klyne
[EMAIL PROTECTED]
PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: FFI Help
Malcolm Wallace wrote:
foreign import ccall math.h signgam signgamC :: IO Int
signgam is an int variable, but this assumes that it is a function
of type int signgam(void).
Write a C wrapper int get_signgam(void) { return signgam; } and
import that.
Or alternatively, foreign import the address of the int and read it
directly with 'peek'.
import Foreign
...
foreign import ccall math.h signgam signgamC :: Ptr Int32
...
gammaIO :: Double - IO Double
gammaIO x = do lg - lgammaC x
s - peek signgamC
return $ fromIntegral s * exp lg
One potential drawback with that approach is that an implementation
might decide to add thread-safety, in the same manner as glibc does
with errno:
# if !defined _LIBC || defined _LIBC_REENTRANT
/* When using threads, errno is a per-thread value. */
# define errno (*__errno_location ())
# endif
[where __errno_location() returns a thread-specific location via
pthread_getspecific().]
OTOH, a C wrapper will cope with whatever contortions the libc
developers decide to use.
--
Glynn Clements [EMAIL PROTECTED]
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: powerset
G'day all. On Wed, Jun 04, 2003 at 02:00:08PM +0100, Keith Wansbrough wrote: This formulation is particularly nice because in memory, you *share* all of the lists from the previous iteration, rather than making copies. [...] Notice all the sharing - this is a very efficient representation! You save on copying, and you save on memory use. I can never resist a can labelled worms. Let me get out my tin opener... You do save on memory allocations. If, however, you consume the list lazily and discard the results as you consume them (which is the common way lazy programs are written), you actually use more memory at once. Try it if you don't believe me. Test it with this program, using each definition of powerset: summer :: [[a]] - Integer summer xss = foldl' (\xs r - r + toInteger (length xs)) 0 xss n :: Int n = 32 main :: IO () main = print (summer (powerset [1..n])) You'll find that one of them runs in O(n) space and the other most likely blows the heap. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
