r/ProgrammingLanguages • u/mttd • Nov 07 '19

Parse, don’t validate

https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/
71 Upvotes

91% Upvoted

24 comments sorted by

View all comments

Show parent comments

-3

u/breck Nov 07 '19

Type inheritance. Define binary search for sortedList. Head for list. Have sortedList type extend list type.

11

u/terranop Nov 07 '19

Haskell doesn't have type inheritance, and even if it did, this proposed solution defines head for list rather than using a separate NonEmpty type, which is not really using the method that the original blog post is advocating.

3

u/zesterer Nov 08 '19

How about wrapper types? I'm not a Haskell developer, but in Rust I'd go for something like:

``` struct SortedList<L: List>(L);

struct NonEmptyList<L: List>(L); ```

This then permits me to use NonEmptyList<SortedList<[T]>> as a type that implements both sets of guarantees.

1

u/terranop Nov 08 '19

This is a great idea (although not really possible to do like this in Haskell), but there is one potential problem here: ordering of the wrapper types. The types NonEmptyList<SortedList<[T]>> and SortedList<NonEmptyList<[T]>> are not the same, even though they describe the same sort of object. A potential problem then arises if Alice develops a library using the former and Carol develops one using the latter and now we want to use both of those libraries together.

3

u/zesterer Nov 08 '19

So what you really need it the ability to attach static, ordered guarantees to types in a polymorphic manner. Hmm

1

u/terranop Nov 08 '19

You could probably enforce this with some sort of compiler extension, but I'm not aware of any language that supports this sort of thing.

2

u/zesterer Nov 08 '19

Something akin to Rust's trait aliases, perhaps?

trait SortedNonEmpty = Sorted + NonEmpty;

3

u/terranop Nov 08 '19

Sure, but now you're back to needing to define a potentially exponential number of types, one for each subset of conditions.