SAFE: a Foldable proposal

[Thomas Tuegel]

On Fri, Feb 26, 2016 at 12:26 AM, Kosyrev Serge
<_deepfire at feelingofgreen.ru> wrote:
> Thomas Tuegel <ttuegel at gmail.com> writes:
>> On Thu, Feb 25, 2016 at 3:32 PM, Kosyrev Serge
>> <_deepfire at 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.