Repository navigation
Make the DList type abstract #4
Description
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.
Activity
spl commentedon Nov 13, 2013
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
fromShowSandtoShowSshare the same problem as described above.basvandijk commentedon Nov 13, 2013
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
dstringI think it's sufficient to just remove thefromShowSfunction.spl commentedon Nov 14, 2013
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?I think I prefer
apply(because that is what the function intuitively does by being a replacement for$intoList) andtoFunction(because you can think of it as a conversion fromDList ato[a] -> [a]).basvandijk commentedon Nov 14, 2013
I like
apply.dag commentedon Nov 19, 2013
You actually can use
unDLto construct anyDList:The same is not true for
applybecause record selectors aren't first class. Thus, wheneverunDLis removed, this should not be done by renaming it toapply.spl commentedon Nov 19, 2013
Excellent point, @dag. Thanks!
Update to 0.6
jimstutt commentedon Apr 23, 2014
I found unDL in planar-graph and substituted apply. What is the preferred syntax? Tnx.
spl commentedon Apr 23, 2014
@jimstutt
unDLis 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 constructingDLists in this way goes around the expected isomorphism. Butapplycan replaceunDLin other situations. Does that help?jimstutt commentedon Apr 24, 2014
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 commentedon Oct 1, 2014
@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 commentedon Oct 2, 2014
Thanks dag. I'll have to revisit the code.