[Haskell-cafe] self-referential data

[wren ng thornton]

brian wrote:
>>From https://secure.wikimedia.org/wikipedia/en/wiki/Bencoding , I
> think I should code
> 
> data BValue = BString     String
>             | BInteger    Integer
>             | BList       [BValue]
>             | BDictionary (M.Map BString BValue)
> 
> but: Not in scope: type constructor or class `BString'
> 
> The implementations I've found just implemented BDictionary's map key
> as String, but I think that's kind of wrong.

Data Types a la Carte[1] seems like a good fit:

  > newtype BString     e = BString     String
  > newtype BInteger    e = BInteger    Integer
  > newtype BList       e = BList       [Bvalue]
  > newtype BDictionary e = BDictionary (M.Map (BString e) BValue)
  >
  > newtype Y f           = Y { unY :: f (Y f) }
  > data    (f :+: g)   e = Inl (f e) | Inr (g e)
  >
  > type BValue = Y (BString
  >              :+: BInteger
  >              :+: BList
  >              :+: BDictionary
  >               )

...with the necessary Functor instances. Or, since BString is the only 
member of the coproduct that needs special treatment, you could squash 
things a bit more:

  > newtype BString e = BString     String
  > data    BValue_ e = BInteger    Integer
  >                   | BList       [Bvalue]
  >                   | BDictionary (M.Map (BString e) BValue)
  >
  > type BValue = Y (BString :+: BValue_)

The former is more homogeneous and so would probably look prettier in 
code, but the latter is a bit more efficient since it needs less 
coproduct tagging and function indirection.

Of course, another approach is to just go with your first approach and 
doubly wrap String. So there's a newtype BString_ = BString_ String, and 
BValue has a constructor (BString BString_) and the dictionary uses the 
BString_ data type.


[1] With added discussion: 
http://wadler.blogspot.com/2008/02/data-types-la-carte.html

-- 
Live well,
~wren