Re: [Haskell-cafe] Re: OCaml list sees abysmalLanguage Shootoutresults
In general only specific *code* can be compiled more efficiently.
I disagree - If GHC optimised as much as is _possible_ the code would be as fast and use as little memory as hand coded 'C'
It can't be transparent. A different type for semi-packed strings,
Again I disagree... I dont see why you cannot change the "implementation" of lists without changing the "interface"... Good old lists will behave like good old lists - just the implementation would try and take advantage of blocking of the data wherever possible. Perhaps a pragma to change the implementation of lists would ne be a sensible way of selecting the implementation. If a clever way of encoding the node-size (for large cells) is used, then it would be no slower than normal list code... One way of doing this would be to only change the format of cells where the next link is null (IE the end of the list)... In this case normal cells would be encoded _exactly_ as they are at the moment (so no slowdown or increase in memory usage) - to encode a large cell, the next pointer is null, and then an extra data structure determines if this really is the end of the list, or if infact it is a large cell (so we need an item count, and a _real_ next cell link, plus the data block) Keean.
At some point in the past, someone's attribution was stripped from:
It can't be transparent. A different type for semi-packed strings,
On Fri, Oct 08, 2004 at 07:28:53PM +0100, MR K P SCHUPKE wrote:
Again I disagree... I dont see why you cannot change the "implementation" of lists without changing the "interface"... Good old lists will behave like good old lists - just the implementation would try and take advantage of blocking of the data wherever possible.
Keith's point regarding sharing is a crucial counterexample to this proposed transparency. On Fri, Oct 08, 2004 at 07:28:53PM +0100, MR K P SCHUPKE wrote:
Perhaps a pragma to change the implementation of lists would ne be a sensible way of selecting the implementation. If a clever way of encoding the node-size (for large cells) is used, then it would be no slower than normal list code... One way of doing this would be to only change the format of cells where the next link is null (IE the end of the list)... In this case normal cells would be encoded _exactly_ as they are at the moment (so no slowdown or increase in memory usage) - to encode a large cell, the next pointer is null, and then an extra data structure determines if this really is the end of the list, or if infact it is a large cell (so we need an item count, and a _real_ next cell link, plus the data block)
I'd be fine with an alternative data type supporting e.g. packing and perhaps O(lg(n)) (!!) and (++) (if I get my wishes wrt. choices of data structures to implement it). The packing semantics are the crucial bit that probably makes this awkward to do in idiomatic Haskell, but there are probably low-level GHC extensions or possibly even standardized low-level operations I'm not aware of that make such feasible to implement as just a Haskell library. Someone more cognizant of those things should probably chime in here for my benefit, as my interest in this is such that I'd be willing to, say, write my own. -- wli
MR K P SCHUPKE wrote: [...]
I dont see why you cannot change the "implementation" of lists without changing the "interface"... Good old lists will behave like good old lists - just the implementation would try and take advantage of blocking of the data wherever possible.
Perhaps a pragma to change the implementation of lists would ne be a sensible way of selecting the implementation.
A phrase of the form "an X to change the implementation of Y" makes me think of X="instance" and Y="a class". Something along these lines: class List l a | l -> a where nil :: l cons :: a -> l -> l But that's not of much use, because there isn't a class method to recover the elements of a List. We could add more methods (corresponding to null, head, and tail), but perhaps it would be neater if class members could be data constructors? import Prelude hiding (null, head, tail) import Data.PackedString class List l a | l -> a where -- note the capital letters in Nil and Cons Nil :: l Cons :: a -> l -> l instance List PackedString Char where -- construction Nil = nilPS Cons = consPS -- pattern matching; not sure of a good syntax for this, -- but try reusing the reserved word 'case' as a function name case ifNil ifCons ps = if nilPS ps then ifNil else ifCons (headPS ps) (tailPS ps) -- cf. Prelude.maybe, Prelude.either instance List [a] a where -- construction Nil = [] Cons = (:) -- pattern matching case ifNil ifCons [] = ifNil case ifNil ifCons (x:xs) = ifCons x xs null :: (List l a) => l -> Bool null Nil = True null _ = False head :: (List l a) => l -> a head (Cons x _) = x tail :: (List l a) => l -> l tail (Cons _ xs) = xs Here are a few more questions which I'm not (yet) qualified to answer: Would such a language extension be messy to implement? Or would it perhaps fit neatly with current dictionary-passing schemes? Would there be other major uses for it, besides a class of list-shaped things? (Remember the first message in the "OCaml list sees..." thread? Part of the cited text was "Haskell strings are lists of characters [...] It's annoying that strings aren't normally processed this way in OCaml". I, like other posters, wonder whether Haskell could get the best of both worlds.) Does Template Haskell, which I haven't studied yet, already do something equivalent? Regards, Tom
participants (3)
-
MR K P SCHUPKE -
Tom Pledger -
William Lee Irwin III