Defining Data Structures/ Types In Haskell

Question

How would it possible to define a data structure in Haskell, such that there are certain constraints/rules that apply to the elements of the structure, AND be able to reflect this in the type.

For example, if I have a type made up of a list of another type, say

r = [x | x <- input, rule1, rule2, rule3].

In this case, the type of r is a list of elements of (type of x). But by saying this, we loose the rules. So how would it be possible to retain this extra information in the type definition.

To give more concreteness to my question, take the sudoko case. The grid of sudoko is a list of rows, which in turn is a list of cells. But as we all know, there are constraints on the values, frequency. But when one expresses the types, these constraints don't show up in the definition of the type of the grid and row.

Or is this not possible?

thanks.

In some cases, GADTs can help. Dependent types could do everything, but they are not supported in Haskell (and they require a non trivial effort from the programmer). — chi
– chi, Commented May 9, 2016 at 13:01
"require non-trivial effort" - the effort required to get a correct program is constant. The choice is where the effort manifests: in the type you declare, in the implementation you write, or just in your head. Of course the last variant is the least re-usable. — d8d0d65b3f7cf42
– d8d0d65b3f7cf42, Commented May 9, 2016 at 15:01

Glubus · Accepted Answer · 2016-05-09 12:31:09Z

In the example of a sodoku, create a data type that has multiple constructors, each representing a 'rule' or semantic property. I.E.

data SodokuType = NotValidatedRow | InvalidRow | ValidRow

Now in some validation function you would return an InvalidRow where you detect a validation of the sodoku rules, and a ValidRow where you detect a successful row (or column or square etc). This allows you to pattern match as well.

The problem you're having is that you're not using types, you're using values. You're defining a list of values, while the list does not say anything about the values it contains.

Note that the example I used is probably not very useful as it does not contain any information about the rows position or anything like that, but you can define it yourself as you'd like.

Collectives™ on Stack Overflow

Defining Data Structures/ Types In Haskell

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related