[Haskell-cafe] ADT patch/update

Sergey Mironov ierton at gmail.com
Sat Aug 7 16:54:48 EDT 2010

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!


More information about the Haskell-Cafe mailing list