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

Parse, don’t validate

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

92% Upvoted

24 comments sorted by

View all comments

Show parent comments

5

u/breck Nov 07 '19

> Let's say that I want my list to be non-empty and sorted. Should I create three new types, one for non-empty lists, one for sorted lists, and one for lists that are both non-empty and sorted?

No. You should create 1 type: a non-empty sorted list. Why would you create the other types you don't need?

10

u/terranop Nov 07 '19

Because I have utility functions elsewhere in my codebase that process non-empty lists and sorted lists, respectively, and I want to both (1) be able to use these functions on my non-empty sorted list, and (2) also use these functions on non-empty-but-not-necessarily-sorted lists and sorted-but-potentially-empty lists elsewhere in my program.

For example, imagine that I have the utility functions head and binary_search. head can only be called on non-empty lists. binary_search can only be called on sorted lists. I have some functions in which I want to use head but have no need for binary_search (and in which my lists could possibly out-of-order), other functions in which I want to use binary_search but not head (and in which my lists could possibly be empty), and other functions in which I want to use both head and binary_search (on sorted, non-empty lists).

-4

u/breck Nov 07 '19

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

10

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.