ADT patch/update

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

ADT patch/update

Sergey Mironov
Hi Cafe. I am searching for materials on one data type-related problem.
Suppose we have version control system storing values of user-defined algebraic
data type. 'User' (actually, programmer) wants to store his/her data and later
update it by applying patches.

By patch I mean value of some (another) type representing one simplest update
of stored value.

Say, for tree type

> data Tree a = Node (Tree a) (Tree a) | Leaf a

one may write

> {-# LANGUAGE TypeFamilies #-}
> {-# LANGUAGE UndecidableInstances #-}
>
> class Storable a where
>     type Patch a :: *
>     update :: Patch a -> a -> a
>
> data TreeStep = Left | Right -- Like in zippers ?
> type family Location a :: *
> type instance Location (Tree a) = [TreeStep]
>
> instance (Storable a) => Storable (Tree a) where
>     type Patch (Tree a) = (Location (Tree a), Patch a)
>     update = ... -- Move to specific location and call node's update

Patch here is coded explicitly but I guess there may be some generic way of it
to calculate. Whether any similar work has been carried out?
Will be glad to read comments!

--
Thanks,
Sergey
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ADT patch/update

Stephen Tetley-2
Maybe this paper is close?

Type-safe diff for families of datatypes
Eelco Lempsink Sean Leather Andres Löh
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ADT patch/update

Sergey Mironov
2010/8/8 Stephen Tetley <[hidden email]>:
> Maybe this paper is close?
>
> Type-safe diff for families of datatypes
> Eelco Lempsink Sean Leather Andres Löh
>

Thanks a lot! Just what I need.. and more trickier than I thought.
They represent any ADT as a tree and use diff algorithm for trees to
build 'EditScripts' - list of operations to transform src data to dest
one.

--
Sergey
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ADT patch/update

Nathan Howell-2
There is an existing implementation on hackage:

http://hackage.haskell.org/packages/archive/gdiff/1.0/doc/html/Data-Generic-Diff.html

On Thu, Aug 12, 2010 at 11:45 AM, Sergey Mironov <[hidden email]> wrote:

> 2010/8/8 Stephen Tetley <[hidden email]>:
>> Maybe this paper is close?
>>
>> Type-safe diff for families of datatypes
>> Eelco Lempsink Sean Leather Andres Löh
>>
>
> Thanks a lot! Just what I need.. and more trickier than I thought.
> They represent any ADT as a tree and use diff algorithm for trees to
> build 'EditScripts' - list of operations to transform src data to dest
> one.
>
> --
> Sergey
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe