[Haskell-cafe] Sparse records/ADTs

Twan van Laarhoven twanvl at gmail.com
Wed Oct 24 17:10:22 CEST 2012


On 24/10/12 12:08, Jon Fairbairn wrote:
>
> Is there a convenient way of handling a data structure with lots
> of fields of different types that may or may not be filled in?
>

Not sure about convenience, but here is a type safe solution with O(log n) 
lookups and updates. The idea is to define a GADT tree type with a fixed layout:

     -- define the structure
     type MyT = TBranch (TLeaf A) (TBranch (TLeaf B) (TLeaf C))
     -- a value level tree that uses that structure
     type My  = GTree MyT

You still have to define the paths to the members

     pa = GL GH
     pb = GR (GL GH)
     pc = GR (GR GH)

But once you have that you can perform lookups and updates:

     *Main> glookup pc (gupdate pa (Just A) (gupdate pc (Just C) gempty))
     Just C

It shouldn't be too hard to make a template haskell function that generates 
these paths. Or perhaps the corresponding lenses.


Twan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2012-10-24-sparse-typed-tree.hs
Type: text/x-haskell
Size: 1422 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121024/2f3ded31/attachment.hs>


More information about the Haskell-Cafe mailing list