It's really cons lists that are harmful -- foldl and foldr are just ways to operate on them. GP's example would work fine with conc trees and a divide-and-conquer reduce instead.