July 2002 - Glasgow-haskell-users

RE: comparison of execution speed of array types
by Zdenek Dvorak 20 Jan '03

20 Jan '03

Hello, >DiffArray seems to be broken :). Either that or I'm using it >incorrectly. I've attached the relevant code, but when I don't reverse >the array everything works fine; when I reverse it the program doesn't >(seem to) halt. I've tried to use DiffArray recently and it is terribly slow. I was forced to write my own version (it is a bit faster, but still nothing great). My suspicion about the result of your measuring is that it does the updates in reversing the array one by one, thus leading to quadratic behavior. Zdenek Dvorak _________________________________________________________________ Chat with friends online, try MSN Messenger: http://messenger.msn.com

2 1

mergesort. Reply
by Serge D. Mechveliani 21 Oct '02

21 Oct '02

Ketil Z. Malde <ketil(a)ii.uib.no> writes > I'll hereby argue for using a quicksort implementation akin to > >> sortBy' _ [] = [] >> sortBy' pc (x:xs) = let (l,e,g) = part3 (`pc` x) xs >> in sortBy' pc l ++ (x:e) ++ sortBy' pc g >> where >> part3 comp xs = p3 [] [] [] comp xs >> p3 ls es gs _ [] = (ls,es,gs) >> p3 ls es gs comp (x:xs) = case comp x of >> LT -> p3 (x:ls) es gs comp xs >> EQ -> p3 ls (x:es) gs comp xs >> GT -> p3 ls es (x:gs) comp xs > > (hopefully this is fairly bug-free) At least for my data (lots of > values, limited range), it appears to speed things up tremendously. I > haven't measured more general cases in any detail, though. And one > obvious drawback may be that it's not stable, which I think can be > alleviated by a few well placed 'reverse's. > > Comments welcome! But sortBy' (compare) [1 .. n] costs too much, even for n = 11000. It costs (on worst data) many times more than mergeSort. ----------------- Serge Mechveliani mechvel(a)botik.ru

8 11

Lazy bind...
by MR K P SCHUPKE 05 Aug '02

05 Aug '02

Is there any way to do a lazy bind operation, something like a <- $ getLine return (Constructor $ a) this works for computations in the IO monad :- a <- unsafeInterleaveIO getLine return (Constructor $ a) but I need to do this for a general monad M. Keean Schupke Department of Electrical & Electronic Engineering, Imperial College London.

5 8

RE: infixed implicit parameters
by Simon Peyton-Jones 02 Aug '02

02 Aug '02

