More on dictionaries

[Simon L Peyton Jones <simonpj@cs.glasgow.ac.uk>]

To: Mark.Jones@prg.oxford.ac.uk
Cc: haskell@cs.glasgow.ac.uk
Subject: More on dictionaries
Date: Fri, 01 Mar 91 12:12:05 +0000
From: Simon L Peyton Jones <simonpj@cs.glasgow.ac.uk>
Sender: haskell-request@cs.glasgow.ac.uk


Replies to Mark's replies.

Simon

 
| Firstly, Simon points out that the Glasgow compiler translates my example:
| 
| |     example x []     = False
| |     example x (p:ps) = p==(x,'c') || example x ps
| 
| to give:
| 
| |     example d = example'
| |                  where
| |                  example' x [] = False
| |                  example' x (p:ps) = (==) d1 p (x,'c') || example' x ps
| |                  d1 = dictEqPair d dictEqChar
| 

(Note from Simon: I've swapped the dashes over in this code, to make
the following less confusing.)

| which certainly doesn't cause the problem of repeated construction of the
| dictionary d1 that I described.  My original translation was based on the
| approach taken in the type classes paper,
| rather than the more sophisticated
| translation scheme described in "A static semantics of Haskell".
| 
| However, I do not think that sophisticated 
| translation schemes can completely
| eliminate repeated construction of dictionaries, even using the program
| transformations that Simon describes.  
| As an example, consider the expression:
| 
|                        map (example x) zs
| 
| Surely (please correct me if I'm wrong) this will still entail the repeated
| construction of d1 for each element in the list zs?


Absolutely not!  The expression translates to

	map (example actual_d x) zs

for some suitable dictionary actual_d.  The expression in the
brackets is shared lazily between all applications to each elt of
zs.  It is a redex, because (example actual_d) reduces to

	example' where example' = ....
		       d1 = ...

Hence the d1 is shared between all applications of the function being 
mapped.

Here's a simpler example of the same thing:

	map (f 3 4) zs
	where
	f x = g where g y = d1+y
		      d1 = x*2

x is only squared once!



| Finally, at the risk of changing the direction of this discussion, I am
| rather puzzled by the idea that it would be easier to apply strictness
| analysis to:
| 
| |   map f xs = map' xs where map' [] = []
| |                            map' (x:xs) = f x : map' xs
| 
| rather than the original definition of map.  Whilst I can see that the
| definition of map' takes only a first-order argument, surely we still
| need to account for the abstract value of f in finding the abstract
| value of map' ... which seems to lead us straight back to the problem
| we started with.  Could somebody enlighten me please?


Certainly.  But you don't need to find the *fixpoint* of a function with
functional arguments, which is the expensive part.