Hello again,
Another thought..
Could it be that sTree0 is cyclic that accounts for this dramatic slow down? I'm not to sure how DiffArray are implemented, but if it's how I would do it it seems you would end up with a massive chain of indirections.
Possible. It is possible to get an O(n) slowdown by using DiffArrays, but only if you index the original array after making updates to it. If you use the array in a single-threaded way, then indexing should be O(1) and additionally update should be O(1) compared to O(n) for ordinary arrays. It's possible that your use of array here is being implemented as a sequence of updates, which will lead to highly suboptimal behaviour:
sTree0 :: STree sTree0 = STree (array (0,9) [(n,(sTree0,[]))| n <- [0..9]])
I haven't checked the DiffArray implementation, though (it would be nice if someone could investigate DiffArray and fix any perf problems they find). Cheers, Simon