1) Is there a more efficient definition of hyperseq that does not traverse the data structure twice? The "show" function traverses the structure once but I found it to be much slower.

persumably because it produces its output with (++), or with (.) and building up lots of closures (?) something like class Size s where size :: s -> Int would help. (or a class Hash ... - both are nice to have anyway in a program) (and automatic instance derivations for them would be nice as well...)

2) In this application the uses of lazy evaluation are rare and easily eliminated (zip xs [1..] and so on); is there some hidden GHC option that evaluates everything strictly? I realise that this would invalidate optimisations relying on certain laws but I just wonder how difficult this would be. Somebody must have given this a thought at one point.

It would also be interesting to find out what exactly the compiler is missing when translating your program. Ideally, it should be able to "see" that everything is strict. -- -- Johannes Waldmann, Tel/Fax: (0341) 3076 6479 / 6480 -- ------ http://www.imn.htwk-leipzig.de/~waldmann/ ---------

Arjan,

I supervise a student who uses Haskell for simulating neural nets. A lot of computation goes on there and the program cannot handle as many iterations as we would like. We have improved performance by a factor of more than ten by putting strictness annotations in all data types. But the problem is that there are lists within these data structures and they are not strict. By using a trick I have now found that making the whole program state strict the program gets a much better looking heap profile. The trick I use is by writing a function hyperseq and then applying it before the next iterations begins:

hyperseq x y = if x==x then y else error "this is very unlikely"

This is very expensive and I chose to apply the function only once every 100 iterations. This gives reasonable performance.

... 1) Is there a more efficient definition of hyperseq that does not traverse the data structure twice? The "show" function traverses the structure once but I found it to be much slower.

I hit a similar problem with my very first Haskell application! As you say, the brute solution of comparing structures for equality with themselves is very expensive, and may be wrong if some components really should be evaluated lazily. My solution was to introduce a single-method class class Norm a where normal :: a -> Bool The intention is that 'normal' functions are defined in such a way that the result of an application 'normal x' is always true, but computing this truth guarantees that x is evaluated to at least a desired minimal extent. For example, supppose we have data Tree a b = Branch (Tree a) a (Tree a) | Leaf b we might then define instance Norm (Tree a b) where normal (Leaf _) = True normal (Branch _ _ _) = True hiding the Leaf and Branch constructors and providing instead leaf :: Norm b => b -> Tree a b leaf x | normal x = Leaf x branch :: Tree a b -> b -> Tree a b -> Tree a b branch lt x rt | normal lt && normal rt = Branch lt x rt we obtain trees that are path-strict in the branch and leaf structure, do not interfere at all with the lazy evaluation of internal labels at branches but ensure 'normal' evaluation of leaf labels. Of course there are many other possible definitions of 'normal' for trees. All sorts of clever tricks could be programmed into the normalising evaluations. But there should be no need for repeated traversals (let alone repeated double traversals, using ==) of already-evaluated structure. With a suitable instance of Norm, your hyperseq function can be redefined hyperseq :: Norm a => a -> b -> b hyperseq x y | normal x = y Regards Colin R Reference: Colin Runciman, "Tip in Haskell -- another exercise in functional programming", pp 278-292 in Proc. 1991 Glasgow Workshop on Functional Programming, Springer-Verlag, 1992.