[Haskell-cafe] reversing big list with constant heap space used
How to solve task of reversing big list with constant heap space used? Amount of heap space used grows exponentially in following examples: 1: main = putStrLn.show.head $reverse [1..1000] 2 (GHC): import Data.List main = putStrLn.show.head $foldl' (flip (:)) [] [1..1000] 3 (GHC): import Control.Monad main = foldM (\x y - return $ y:x) [] [1..1000] = putStrLn.show.head -- Best regards, Sergey Perminov ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: The danger of Monad ((-) r)
On Tue, May 15, 2007 at 06:55:11AM -0700, Conal Elliott wrote: You could also use mappend instead of concatStmts and keep the Database - IO () representation.- Conal You mean using the (Monoid b) = Monoid (a - b) instance ? I can see that IO () makes a perfect Monoid, but there doesn't seem to be a standard instance for that. Pozdrawiam Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type class help please
Adrian Hey wrote:
-- Instances of GT are instances of Eq --
instance (GT map key, Eq a) = Eq (map a) where
map1 == map2 = assocsAscending map1 == assocsAscending map2
...
Overlapping instances for Eq [(key, a)]
arising from use of `==' at Test.hs:10:16-59
Matching instances:
instance (Eq a) = Eq [a] -- Defined in GHC.Base
instance (GT map key, Eq a) = Eq (map a) -- Defined at Test.hs:9:0
How can my new instance overlap with the old (ghc) instance unless
[] is also an instance of GT for some key type (which it isn't).
Could someone explain?
You are right in your explanation of the GHC behavior. Your instance
|Eq (map a)| indeed overlaps the `standard` instance |Eq [a]|. The
overlap may be easier to see if we write [a] as ([] a), which is what
it is, an application of the type constructor [] to the type variable
a. So, the type [a] (aka [] a) is a particular instance of the type
(map a), with `map' being []. This is the overlapping that GHC is
complaining about.
Regarding the need for -fallow-undecidable-instance: GHC is not a
general purpose termination checker. Furthermore, it seems reasonable
for GHC to employ simple termination heuristics, which can be decided
quickly, syntactically and locally (that is, considering only the
instance in question, rather than collection of all instances in the
program). Thus GHC employs a set of heuristics that look if
the instance constraints are `smaller' than the instance head. That
will assure termination. That criterion is of course not complete, so
there are (many) terminating, decidable typeclass program that fail
simple GHC termination tests and thus require
-fallow-undecidable-instance extension.
One method of avoiding overlapping instances is to define a newtype
wrapper:
newtype MyMap map a = MyMap{unMyMap::map a}
class Ord key = GT map key | map - key where
assocsAscending :: map a - [(key,a)] -- Just 1 of many methods
instance GT (MyMap Data.IntMap) Int where ...
The drawback is writing MyMap and unMyMap in many places. That spoils
the appearance, but rarely fatal.
Another solution is replacing the general instance
instance (GT map key, Eq a) = Eq (map a) where
map1 == map2 = assocsAscending map1 == assocsAscending map2
with its instantiations, for all `maps' in question:
instance Eq a = Eq (Data.IntMap a) where ...
instance Eq a = Eq (Data.Map key a) where ...
instance Eq a = Eq (Data.IntSet a) where ...
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Converting CTime - Int
On Wed, May 16, 2007 at 12:38:55AM -0400, Brandon S. Allbery KF8NH wrote: On May 16, 2007, at 0:35 , Rob Hoelz wrote: wrapping returns time_t. I see that this maps to CTime in Foreign.C.Types, but I can't figure out how to convert it to an Int (or any other useful Haskell type, for that matter) for the life of me. I've poured over the standard library docs, but to no avail. Could someone give me a hint? It's an instance of Enum, so use fromEnum to create an Int. (Don't feel too bad, it took me an embarrasingly long amount of time to figure that out as well; before that I used read . show :) I'm not sure it's a good idea - in theory, Int can have fewer bits than CTime. I wonder why CTime is not Integral - maybe there is no such guarantee for time_t? If so, then you shouldn't rely on Enum. The safest bet seems to be toRational - CTime is Real. Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: The danger of Monad ((-) r)
Tomasz Zielonka wrote: On Tue, May 15, 2007 at 06:55:11AM -0700, Conal Elliott wrote: You could also use mappend instead of concatStmts and keep the Database - IO () representation.- Conal You mean using the (Monoid b) = Monoid (a - b) instance ? I can see that IO () makes a perfect Monoid, but there doesn't seem to be a standard instance for that. Indeed, all Monads are Monoids (that is, if m :: * - * is a Monad, then m a :: * is a Monoid, for any fixed type a) by using . MonadPlusses have a Monoid structure at each particular fixed type, using mplus, but it's not the same one in all but the most trivial case. E.g: Prelude System.IO Control.Monad Just 3 Nothing Nothing Prelude System.IO Control.Monad Just 3 `mplus` Nothing Just 3 The general point here is that an awful lot of things are Monoids, often in more than one way. There isn't a really elegant way to choose which instance you want, though. newtype hackery is one way to partition them, although it might be nicer (?) to have a more general notion of 'naming instances'. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: The danger of Monad ((-) r)
On Wed, May 16, 2007 at 09:28:31AM +0100, Jules Bean wrote: Tomasz Zielonka wrote: You mean using the (Monoid b) = Monoid (a - b) instance ? I can see that IO () makes a perfect Monoid, but there doesn't seem to be a standard instance for that. Indeed, all Monads are Monoids (that is, if m :: * - * is a Monad, then m a :: * is a Monoid, for any fixed type a) by using . Are you sure that (IO Int) is a monoid with mappend = ()? How do you define mempty, so it is an identity for mappend? It would help if type a was a Monoid, then: mempty = return mempty mappend mx my = do x - mx y - my return (x `mappend` y) It's easier if a = (). Regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: The danger of Monad ((-) r)
Tomasz Zielonka wrote: On Wed, May 16, 2007 at 09:28:31AM +0100, Jules Bean wrote: Tomasz Zielonka wrote: You mean using the (Monoid b) = Monoid (a - b) instance ? I can see that IO () makes a perfect Monoid, but there doesn't seem to be a standard instance for that. Indeed, all Monads are Monoids (that is, if m :: * - * is a Monad, then m a :: * is a Monoid, for any fixed type a) by using . Are you sure that (IO Int) is a monoid with mappend = ()? How do you define mempty, so it is an identity for mappend? It would help if type a was a Monoid, then: mempty = return mempty mappend mx my = do x - mx y - my return (x `mappend` y) It's easier if a = (). Oops, you're right. I spoke too fast. It's only a monoid for (). Otherwise you can't hope to have a right identity. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type class help please
Brandon S. Allbery KF8NH wrote: On May 16, 2007, at 0:57 , Adrian Hey wrote: -- GT class -- class Ord key = GT map key | map - key where assocsAscending :: map a - [(key,a)] -- Just 1 of many methods -- Instances of GT are instances of Eq -- Instances of Ord are instances of Eq, so defining your own instance Eq for a subclass of Ord causes confusion. Specifically, depending on how the value is used, the compiler may not be able to decide between the standard Eq instance or your added one. Don't do that. I don't think I understand. How would you suggest I make Eq instances from GT? AFAICS it won't happen automatically without something like this. Or are you saying they shouldn't be instances of Eq? Perhaps it should be done separately on each and every type that is made an instance of GT, as Oleg has suggested. That seems a little awkward as they will all be essentially identical. (I thought one of the advantages of type classes was to avoid this kind of repetition.) Thanks -- Adrian Hey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type class help please
[EMAIL PROTECTED] wrote: Adrian Hey wrote: -- Instances of GT are instances of Eq -- instance (GT map key, Eq a) = Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 ... Overlapping instances for Eq [(key, a)] arising from use of `==' at Test.hs:10:16-59 Matching instances: instance (Eq a) = Eq [a] -- Defined in GHC.Base instance (GT map key, Eq a) = Eq (map a) -- Defined at Test.hs:9:0 How can my new instance overlap with the old (ghc) instance unless [] is also an instance of GT for some key type (which it isn't). Could someone explain? You are right in your explanation of the GHC behavior. Your instance |Eq (map a)| indeed overlaps the `standard` instance |Eq [a]|. The overlap may be easier to see if we write [a] as ([] a), which is what it is, an application of the type constructor [] to the type variable a. So, the type [a] (aka [] a) is a particular instance of the type (map a), with `map' being []. This is the overlapping that GHC is complaining about. So if I understand correctly, it's complaining about a potential overlap, not an actual overlap (there is no actual overlap until [] is made an instance of GT AFAICS). Also, I suspect I'm still missing something important here, for example I don't understand why, if it overlaps for [], it doesn't overlap with other instances (like Maybe for example). Or am I just not getting the error for Maybe because ghc stops after the first error? Another solution is replacing the general instance instance (GT map key, Eq a) = Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 with its instantiations, for all `maps' in question: instance Eq a = Eq (Data.IntMap a) where ... instance Eq a = Eq (Data.Map key a) where ... instance Eq a = Eq (Data.IntSet a) where ... This seems like the more attractive option if my current approach is unworkable, but it seems strange that I should have to do this. Thanks -- Adrian Hey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Type class help please
Adrian Hey wrote: [EMAIL PROTECTED] wrote: Adrian Hey wrote: -- Instances of GT are instances of Eq -- instance (GT map key, Eq a) = Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 ... Overlapping instances for Eq [(key, a)] arising from use of `==' at Test.hs:10:16-59 Matching instances: instance (Eq a) = Eq [a] -- Defined in GHC.Base instance (GT map key, Eq a) = Eq (map a) -- Defined at Test.hs:9:0 How can my new instance overlap with the old (ghc) instance unless [] is also an instance of GT for some key type (which it isn't). Could someone explain? You are right in your explanation of the GHC behavior. Your instance |Eq (map a)| indeed overlaps the `standard` instance |Eq [a]|. The overlap may be easier to see if we write [a] as ([] a), which is what it is, an application of the type constructor [] to the type variable a. So, the type [a] (aka [] a) is a particular instance of the type (map a), with `map' being []. This is the overlapping that GHC is complaining about. So if I understand correctly, it's complaining about a potential overlap, not an actual overlap (there is no actual overlap until [] is made an instance of GT AFAICS). Also, I suspect I'm still missing something important here, for example I don't understand why, if it overlaps for [], it doesn't overlap with other instances (like Maybe for example). Or am I just not getting the error for Maybe because ghc stops after the first error? Ah, this brings me to something else I don't quite understand about this error, but kind of explains the absence of similar errors for Maybe. It's the arising from use of `==' at Test.hs:10:16-59 part. I don't understand why, but if I use.. -- Instances of GT are instances of Eq -- instance (GT map key, Eq a) = Eq (map a) where map1 == map2 = True ..the error goes away. So it's not objecting to such instances in general, but rather the specific use of == in the definition. So now I'm really confused. Why, if it's possible that this instance overlaps with another for [], does it make any difference whether or not I've used == in the definition? Surely, if there's any ambiguity about which instance of Eq to use for [] (should [] be made an instance of GT), then the ambiguity exists whether or not I've used == in the definition. Hmm.. Regards -- Adrian Hey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ANNOUNCE: Harpy -- run-time code generation library
Dirk Kleeblatt wrote: apfelmus wrote: Dirk Kleeblatt wrote: apfelmus wrote: I also think that having liftIO in the CodeGen-monad is plain wrong. I mean, CodeGen is a monad that generates code without any execution note that runCodeGen runs the code _generation_, executing the generated code is done _within_ the CodeGen monad via the functions generated by callDecl (or the predefined functions in the Harpy.Call module). This is even more intertwined, but intentional. Huh? That means that code gets executed during it's own generation? But why do you mix separate concerns? I don't see what use this is besides being an opportunity to mess up. One of our projects is a just-in-time compiler for a functional language. Here, compilation is done lazily: A starting stub is compiled and executed, when the execution reaches some point for which no code has been generated yet the next bit of code is compiled, and the program is resumed, and so on. So execution and code generation are interleaved. Another project is related to dependent type checking as described by Benjamin Grégoire and Xavier Leroy in [1]. Here, functions can occur in types, and the cited paper describes how these functions can be executed by compiled code. During type checking. So type checking, code generation, and execution are interleaved. Of course, again a different design is possible, making runCodeGen return a binary code object, that can be called from the IO monad. But then, the user has to care about releasing code buffers, and not to have unevaluated closures having code pointers to already released run-time generated code. Huh, why does the user have to care? Shouldn't wrapping the raw memory block into a Foreign.ForeignPtr do the job? Well, both projects manage a separate memory block which is used like a heap by generated code. This heap contains closures that have code pointers into generated code. And these are subject to our (not yet implemented... ;-) ) garbage collectors, not the Haskell collector. Ah, I think the memory organization issues are the driving force for liftIO in the CodeGen-monad, not the possibility to interleave code generation and execution. This is because you can always interleave code generation and execution with the binary code object-design as well like in do codeobject - runCodeGen code1 result - exec codeobject codeobject2 - runCodeGen (code2 result) result2 - exec codeobject2 ... Note that the generated second code may well depend on the result gained from executing the first. However, you currently don't want free-floating binary code objects because you want to manage memory yourself. In other words, you carry around a single-threaded memory agglomeration that contains code and data, i.e. you're working in a monad StateT Memory IO a because only that can guarantee that there exists only a single instance of the memory agglomeration. (In fact, you have to use IORefs but that's not essential). Still, I think that writing opcodes somewhere and memory managing this somewhere are separate concerns. I'd separate them by splitting the CodeGen monad into a monad (I'll call it Executor) over IO that threads the mentioned memory agglomeration and a data type that represents x86 assembly (hereby called Code). It is convenient to have Code being a monad too, but it's not necessary and conceptually wrong. Given this separation, you can support *both* designs simultaneously: - calling x86 assembly inside the Executor foo :: Code - Executor () foo code = do buf - newBuffer (size code) writeCode buf code exec buf freeBuffer buf - calling code from binary code objects bar :: Code - IO () bar code = do (f :: IO ()) - mkFunction code f The first one is for your intended applications. The second one is a simple way to outsource performance critical parts of a Haskell programs to assembly, something some people from this list are probably very interesting in. Last but not least, here are more details about Code and why it's not really a monad. The basic operation on Code is to glue two Code pieces together in sequence append :: Code - Code - Code In an assembly language without jumps, that's all about it besides primitive instructions like bite :: Code bark :: Code and so on. Thus, Code is at least a monoid. Now, jumps are what make Code special, we need a way to reference code positions, aka labels. Let's assume a primitive jump:: Label - Code One way is to base it on the following two operations append' :: Code - (Label - Code) - Code ccall :: (Label - Code) - Code The function append' supplies the position of it's first argument to the second so that the second can reference it. The function ccall supplies the position after the end of the code block to the code block itself, just like call with current continutation would do. The robodog example from last time then
Re: [Haskell-cafe] reversing big list with constant heap space used
On Wed, 16 May 2007, Sergey Perminov wrote: How to solve task of reversing big list with constant heap space used? By avoiding 'reverse'? Amount of heap space used grows exponentially in following examples: 1: main = putStrLn.show.head $reverse [1..1000] Data.List.last I think that in every particular case you have to find out how to avoid 'reverse'. Especially if you have two 'reverse's like in reverse . dropWhile p . reverse there are more efficient solutions. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] quiry
how to convert a hexadecimal into base 10 integer using haskell . I have written a code but its not working for large values , please help ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: quiry
On Wed, May 16, 2007 at 06:34:53PM +0530, ashutosh dimri [EMAIL PROTECTED] wrote a message of 34 lines which said: how to convert a hexadecimal into base 10 integer using haskell . I have written a code but its not working for large values , please help Not showing the code you wrote will not help. Please read the instructions first: http://www.haskell.org/haskellwiki/Homework_help ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] quiry
ashutosh dimri [EMAIL PROTECTED] writes: how to convert a hexadecimal into base 10 integer using haskell . I have written a code but its not working for large values , please help from http://pleac.sourceforge.net/pleac_haskell/numbers.html#AEN118 : -- read handles both octal and hexadecimal when prefixed with 0x or 0o -- here are versions adding the prefix and calling read hex s = read (0x ++ s) :: Integer oct s = read (0o ++ s) :: Integer -- hex 45 == 69 -- oct 45 == 37 -- hex 45foo = Exception: Prelude.read: no parse -- calling explicitly readHex or readOct: hex = fst . head . Numeric.readHex oct = fst . head . Numeric.readOct ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: problem with implicit parameter
Eric eeoam at ukfsn.org writes:
Hi there,
I've written the following program
putchr = putChar ?d
main = do
{ c - getChar
; putchr with ?d = c}
I think you're supposed to use a let binding, like this:
putchr :: (?d::Char) = IO ()
putchr = putChar ?d
main = do
c - getChar
let ?d = c
putchr
Best,
--
Grzegorz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Tail Recursion within the IO Monad
Hello everyone,
You may have seen my message about how I'm writing a binding to a C
library. This is another question related to that.
So, let's say I have a linked list implemented in C. Here's what its
definition looks like:
struct __linked_list {
void *data;
struct __linked_list *next;
};
typedef struct __linked_list linked_list_t;
void *linked_list_getdata(linked_list_t *);
linked_list_t *linked_list_next(linked_list_t *);
Keep in mind, this is just a segment.
So using the Haskell FFI, I import these into my .hsc file:
data LinkedList = LL (Ptr linked_list_t)
foreign import ccall unsafe linked_list.h
linked_list_getdata :: Ptr LinkedList - IO Ptr a
foreign import ccall unsafe linked_list.h
linked_list_next :: Ptr LinkedList - IO Ptr LinkedList
So now that that's done, I attempt to write a Ptr LinkedList -
[String] function (assuming the given LinkedList is holding c strings):
linkedListToStringList :: Ptr LinkedList - IO [String]
linkedListToStringList listPtr =
if listPtr == nullPtr
then
return []
else do
item - linked_list_getdata listPtr
next - linked_list_next listPtr
cStr - peek item
hStr - peekCString cStr
t - linkedListToStringList next
return (hStr : t)
This is just ugly...making the recursive call first, THEN consing the
value on? However, this is the only way I could think of doing it. I
figure there are three possibilities from here:
1) Leave this code alone, as GHC will optimize it because it's smart.
2) There's a way to more effectively write this code! Change it!
3) Roll my own optimization.
I know how to do 3, but I'd rather avoid it. I guess I'm looking for
an answer to 2, but if 1 is true, that'd be ok too. Could anyone give
me a hand?
And as long as I'm asking, is there some kind of monadic function
composition operator? I'd like to clean up the above with something
like peekCString . peek . linked_list_getdata...
Many thanks,
Rob Hoelz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tail Recursion within the IO Monad
On May 16, 2007, at 12:23 , Rob Hoelz wrote: And as long as I'm asking, is there some kind of monadic function composition operator? I'd like to clean up the above with something like peekCString . peek . linked_list_getdata... (=)? -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tail Recursion within the IO Monad
Brandon S. Allbery KF8NH [EMAIL PROTECTED] wrote: On May 16, 2007, at 12:23 , Rob Hoelz wrote: And as long as I'm asking, is there some kind of monadic function composition operator? I'd like to clean up the above with something like peekCString . peek . linked_list_getdata... (=)? Thanks for the reply; I can't believe I missed that one! But while looking over the documentation, completely humbled, I discovered sequence, which allows me to write my code cleanly! Thanks for the help! -Rob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] reversing big list with constant heap space used
On 16/05/07, Sergey Perminov [EMAIL PROTECTED] wrote: How to solve task of reversing big list with constant heap space used? I think that as lists are singly-linked in Haskell, reversing a list will always be O(n) space. -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Books on Haskell
Hi, Is Graham Hutton's book on Haskell Programming a good text for FP beginners? Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Books on Haskell
Hi Is Graham Hutton's book on Haskell Programming a good text for FP beginners? Yes. There is a review in The Monad Reader: http://www.haskell.org/sitewiki/images/0/03/TMR-Issue7.pdf From the abstract: Do we need another introductory Haskell book? Is there anything new to be said or a better approach to take? Graham Hutton thinks there is. I think he is right. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] quiry
Pixel wrote: from http://pleac.sourceforge.net/pleac_haskell/numbers.html#AEN118 : -- read handles both octal and hexadecimal when prefixed with 0x or 0o -- here are versions adding the prefix and calling read hex s = read (0x ++ s) :: Integer oct s = read (0o ++ s) :: Integer -- hex 45 == 69 -- oct 45 == 37 I want to remark that Integer does not necessarily use decimal internally; rumour goes that it is binary. But whatever it is, show turns that into decimal, e.g., show (hex 45) gives 69 indeed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Converting CTime - Int
On Wed, May 16, 2007 at 12:38:55AM -0400, Brandon S. Allbery KF8NH wrote: On May 16, 2007, at 0:35 , Rob Hoelz wrote: wrapping returns time_t. I see that this maps to CTime in Foreign.C.Types, but I can't figure out how to convert it to an Int (or any other useful Haskell type, for that matter) for the life of me. I've poured over the standard library docs, but to no avail. Could someone give me a hint? It's an instance of Enum, so use fromEnum to create an Int. (Don't feel too bad, it took me an embarrasingly long amount of time to figure that out as well; before that I used read . show :) 'fromInteger . round' is probably a better idea if you only need second accuracy, there is no guarentee that a time_t will fit in an Int, if you need subsecond accurancy, then realToFrac will convert it to a Float or Double, but I doubt any system that ghc supports provides such accuracy via CTime. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] reversing big list with constant heap space used
David House wrote: On 16/05/07, Sergey Perminov [EMAIL PROTECTED] wrote: How to solve task of reversing big list with constant heap space used? I think that as lists are singly-linked in Haskell, reversing a list will always be O(n) space. You can do it in O(n^2) time and constant space, by using repeated calls to (!!), in principle. In practice you need to be a bit tricky otherwise keeping the reference to the whole list around will stop the GC ever collecting it. You'd need to stream it rather carefully, and then it wouldn't actually be (!!) any more; just something 'like (!!)'. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tail Recursion within the IO Monad
Rob Hoelz wrote: item - linked_list_getdata listPtr next - linked_list_next listPtr cStr - peek item hStr - peekCString cStr t - linkedListToStringList next return (hStr : t) item - linked_list_getdata listPtr next - linked_list_next listPtr cStr - peek item hStr - peekCString cStr fmap (hStr :) linkedListToStringList next This is just ugly...making the recursive call first, THEN consing the value on? However, this is the only way I could think of doing it. I figure there are three possibilities from here: I think you're over-valuing tail recursion. It's not an exciting thing in a lazy language the way it is in a pure language. The change I made above may not result in particularly better code, although it is more concise. And as long as I'm asking, is there some kind of monadic function composition operator? I'd like to clean up the above with something like peekCString . peek . linked_list_getdata... Yes, that's what = and = are. hStr - peekCString = peek = linked_list_getdata listPtr fmap (hStr :) linkedListToStringList = linked_list_next listPtr ...or even... liftM2 (:) (peekCString = peek = linked_list_getdata listPtr) (linkedListToStringList = linked_list_next listPtr) It's really a matter of taste you could turn the arrows round, too. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] reversing big list with constant heap space used
I think that in every particular case you have to find out how to avoid 'reverse'. Especially if you have two 'reverse's like in reverse . dropWhile p . reverse there are more efficient solutions. Just from curiosity, what *is* an efficient way to do rDropWhile? Here's something which at least avoids 2 reverses: rDropWhile = doRDropWhile [] doRDropWhile accum f [] = [] doRDropWhile accum f (x:xs) | f x = doRDropWhile (x:accum) f xs | otherwise = reverse (x:accum) ++ doRDropWhile [] f xs I assume this is not in Data.List to discourage people from doing things to the right side of lists... it's still useful for string stuff where ByteString would be overkill though. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Imagining a G-machine
A native G-machine --- physical, or chemical, or biological, but not a repressed simulation over the imperative cpu-memory architecture --- is the dream of every lazy-functional programmer of great devotion. If only it became the dominant computing architecture! People would say, Haskell is high-level assembly because it is the closest to the bare metal (or bare protein) and still supports all sorts of abstractions. People would ask, why is my C program five times slower than Haskell, and people would answer, that's because C is compiled to a stack of seven monad transformers (one of which is ContT to support longjmp), and because you should use more linked lists and fewer arrays. We truely rule the world when C programmers have to consult us for performance tips. A necessary condition for dominance is existence. Here is my crazy imagination of a native G-machine. It is worded as biotech but may as well be molecular computing or nanotech. The heap is a soup of nutrients. A node is a molecular structure made from the nutrients. A thunk is a lot of nodes linked up. Nodes and thunks are suspended in the soup. Allocation means constructing nodes and links from nutrients, and deallocation means unlinking nodes and eventually dismantling them back into nutrients. As a side effect, memory upgrade is cheap and convenient: Just go buy a can of Campbell soup (my favourite is the alphabet soup) and pour into your heap. There are 24-hour convenient stores at every street corner --- pervasive computing has never been so pervasive before. A thunk is nodes linked together and suspended in the soup. A theorem in graph theory asserts that all finite graphs can be embedded without crossing edges in 3D space, and we take advantage of this to space out the nodes in a complicated thunk. Still, it is not easy, being NP-hard and all. There is a relaxation heuristic for this: It simply requires nodes to be a bit repulsive to each other and links to be elastic, and they will sort things out themselves. (When they don't, a bit of shaking up helps tremendously.) Evaluation is performed by a small organism crawling over a thunk and performing its thunk-rewriting duty as per the G-machine. It applies enzymes to construct and deconstruct nodes and links from nutrients. It performs primitive arithmetic on its own. It maintains its own stack, inside or outside its body (to be investigated). It is possible to unleash several such evaluators for parallel computing. It is possible to enable reproduction to boost parallelism. To add garbage collection, roots send out a periodic (or sustained) signal to all connected nodes. Nodes receiving the signal do not self-destruct. Nodes not receiving the signal invokes their built-in self-destruct mechanism to dissolve themselves back into nutrients. There may be better schemes. Interacting with the outside world is open, but Andrew Gordon's thesis contains translations from monadic I/O to other I/O schemes, e.g., continuations, streams, etc. Perhaps one of them can be adapted. Debugging can be done by making evaluators send radio signals concerning operations they perform; then a second computer can log these and you can review them. You can also use radio signals to instruct the evaluators to perform unusual operations on demand. The existence of a native G-machine is a necessary but not sufficient condition for world dominance. We still need to make it fast, compact, and cheap. There may also be better but totally different ways to realize a native G-machine. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Imagining a G-machine
On Wed, May 16, 2007 at 03:41:30PM -0700, John Meacham wrote: I look forward to the day when the OS will notice that a binary was compiled from haskell, and therefore is provably not buggy due to haskells strong type system. So it happily turns off all memory protection and lets it run on the bare hardware at full speed. :) This is not entirely unreasonable, operating systems with trusted compilers and typed assembly languages are active areas of research. But then GHC would be faster then JHC! (Nobody cares about jhc, certainly not enough to implement a recognizer for it...) Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Imagining a G-machine
On Wed, May 16, 2007 at 03:47:07PM -0700, Stefan O'Rear wrote: On Wed, May 16, 2007 at 03:41:30PM -0700, John Meacham wrote: I look forward to the day when the OS will notice that a binary was compiled from haskell, and therefore is provably not buggy due to haskells strong type system. So it happily turns off all memory protection and lets it run on the bare hardware at full speed. :) This is not entirely unreasonable, operating systems with trusted compilers and typed assembly languages are active areas of research. But then GHC would be faster then JHC! (Nobody cares about jhc, certainly not enough to implement a recognizer for it...) Ah, but think of how much faster jhc development would be if it didn't take ghc 20 minutes to compile it every time I made a change :) John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Imagining a G-machine
Hi It is worded as biotech but may as well be molecular computing or nanotech. biotech machines tend to be inaccurate, but highly parallel. Unfortunately the G machine is very un-parallel and requires 100% precision. Things like speculative evaluation may be more interesting. To add garbage collection, roots send out a periodic (or sustained) signal to all connected nodes. Nodes receiving the signal do not self-destruct. Nodes not receiving the signal invokes their built-in self-destruct mechanism to dissolve themselves back into nutrients. There may be better schemes. I think that in a novel machine you aren't going to want to do the traditional methods of garbage collection, or anything else. You'll probably need entirely new methods of doing entirely new things. Debugging can be done by making evaluators send radio signals concerning operations they perform; then a second computer can log these and you can review them. You can also use radio signals to instruct the evaluators to perform unusual operations on demand. It would also be a shame if for the G'-machine we have excellent debugging capabilities, but for normal Haskell on a normal computer we're stuck with Debug.Trace... Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Imagining a G-machine
Albert Y. C. Lai wrote: A native G-machine --- physical, or chemical, or biological, but not a repressed simulation over the imperative cpu-memory architecture --- is the dream of every lazy-functional programmer of great devotion. If only it became the dominant computing architecture! People would say, Haskell is high-level assembly because it is the closest to the bare metal (or bare protein) and still supports all sorts of abstractions. People would ask, why is my C program five times slower than Haskell, and people would answer, that's because C is compiled to a stack of seven monad transformers (one of which is ContT to support longjmp), and because you should use more linked lists and fewer arrays. We truely rule the world when C programmers have to consult us for performance tips. A necessary condition for dominance is existence. Here is my crazy imagination of a native G-machine. It is worded as biotech but may as well be molecular computing or nanotech. The heap is a soup of nutrients. A node is a molecular structure made from the nutrients. A thunk is a lot of nodes linked up. Nodes and thunks are suspended in the soup. Allocation means constructing nodes and links from nutrients, and deallocation means unlinking nodes and eventually dismantling them back into nutrients. As a side effect, memory upgrade is cheap and convenient: Just go buy a can of Campbell soup (my favourite is the alphabet soup) and pour into your heap. There are 24-hour convenient stores at every street corner --- pervasive computing has never been so pervasive before. A thunk is nodes linked together and suspended in the soup. A theorem in graph theory asserts that all finite graphs can be embedded without crossing edges in 3D space, and we take advantage of this to space out the nodes in a complicated thunk. Still, it is not easy, being NP-hard and all. There is a relaxation heuristic for this: It simply requires nodes to be a bit repulsive to each other and links to be elastic, and they will sort things out themselves. (When they don't, a bit of shaking up helps tremendously.) Evaluation is performed by a small organism crawling over a thunk and performing its thunk-rewriting duty as per the G-machine. It applies enzymes to construct and deconstruct nodes and links from nutrients. It performs primitive arithmetic on its own. It maintains its own stack, inside or outside its body (to be investigated). It is possible to unleash several such evaluators for parallel computing. It is possible to enable reproduction to boost parallelism. To add garbage collection, roots send out a periodic (or sustained) signal to all connected nodes. Nodes receiving the signal do not self-destruct. Nodes not receiving the signal invokes their built-in self-destruct mechanism to dissolve themselves back into nutrients. There may be better schemes. Interacting with the outside world is open, but Andrew Gordon's thesis contains translations from monadic I/O to other I/O schemes, e.g., continuations, streams, etc. Perhaps one of them can be adapted. Debugging can be done by making evaluators send radio signals concerning operations they perform; then a second computer can log these and you can review them. You can also use radio signals to instruct the evaluators to perform unusual operations on demand. The existence of a native G-machine is a necessary but not sufficient condition for world dominance. We still need to make it fast, compact, and cheap. There may also be better but totally different ways to realize a native G-machine. Amorphous computing (http://www-swiss.ai.mit.edu/projects/amorphous/), including biological computers (http://www-swiss.ai.mit.edu/~rweiss/bio-programming/), an application domain for pure FP (http://www.eecs.harvard.edu/~mdw/proj/mp/) ? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] CUFP website
cyril.schmidt: I noticed recently that the website of CUFP conference (Commercial Uses of Function Programming), which used to be at http://www.galois.com/cufp, is not accessible anymore. Does anybody know where it moved? Try http://cufp.galois.com/ -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: Dimensional 0.4 -- Statically checked physical dimensions
Dear all, I am pleased to announce version 0.4 of Dimensional (working name). Dimensional is a library providing data types for performing arithmetic with physical quantities and units. Information about the physical dimensions of the quantities/units is embedded in their types and the validity of operations is verified by the type checker at compile time. The boxing and unboxing of numerical values as quantities is done by multiplication and division with units. The library is designed to, as far as is practical, enforce/encourage best practices [1] of unit usage. Since the previous formal announcement [2] (version 0.1) Dimensional has gone through several structural and stylistic improvements but usage remains fundamentally unchanged. Noteworthy changes are a vastly solidified 'NumType' module, a complete(?) set of elementary functions and a 'Prelude'-replacement for users' convenience. There is also an experimental 'Extensible' module supporting user-defined dimensions. Additional structural changes and additions (primarily of units) are planned and the library will continue to have an unstable API until the 1.0 release. However, apart from module reshuffling no changes are anticipated that would break user code. Additional information and code is available from the project web site [3]. Thank you, Bjorn Buckwalter [1] http://physics.nist.gov/Pubs/SP811/ [2] http://www.haskell.org/pipermail/haskell/2006-December/018993.html [3] http://code.google.com/p/dimensional/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Type class help please
Also, I suspect I'm still missing something important here, for example I don't understand why, if it overlaps for [], it doesn't overlap with other instances (like Maybe for example). Or am I just not getting the error for Maybe because ghc stops after the first error? One may think of instances as denoting sets of types that satisfy them. For example, instance Eq a = Eq [a] denotes list types, whose elements are themselves members of Eq. Likewise, Eq (map a) denotes all those types that are constructed by the application of something to something else. For example, [a], Maybe Int, Either a b all satisfy whereas Int does not. Normally the sets of types denoted by all the instances in a class must be disjoint. That is, given a type, one can always find an instance it is a member of -- or fail. GHC however checks for overlapping lazily. GHC does not immediately report that the set of types (i.e., the extension) of one instance is a proper subset of the extension of another instance in the class. One should note that if two extensions are identical, this is a duplicate instance error. If two instance extensions have non-empty overlap but one does not fully include the other, that is an incurable overlapping error. GHC reports an error if, during typechecking of an expression, it tries to find the instance a type is a member of -- and finds two such instances. If GHC is never prompted to search for instances for such a type, no error is reported in that particular program. The original message gives an example of that: instance (GT map key, Eq a) = Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 I don't understand why, but if I use.. -- Instances of GT are instances of Eq -- instance (GT map key, Eq a) = Eq (map a) where map1 == map2 = True ..the error goes away. The function `assocsAscending' returns the list [(key,a)] pairs. So, to compile the operation assocsAscending map1 == assocsAscending map2 GHC needs to figure out how to compare lists for equality. So, GHC needs to find an Eq instance that includes the type [(key,a)]. And there it finds two such instances, Eq [a] and Eq (map a). Hence the error. GHC is not asked to compare two Maybe values in that code, hence it does not report overlapping there. Once you define map1 == map2 = True GHC no longer needs to know how to compare lists -- and so the overlapping error went away. Incidentally, Hugs reports the overlapping errors eagerly. It would still complain about the changed code, because the error is with instances rather with their use. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
