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
