Mark Jones gives the following alternative definitions for Lists:

>     type List a b = b -> (a -> b -> b) -> b
>     nil           :: List a b
>     nil f g        =  f
>     cons          :: a -> List a b -> List a b
>     cons x xs f g  =  g x (xs f g)
>     fold           :: b -> (a -> b -> b) -> List a b -> b
>     fold z f xs     =  xs z f

A while ago I instrumented the Gofer interpreter (version 2.28a) to
 measure the number of G-machine instructions executed in evaluating
 an expression. I thought people might be interested in the difference
 in performance between this and the standard definition.

Using the standard definition, we get:

|       foldr (+) 0 [1,2,3,4]
|       10
|       (11 reductions, 76 instructions, 24 cells)

and using Mark's definition, we get:

|       fold 0 (+) (cons 1 (cons 2 (cons 3 (cons 4 nil))))
|       10
|       (11 reductions, 64 instructions, 29 cells)

which uses 20% more store but 15% fewer instructions.

Using appropriate definitions of enumFromTo to generate (and then sum)
lists of length 5000, the 15% fewer instructions seems to translate 
into about 10% less real time.

This makes me wonder why this definition isn't used in implementations.
Are people scared off by the strange looking definitions and the need
for strange-looking types inside the code generator? Or is the problem
the extra space use/ garbage collection/ or what?

Alastair Reid

Reply via email to