headers
Simon Peyton-Jones | 1 Mar 2004 12:33
Picon
Favicon
Gravatar

RE: Per-type function namespaces (was: Data.Set whishes)

| > In Haskell today, you can at least tell what value is bound to each
| > identifier in the program, *without* first doing type checking.
| 
| I'm afraid I'm confused. In the following code
| 
| > data Z
| > data S a
| >
| > class Card c where c2int:: c -> Int
| >
| > instance Card Z where c2int _ = 0
| > instance (Card c) => Card (S c) where c2int _ = 1 + c2int
(undefined::c)
| >
| > foo = c2int (undefined::(S (S (S (S Z)))))
| 
| how can one tell the value of foo without first doing the
| typechecking? 

What I meant was that you can always tell what executable code a value
is bound to, without type checking.  'foo' is bound to the code for
'c2int (undefined::(S (S (S (S Z)))))'. 
'c2int' is bound to code that extracts a method from it's first argument
(which is a dictionary for Card).

In any higher-order language, a function might invoke one of its
arguments
	f x g = g x
but I still say that it's clear what code is executed when f is called!
(Continue reading)

Permalink | Reply | 0 comments |
headers
Koji Nakahara | 1 Mar 2004 13:44
Picon

Incremental Array update (Re: performance tuning Data.FiniteMap)

Hi,

Reading the recent discussions abount Array and FiniteMap, 
I want to know what people think about the current specification of the Array update.

