Instance checking and phantom types
Hi all, I have an example wich I don't understand: ---begin class C t data T = T instance C T data C t => T1 t = T1 f1 :: T1 () f1 = T1 data C t => T2 t = T2 t f2 :: T2 () f2 = T2 () end The first function, f1, is accepted both by hugs and ghc, unlike the second wich is rejected. Why does this happen? Shouldn't f1 be rejected with "no instance C ()" Thanks for help Vincenzo ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: threaded red-black tree
this might help: http://www.cs.kent.ac.uk/people/staff/smk/redblack/Untyped.hs andrew Lex Stein said: > > Hi, No one responded to my question several weeks ago about a purely > functional implementation of a threaded, red-black tree. My message was > sent about the same time as that flurry of silly emails about "how to > respond to homework questions". Was my message not responded to because it > was classified as a homework question? I assure you this is officework, > not homework. I ended up porting Okasaki's red-black tree implementation; > hacking it apart with a bunch of mutation for the threading of the list > through the tree. However, I'm still missing a deletion function and I > haven't been able to find a prototype (Okasaki's red-black tree module > lacks delete). My study of the RB-tree deletion routine in CLR hasn't yet > yielded an adaptation for a functional environment. Any advice would be > much appreciated. > > Thanks, > Lex > > -- > Lex Stein http://www.eecs.harvard.edu/~stein/ > [EMAIL PROTECTED]cell: 617-233-0246 > > ___ > Haskell-Cafe mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- http://www.acooke.org/andrew ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Read file problems
HI, I have a recurrent probleme with function readFile and Monad : it is that i try to get a line, transform it and stock it in a list and what i want is that function return me the list. But hugs say me that in readFile my_file >>= \s -> map cons_line (lines s) readFile is a IO String type but is used here as [[Char]] type... and i don't know what to do... Ghc say me that is the lambda abstraction that fails with "map cons_line (lines s)" , he couldn't match IO against [] ! Help me please, i understand well (i hope) how Monad work but here i don't see a solution. Sorry for my poor english but i'm already a student. Thanks for all. -- C, socks and sun ;-) and haskell bugs :-( ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Read file problems
Hi, This is a pretty simple problem to fix. (>>=) has type IO a -> (a -> IO b) -> IO b. 'readFile my_file' has type IO String, so this means whatever comes on the RHS of >>= should have type (String -> IO b). In your case, it doesn't. It has type String -> [something], but the [something] isn't an IO type. Hint: you need to put a call to 'return' in there. - Hal On Mon, 2003-09-15 at 06:55, Frederic BELLOC wrote: > HI, > I have a recurrent probleme with function readFile and Monad : > it is that i try to get a line, transform it and stock it in a list > and what i want is that function return me the list. > But hugs say me that in > > readFile my_file >>= \s -> map cons_line (lines s) > readFile is a IO String type but is used here as [[Char]] type... > and i don't know what to do... > > Ghc say me that is the lambda abstraction that fails with > "map cons_line (lines s)" , he couldn't match IO against [] ! > > Help me please, i understand well (i hope) how Monad work but here i don't see > a solution. > > Sorry for my poor english but i'm already a student. > > Thanks for all. -- -- Hal Daume III | [EMAIL PROTECTED] "Arrest this man, he talks in maths." | www.isi.edu/~hdaume ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Read file problems
Hal Daume III <[EMAIL PROTECTED]> disait récemment : > Hi, > > This is a pretty simple problem to fix. (>>=) has type IO a -> (a -> IO > b) -> IO b. 'readFile my_file' has type IO String, so this means > whatever comes on the RHS of >>= should have type (String -> IO b). In > your case, it doesn't. It has type String -> [something], but the > [something] isn't an IO type. > > Hint: you need to put a call to 'return' in there. > Yes, thanks ps : i've read something like that in the Monad Tutorial but i was not sure... http://www.nomaware.com/monads/html/index.html -- C, socks and sun ;-) No haskell bug :-D ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: An IO Question from a Newbie
> > But there's one significant difference between C and > Haskell, which is > > applicable in the case of Matt's program. In C, any line-buffered > > output streams are automatically flushed when a read from an > > unbuffered or line-buffered stream can't be satisfied from > its buffer. > > Interesting. I didn't know this. Maybe we should match this > behaviour, or > provide a write-string-and-flush function. It seems like this issue > is causing an undue amound of trouble. I wrote GHC's IO library, and deliberately didn't include this feature. The previous version of the library did have such a feature, specifically for stdin/stdout. Note that the report doesn't say we must do this. The reason I didn't include the feature is because I can't see a way to do it right. Flushing *all* line-buffered handles (the ANSI C way) doesn't seem right. Flushing stdout just because we read from stdin is not right, because the two streams might refer to completely different I/O objects. Perhaps we should attempt to detect when there are two streams connected to the same I/O object (file, pipe, tty, whatever) and enable the magic flushing then. But now do I have to explain to people how this works? I suppose we could take the view that extra flushing is basically harmless, so it doesn't matter that we flush a bunch of Handles more often than we need to. The advantage of the current scheme is that it is easy to understand and explain; the library doesn't try to do clever stuff behind your back. The disadvantage is that it catches people out, and it sometimes requires you to import IO in an otherwise Prelude-only program. I'm more-or-less agnostic - if there's a way to avoid catching people out without introducing too much overhead or complicated rules that we have to explain, then I'll happily implement it. Cheers, Simon ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Instance checking and phantom types
Nick Name wrote: Hi all, I have an example wich I don't understand: First of all, let's rename the constructors and types a bit to make things clearer add the instance in question, and remove the type signatures: module Main where class C t data T = MkT instance C T instance C () data C t => T1 t = MkT1 f1 = MkT1 data C t => T2 t = MkT2 t f2 = MkT2 () Then we can easily ask GHC: [EMAIL PROTECTED]:~> ghci -v0 Main.hs *Main> :i T1 MkT1 f1 T2 MkT2 f2 -- T1 is a type constructor, defined at Main.hs:8 data (C t) => T1 t = MkT1 -- MkT1 is a data constructor, defined at Main.hs:8 MkT1 :: forall t. T1 t -- f1 is a variable, defined at Main.hs:10 f1 :: forall t. T1 t -- T2 is a type constructor, defined at Main.hs:12 data (C t) => T2 t = MkT2 t -- MkT2 is a data constructor, defined at Main.hs:12 MkT2 :: forall t. (C t) => t -> T2 t -- f2 is a variable, defined at Main.hs:14 f2 :: T2 () The first function, f1, is accepted both by hugs and ghc, unlike the second wich is rejected. Why does this happen? Shouldn't f1 be rejected with "no instance C ()" The reason is buried in http://haskell.org/onlinereport/decls.html#sect4.2.1 In a nutshell: The context in datatype declarations has only an effect for the *data* constructors of that type which use the type variables mentioned in the context. Contexts have no effect for the *type* constructor. IIRC the reason for this design decision was that contexts in type signatures should always be explicit. Cheers, S. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Instance checking and phantom types
Alle 20:07, lunedì 15 settembre 2003, Sven Panne ha scritto: > IIRC the > reason for this design decision was that contexts in type signatures > should always be explicit. Got it ;) Thanks for prompt reply. What does "should always be explicit" mean? Is there a notion of "explicit context" that I should know? Thanks Vincenzo ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
simpler I/O buffering [was: RE: An IO Question from a Newbie]
I've long thought that I/O buffering behavior--not just in Haskell, but
in most places I've encountered it--was unnecessarily complicated.
Perhaps it could be simplified dramatically by treating it as strictly a
performance optimization. Here's a sketch of the approach.
Writing a sequence of characters across the interface I'm proposing is a
request by the writing program for those characters to appear at their
destination "soon". Ideally, "soon" would be "immediately"; however, the
characters' appearance may deliberately be delayed ("buffered"), for
efficiency, as long as such delay is "unobtrusive" to a human user of the
program. Buffering timeouts would depend on the device; for a terminal,
perhaps 50-100 ms would be appropriate. Such an interval would tend not
to be noticeable to a human user but would be long enough to effectively
collect, say, an entire line of output for output "in one piece". The use
of a reasonable timeout would avoid the confusing behavior where a
newline-less prompt doesn't appear until the prompted data is entered.
With this scheme, I/O buffering no longer has any real semantic content.
(In particular, the interface never guarantees indefinite delay in
outputting written characters. Line buffering, if semantically important,
needs to be done above the level of this interface.) Hence, buffering
control could be completely eliminated from the interface. However, I
would retain it to provide (non-semantic) control over buffering. The
optional buffer size currently has such an effect. A timeout value could
be added for fine tuning. (Note that a timeout of zero would have an
effect similar to Haskell's current NoBuffering.) Lastly, the "flush"
operation would remain, as a hint that it's not worth waiting even the
limited timeout period before endeavoring to make the characters appear.
Is such an approach feasible? Has it been implemented anywhere? Would
such behavior best be implemented by the operating system? Could it be
implemented by the runtime system?
Dean
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Instance checking and phantom types
Nick Name wrote: Got it ;) Thanks for prompt reply. What does "should always be explicit" mean? Is there a notion of "explicit context" that I should know? What I meant was the fact that you always have to write down *all* contexts involved in a type signature. Nothing is "inherited under the hood" by contexts in datatype declarations. Cheers, S. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: threaded red-black tree
Carl Witty writes: | On Sun, 2003-09-14 at 21:48, Lex Stein wrote: | > Hi, No one responded to my question several weeks ago about a purely | > functional implementation of a threaded, red-black tree. | | I'm not sure what you mean by "threaded". By simply ignoring that word, | I come up with the following solution :-) IIRC a threaded tree (in an imperative language) is one where 'unused' child pointers are made to point to the next (right child pointer) or previous (left child pointer) node in an in-order traversal. The pointers have to be flagged to show whether they're normal or threading. For example, if this tree R / \ L S \ M were threaded, the unused pointers would be pressed into service thus: L's left: still nil, because L is the least element M's left: thread to L (predecessor) M's right: thread to R (successor) S's left: thread to R (predecessor) S's right: still nil, because S is the greatest element A benefit of threading is that you can make an in-order traversal in constant space, because you don't have to remember the whole path from the root to your current position. You *could* translate it into a purely functional representation, along these lines data TRBT a = Empty | Node Colour (Ptr a) a (Ptr a) data Colour = Red | Black data Ptr a = Child (TRBT a) | Thread (TRBT a) but you'd have to do some tricky stuff http://haskell.org/hawiki/TyingTheKnot to deal with the circular nature of the data structure (e.g. in the above tree, R points to L, L points to M, and M points to R). Also note that every insert or delete is O(n) instead of O(log n), because *every* node in the old tree can see the part you change. I suggest you (Lex) either go imperative (with STRef or IORef) or do without threading, unless you're sure that you'll be doing many more lookups and traversals than inserts and deletes. Regards, Tom ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: simpler I/O buffering [was: RE: An IO Question from a Newbie]
Dean Herington wrote:
> I've long thought that I/O buffering behavior--not just in Haskell, but
> in most places I've encountered it--was unnecessarily complicated.
> Perhaps it could be simplified dramatically by treating it as strictly a
> performance optimization.
This isn't entirely possible; there will always be situations where it
matters as to exactly when and how the data gets passed to the OS. My
experience taught me that the simplest solution was never to use ANSI
stdio buffering in such situations.
> Here's a sketch of the approach.
>
> Writing a sequence of characters across the interface I'm proposing is a
> request by the writing program for those characters to appear at their
> destination "soon". Ideally, "soon" would be "immediately"; however, the
> characters' appearance may deliberately be delayed ("buffered"), for
> efficiency, as long as such delay is "unobtrusive" to a human user of the
> program. Buffering timeouts would depend on the device; for a terminal,
> perhaps 50-100 ms would be appropriate. Such an interval would tend not
> to be noticeable to a human user but would be long enough to effectively
> collect, say, an entire line of output for output "in one piece". The use
> of a reasonable timeout would avoid the confusing behavior where a
> newline-less prompt doesn't appear until the prompted data is entered.
>
> With this scheme, I/O buffering no longer has any real semantic content.
> (In particular, the interface never guarantees indefinite delay in
> outputting written characters. Line buffering, if semantically important,
> needs to be done above the level of this interface.)
That's already true, at least in C: if you output a line which is
longer than the buffer, the buffer will be flushed before it contains
a newline (i.e. the line won't be written atomically).
> Hence, buffering
> control could be completely eliminated from the interface. However, I
> would retain it to provide (non-semantic) control over buffering. The
> optional buffer size currently has such an effect. A timeout value could
> be added for fine tuning. (Note that a timeout of zero would have an
> effect similar to Haskell's current NoBuffering.) Lastly, the "flush"
> operation would remain, as a hint that it's not worth waiting even the
> limited timeout period before endeavoring to make the characters appear.
>
> Is such an approach feasible?
Possibly.
As things stand, anyone who writes code which relies upon output being
held back until a flush is asking for trouble. So, your approach
wouldn't make it any harder to write correct code, although it might
make it significantly more obvious if code was incorrect.
AFAICT, the biggest problem would be providing an upper bound on the
delay, as that implies some form of preemptive concurrency.
> Has it been implemented anywhere?
Not that I know of.
> Would such behavior best be implemented by the operating system?
No. The OS (i.e. kernel) doesn't know anything about user-space
buffering. Furthermore, one of the main functions of user-space
buffering is to minimise the number of system calls, so putting it
into the OS would be pointless.
> Could it be implemented by the runtime system?
It depends what you mean by "the runtime system"; it would have to be
implemented in user-space.
--
Glynn Clements <[EMAIL PROTECTED]>
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
