Make the DList type abstract

[spl]

DList a is isomorphic to [a] via fromList/toList, but [a] -> [a] is not isomorphic to [a]. That is, all lists are dlists, and all dlists are lists only if there is no way to construct a y :: DList a from an "unsafe" x :: [a] -> [a].

Currently, the library exports the constructor DL and deconstructor unDL which allows the construction of unsafe dlist values. Consider this GHCi session:

*Data.DList> let x = DL $ \z -> z ++ z
*Data.DList> toList x
[]
*Data.DList> fromList $ toList x
Data.DList.fromList []

The values of x and toList x are clearly not isomorphic. When used:

*Data.DList> append x (singleton 'a')
Data.DList.fromList "aa"
*Data.DList> append (fromList $ toList x) (singleton 'a')
Data.DList.fromList "a"

DList was abstract early on. I don't know why it was changed.

To preserve the isomorphism, I think DList should be an abstract type and the constructor and deconstructor should be removed from the export list.

[spl]

I did a quick search of Hackage to see which packages are using DL/unDL. The only one I came up with was dstring.

@basvandijk What do you think about this? Your fromShowS and toShowS share the same problem as described above.

[basvandijk]

Good point. Lets make DList abstract.

However I think we can keep the export of unDL. You can't use it to create unsafe DLists.

With regards to dstring I think it's sufficient to just remove the fromShowS function.

[spl]

True, only the constructor is unsafe, not the deconstructor, so we can still use unDL. However, I think a more descriptive name would be suitable. How about one of the following?

apply          :: DList a -> [a] -> [a]
undlist
toList'
toListFunction
toListFun
toFunction
fromDList

I think I prefer apply (because that is what the function intuitively does by being a replacement for $ in toList) and toFunction (because you can think of it as a conversion from DList a to [a] -> [a]).

[basvandijk]

I like apply.

[dag]

You actually can use unDL to construct any DList:

x = empty { unDL = \z -> z ++ z }

The same is not true for apply because record selectors aren't first class. Thus, whenever unDL is removed, this should not be done by renaming it to apply.

[spl]

Excellent point, @dag. Thanks!

[jimstutt]

I found unDL in planar-graph and substituted apply. What is the preferred syntax? Tnx.

[spl]

@jimstutt unDL is no longer available as a record selector (a.k.a. field). It can no longer be used in a “setter” way, e.g. DL { unDL = ... }. This is not allowed because constructing DLists in this way goes around the expected isomorphism. But apply can replace unDL in other situations. Does that help?

[jimstutt]

It was @dag's comment "Thus, whenever unDL is removed, this should not be done by renaming it to apply." which prompted me to ask. I'll just use apply.

[dag]

@jimstutt Sorry for the late response here, but anyway: what I meant was that when unDL is removed from the dlist package itself it's not enough to simply rename the record field and export the new name, because record fields can be used as setters, and can be used to break module boundaries otherwise imposed by private constructors. My remark was not meant to say anything about code using the dlist package. Hope that clears it up!

[jimstutt]

Thanks dag. I'll have to revisit the code.