Re: SAFE: a Foldable proposal

On Fri, Feb 26, 2016 at 12:26 AM, Kosyrev Serge <_deepfire@feelingofgreen.ru> wrote:

Thomas Tuegel writes:

...

On Thu, Feb 25, 2016 at 3:32 PM, Kosyrev Serge <_deepfire@feelingofgreen.ru> wrote:

...

What about adding unstructural fold/traversal under different names?

That way we could have the convenience when we truly don't care about the directionality property, and the benefits of pure folding at the same time.

That's a good idea, but I don't think it really changes anything. The chief problem with types that aren't structurally ordered is really that there are multiple valid orders. For example, if [a] is our canonical structurally-ordered type, there are at least two obvious ways to write f :: Ord a => Set a -> [a]. I don't think an unstructured version of Foldable has much benefit over simply converting the improper type to a proper one.

Just off the top of my head -- efficiency? Or is that overhead imaginary?

I don't think there's a significant efficiency concern here. The list example should be subject to fusion, i.e. the intermediate list would never actually be constructed. Even if we were concerned about the fusion rules failing to fire, we could always define a simple iterator type which is perfectly well ordered with practically no overhead.