[Haskell-cafe] Any precedent or plan for guaranteed-safe Eq and Ord instances?

[Ryan Newton]

Tillmann,

Thanks, that is in interesting use case for handwritten Generics.

I'm not fully dissuaded though, simply because:

(1) it can't be too common!  Especially when you intersect the people who
have done or will do this with the people who care about SafeHaskell.
 (Again, if they don't, they won't mind this tiny Unsafe toggle.)

(2) even people who fall in this intersection still have the recourse of
doing what they need to do and asserting "TrustWorthy".  SafeHaskell is
good at supporting this kind of individual exception.

Whereas in my case I have no recourse!  Because my problem not about
asserting that a particular module is TrustWorthy, but rather about keeping
other users (running in -XSafe) from breaking my library.



On Sun, Oct 6, 2013 at 6:54 PM, Tillmann Rendel <
rendel at informatik.uni-marburg.de> wrote:

> Hi,
>
>
> Ryan Newton wrote:
>
>> It is very hard for me to
>> see why people should be able to make their own Generic instances (that
>> might lie about the structure of the type), in Safe-Haskell.
>>
>
> I guess that lying Generics instances might arise because of software
> evolution. Let's say we start with an abstract data type of binary trees.
>
>   module Tree (Tree, node, empty, null, split) where
>     data Tree a = Node (Tree a) (Tree a) | Empty
>       deriving Generics
>
>     node = Node
>
>     empty = Empty
>
>     null Empty = True
>     null _ = False
>
>     split (Node a b) = (a, b)
>
>     size Empty = 0
>     size (Node x y) = size x + size y
>
> Note that this data type is not really abstract, because we export the
> Generics instance, so clients of this module can learn about the
> implementation of Tree. This is not a big deal, because the chosen
> implementation happens to correspond to the abstract structure of binary
> trees anyway. So I would expect that generic code will work fine. For
> example, you could use generic read and show functions to serialize trees,
> and get a reasonable data format.
>
> Now, we want to evolve our module by caching the size of trees. We do
> something like this:
>
>   module Tree (Tree, node, empty, null, split) where
>     data Tree a = Tree !Int (RealTree a)
>
>     data RealTree a = Node (Tree a) (Tree a) | Empty
>
>     tree (Node a b) = Tree (size a + size b) t
>     tree Empty = Tree 0 Empty
>
>     node x y = tree (Node x y)
>
>     empty = tree Empty
>
>     null (Tree _ Empty) = True
>     null _ = False
>
>     split (Tree _ (Node a b)) = (a, b)
>
>     size (Tree n _) = n
>
> Except for the Generics instance, we provide the exact same interface and
> behavior to our clients, we just traded some space for performance. But
> what Generics instance should we provide? If we just add "deriving
> Generics" to the two datatypes, we leak the change of representation to our
> clients. For example, a client that serialized a tree with a generic show
> function based on the old Tree cannot hope to deserialize it back with a
> generic read function based on the new Tree. The size information would be
> missing, and the structure would be different.
>
> If we write a Generics instance by hand, however, I guess we can make it
> present the exact same structure as the derived Generics instance for the
> old Tree. With this lying instance, the generic read function will happily
> deserialize the old data. The size will be computed on the fly, because our
> hand-written Generics instance will introduce calls to our smart
> constructors.
>
>
>   Tillmann
> ______________________________**_________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20131007/5290783a/attachment.htm>