Reasonable suggestion, and not hard to implement. Definitions are more troublesome. Currently implicit parameter bindings must be of the form ?x = e I.e. no pattern-matching, function defintions etc. Changing this would be quite a bit more work. One could imagine a) status quo b) allow infix application, but keep binding syntactically restricted c) allow arbitrary binding forms (pattern matching etc) I think (b) is defensible; I don't think (c) is worth the work. But I would prefer to do (b) in sync with Hugs. Let's see what they think. Simon | -----Original Message----- | From: Hal Daume III [mailto:hdaume@ISI.EDU] | Sent: 23 July 2002 18:38 | To: GHC Users Mailing List | Subject: infixed implicit parameters | | | in the cannonical sort with implicit params, i we write | something like: | | mySort :: (?cmp :: a -> a -> Ordering) => [a] -> [a] | mySort [] = [] | mySort (x:xs) = insert x (mySort xs) | where insert x [] = [x] | insert x (y:ys) | | ?cmp x y == GT = y : insert x ys | | otherwise = x : y : ys | | but we cannot write for the second-to-last line: | | x `?cmp` y | | or | | x ?`cmp` y | | any chance this will be changed (my preference would be for | the first one. | | - hal | | -- | Hal Daume III | | "Computer science is no more about computers | hdaume(a)isi.edu | than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users(a)haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-| haskell-users |

2 1

"ignoring polymorphic case..."
by Hal Daume III 31 Jul '02

31 Jul '02

I'm getting the WARNING: ignoring polymorphic case in interpreted mode. Possibly due to strict polymorphic/functional constructor args. Your program may leak space unexpectedly. warning in GHCi (5.04). I'm used to getting this when I have a datatype with strict arguments, but the only data type I have in this module (and it doesn't import any of my own modules) is: newtype GArray s key elt = GA ((STRef s (Int, STArray s Int (key, elt)))) should I be worried? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1

RE: "ignoring polymorphic case..."
by Simon Marlow 31 Jul '02

31 Jul '02

> WARNING: ignoring polymorphic case in interpreted mode. > Possibly due to strict polymorphic/functional constructor args. > Your program may leak space unexpectedly. > > warning in GHCi (5.04). I'm used to getting this when I have > a datatype > with strict arguments, but the only data type I have in this > module (and > it doesn't import any of my own modules) is: > > newtype GArray s key elt = GA ((STRef s (Int, STArray s Int > (key, elt)))) > > should I be worried? These might also crop up as a result of using seq. Don't be worried unless you are using seq on purpose to avoid space leaks or to force (unsafe) I/O to happen. The warning essentially means that the seq is being ignored by GHCi because of an implementation wibble. Cheers, Simon

1 0

RE: STUArrays for Pairs
by Simon Marlow 31 Jul '02

31 Jul '02

> > it seems to me that if you have > > > > instance MArray (STUArray s) a (ST s) > > > > and > > > > instance MArray (STUArray s) b (ST s) > > > > you should be able to have > > > > instance MArray (STUArray s) (a,b) (ST s) > > > > by simply keeping two arrays with identical bounds, one > holding as and one > > holding bs, and then when you lookup, you lookup in each > individually and > > pair. > > > > i'd like to write such an instance, but have no idea where > to start...any > > pointers? > > It's a little bit more difficult, but possible. Have a look > at I'll confess I haven't looked into your stuff in any great detail, but I'm wondering whether Hal's idea can be achieved without any extra machinery. Here's my best shot; it's not entirely satisfactory because there's an extra dummy type parameter to the STUPairArray type constructor, and you need -fallow-undecidable-instances, but it seems to do the job: module PairArray where import Data.Array.Base import Control.Monad.ST data STUPairArray a b s i t = STUPairArray (STUArray s i a) (STUArray s i b) instance HasBounds (STUPairArray a b s) where bounds (STUPairArray left right) = bounds left instance (MArray (STUArray s) a m, MArray (STUArray s) b m) => MArray (STUPairArray a b s) (a,b) m where newArray (l,u) (a,b) = do lft <- newArray (l,u) a rgt <- newArray (l,u) b return (STUPairArray lft rgt) unsafeRead (STUPairArray lft rgt) i = do a <- unsafeRead lft i b <- unsafeRead rgt i return (a,b) unsafeWrite (STUPairArray lft rgt) i (a,b) = do unsafeWrite lft i a unsafeWrite rgt i b Cheers, Simon

2 1

RE: question about RealWorld and realWorld#
by Simon Marlow 31 Jul '02

31 Jul '02

> Am I right in saying that the type constructor > RealWorld is special to the compiler in that it is not defined in > any Haskell code but wired in? Yes, it is a primitive type, albeit a very special one. RealWorld is only used to instantiate the type parameter of the State# type constructor (another primitive type) in the IO monad and in runST. > Am I also correct is saying that the identifier realWorld# is > similar in > that it isn't defined in any Haskell code, but is primitive > to the compiler? Yes. > I would have expected to find something like: > > realWorld# :: State# s > realWorld# = undefined There isn't really a way to define the value of realWorld# in Haskell. Think of realWorld# as a constant of type State# RealWorld. > My instinctive feeling is that GHC treats State# objects > specially, so that > they only live at compile time but are not present at > runtime. This is mentioned > in the "Lazy functional state threads" paper: > > "By the time the program reaches the code generator, the > role of the state > values is over, and the code generator arranges to > generate no code at all > to move around values of type State#" (page 13 in my > version of the paper). They are "almost invisible" at runtime. For example, there must still be a difference between a function of type 'State# s -> a' and a value of type 'a', although the argument doesn't have a value and doesn't use any registers. HTH, Simon

1 0

FiniteMap.keysFM
by Christian Maeder 31 Jul '02

31 Jul '02

Designers of FiniteMap and Set (it's me again), I wish "keysFM" would yield "Set key" rather than "[key]"! Could such an implementation take constant time (by simply ignoring "elts")? (Converting a list to a set and back will sort the list and thus may take more than linear time.) Cheers Christian

2 2

STUArrays for Pairs
by Hal Daume III 31 Jul '02

31 Jul '02

it seems to me that if you have instance MArray (STUArray s) a (ST s) and instance MArray (STUArray s) b (ST s) you should be able to have instance MArray (STUArray s) (a,b) (ST s) by simply keeping two arrays with identical bounds, one holding as and one holding bs, and then when you lookup, you lookup in each individually and pair. i'd like to write such an instance, but have no idea where to start...any pointers? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1