The Array implementaton of GHC effectively has this property (like FiniteMap):
	(arr // cs1) // cs2 == arr // (cs1 ++ cs2) -- allow duplicate indices

Because (//) copies a whole array and slow, instead of the successive updates, I usually accumulate those
changes to a list as many as I can in advance, and then give it to (//).
As far as GHC is concerned, all we have to do is to concatenate the list of changes by (++) thanks to the
propety.  It generally results in a huge performance inprovement.

However, 
Haskell Report reads (16.2):
> (As with the array function, the indices in the association list must be unique for the updated elements to
be defined.) 
So, we must somehow (as oleg's add_uniq[1]) remove the preceding elements having the same index from the
list 
to make the program comply Haskell 98 and support Hugs since Hugs does implement that check.  The
preconditioning (and also the check performed by the runtime system) causes no small amount of
performance hit.

I think it would be better if the above property of incremental updates of Array
is guaranteed sometime hopefully in Haskell 2.

Note:
0) Array give us O(1) read.
1) FiniteMap has the same property.
2) Array is more convenient than monadic arrays, e.g. STArray.
(Continue reading)

Permalink | Reply | 4 comments |
headers
Wolfgang Jeltsch | 1 Mar 2004 21:08

System.Random

Hello,

why is the Random module situated under System?  Wouldn't something like Data 
be more adequate?

Wolfgang
Permalink | Reply | 0 comments |
headers
ajb | 2 Mar 2004 02:32
Favicon
Gravatar

Re: Re: performance tuning Data.FiniteMap

G'day all.

Quoting oleg <at> pobox.com:

> 	If indeed the read performance is at premium and updates are
> infrequent, by bother with ternary etc. trees -- why not to use just a
> single, one-level array. Given a reasonable hash function, the
> retrieval performance is O(1).

Ah, but key comparison and computing the hash function is _not_ an O(1)
operation for keys of non-fixed-size.  At the very least, it's O(k) where
k is the length of the key.  If you have a perfect hash function, and you
know that you are not searching for elements which are not in the set,
hash searching will take precisely one scan through the whole key.

Radix searching, on the other hand, only needs to scan through as much of
the key as is necessary to discriminate between them.  Plus, even if you
need to search for keys which are not in the set, it takes at most one
pass through the key, as opposed to at least two for hashing.

If constant factors matter, and your keys are appropriately decomposable,
I would recommend radix searching over hashing any day.

Cheers,
Andrew Bromage
Permalink | Reply | 0 comments |
headers
S. Alexander Jacobson | 2 Mar 2004 04:08

Re: performance tuning Data.FiniteMap

On Fri, 27 Feb 2004 oleg <at> pobox.com wrote:
> 	If indeed the read performance is at premium and updates are
> infrequent, by bother with ternary etc. trees -- why not to use just a
> single, one-level array. Given a reasonable hash function

Because updates are not so infrequent that I want
to pay the cost of replicating the entire array
every update (or every ten!).  I'm willing to
exchange *some* read time for faster update. Also,
because small array copies may be sufficiently
faster than tree traversals that I may pay very
little extra for faster reads.

FYI, my current code looks like this:

  type HTArray base elt = Array base (HT base elt)
  data HT base elt = HT (Maybe (HTArray base elt)) (Maybe elt)
  data MyMap base key elt = ArrMap (HTArray base elt) (key->[base]) (HT base elt)

  newMap minBase maxBase toBase = ArrMap proto toBase emptyHT
	where
	proto= array (minBase,maxBase) [(x,emptyHT) | x<- [minBase..maxBase]]
	emptyHT=HT Nothing Nothing

  lookup (ArrMap _ toBase ht) key = lookup' ht $ toBase key
  lookup' (HT x y) [] = y
  lookup' (HT Nothing _) _ = Nothing
  lookup' (HT (Just ar) _) (k:ey) = lookup' (ar!k) ey

  insert (ArrMap proto toBase ht) key elt = ArrMap proto toBase newHT
(Continue reading)

Permalink | Reply | 668 comments |
headers
Bernard James POPE | 2 Mar 2004 05:11
Picon
Picon

Announce: buddha version 1.1

Announcing buddha version 1.1 
-----------------------------

www.cs.mu.oz.au/~bjpop/buddha

New in this release:

   - support for GHC 6.2 
   - better user interface
   - many bug fixes

--------------------------------------------------------------------------

A declarative debugger for Haskell 98. It is based on program
transformation and works with GHC 5.x and 6.x.

buddha offers a declarative debugging algorithm and a browsing mechanism.
It is useful for finding logical errors in programs and for exploring 
computations in a high-level manner.

Version 1.1 is known to work on GNU/linux (x86). It _ought_ to work 
on any unix-like system including Mac OS X, and freeBSD.

It does not work on Windows (as far as I know).

buddha is released under the GPL license.

Enjoy!
Bernie.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Alastair Reid | 2 Mar 2004 10:52
Picon

Re:

Koji Nakahara argues that // should behave as follows

    (arr // cs1) // cs2 == arr // (cs1 ++ cs2) -- allow duplicate indices

His argument that this is what his app (and, no doubt,m others) needs is quite 
convincing - it would be useful to have an operation that behaves this way.

However, I think there's also a strong argument for having operations that 
reports an error given duplicate indices.  

Maybe we can have both sets of operations?  This could be done either using 
two separate Array types or by having two variants of a few of the array ops.

--
Alastair Reid   haskell-consulting.com
Permalink | Reply | 3 comments |
headers
Simon Marlow | 2 Mar 2004 13:32
Picon
Favicon

RE: System.Random


> why is the Random module situated under System?  Wouldn't 
> something like Data be more adequate?

There is usually an external source of randomness, which is why the
library in placed in System rather than Data.  A purely functional
random library would be rather less useful...

Cheers,
	Simon
Permalink | Reply | 3 comments |
headers
Jerzy Karczmarczuk | 2 Mar 2004 13:47
Picon
Favicon

Re: System.Random

Simon Marlow wrote:
>  
>>why is the Random module situated under System?  Wouldn't 
>>something like Data be more adequate?
>  
> There is usually an external source of randomness, which is why the
> library in placed in System rather than Data.  A purely functional
> random library would be rather less useful...

Now, I don't understand this at all...

All the development of the Random stuff in all languages has nothing
of random whatsoever. Perhaps *some* people like to seed the generator
with the clock time, but most *real* developers *known to me* usually choose
the seed deterministically, in order to reproduce the sequence, until
the program is ready to run in the end-user environment.

Anyway, conceptually, the behaviour of random generators is very far from
any "external source of randomness", so the question 'why "System"' for
me remains valid. The module Random might of course use Time or similar
entities for the randomization/initialization, but this is a contingency.

Jerzy Karczmarczuk
Permalink | Reply | 2 comments |
headers
Wolfgang Jeltsch | 2 Mar 2004 14:16

Re: System.Random

Am Dienstag, 2. März 2004 13:47 schrieb Jerzy Karczmarczuk:
> Simon Marlow wrote:
> >>why is the Random module situated under System?  Wouldn't
> >>something like Data be more adequate?
> >
> > There is usually an external source of randomness, which is why the
> > library in placed in System rather than Data.  A purely functional
> > random library would be rather less useful...
>
> Now, I don't understand this at all...
>
> All the development of the Random stuff in all languages has nothing
> of random whatsoever. Perhaps *some* people like to seed the generator
> with the clock time, but most *real* developers *known to me* usually
> choose the seed deterministically, in order to reproduce the sequence,
> until the program is ready to run in the end-user environment.
>
> Anyway, conceptually, the behaviour of random generators is very far from
> any "external source of randomness", so the question 'why "System"' for
> me remains valid. The module Random might of course use Time or similar
> entities for the randomization/initialization, but this is a contingency.
>
> Jerzy Karczmarczuk

Yes.  My question was based on the fact that most of the stuff in Random has 
really nothing to do with the system.  The main random stuff is purely 
functional.  Things like getStdGen are rather nice additions to the core 
stuff.

Wolfgang
(Continue reading)

Permalink | Reply | 1 comment |

Gmane