Is there any way to parametrize a type by a value, rather than another type? What I would like to do is to define "list of length 3" and "list of length 4" as separate parametrization of the same type, such that I could write functions that accept lists (under my new typename) of any length as long as parameters have the same length. The goal is to remove the need for runtime checks all over the code. Konrad.
On Tue, 5 Aug 2003 12:23:06 +0200
Konrad Hinsen
3
Is there any way to parametrize a type by a value, rather than another type? What I would like to do is to define "list of length 3" and "list of length 4" as separate parametrization of the same type, such that I could write functions that accept lists (under my new typename) of any length as long as parameters have the same length. The goal is to remove the need for runtime checks all over the code.
This is called "dependent types" and is not a feature of haskell (nor of any language that I know); there was "cayenne" (try a google search) but I don't believe it is still mantained. BTW, why is there no general interest for such a thing as dependent types? V.
On Tuesday, 2003-08-05, 15:22, CEST, Nick Name wrote:
[...]
Is there any way to parametrize a type by a value, rather than another type? What I would like to do is to define "list of length 3" and "list of length 4" as separate parametrization of the same type, such that I could write functions that accept lists (under my new typename) of any length as long as parameters have the same length. The goal is to remove the need for runtime checks all over the code.
This is called "dependent types" and is not a feature of haskell (nor of any language that I know); there was "cayenne" (try a google search) but I don't believe it is still mantained.
Well, there are, e.g., Ada and C++ which allow types to be parametrized by values. The point is that they obviously still use runtime checks, it's just that you don't have to code these checks explicitely.
BTW, why is there no general interest for such a thing as dependent types?
What negative consequences does their implementation have? I think, sometimes they could be quite handy.
V.
W. ;-)
On Tue, 5 Aug 2003 15:30:44 +0200
Wolfgang Jeltsch
What negative consequences does their implementation have? I think, sometimes they could be quite handy.
That you have to solve a constraint system to compile your program, AFAIK. But I guess that a brave GHC user should not be afraid of waiting at compile-time ^_____^ V. -- Teatri vuoti e inutili potrebbero affollarsi se tu ti proponessi di recitare te [CCCP]
On Tuesday, 2003-08-05, 12:23, CEST, Konrad Hinsen wrote:
Is there any way to parametrize a type by a value, rather than another type?
No, there isn't.
What I would like to do is to define "list of length 3" and "list of length 4" as separate parametrization of the same type, such that I could write functions that accept lists (under my new typename) of any length as long as parameters have the same length. The goal is to remove the need for runtime checks all over the code.
There probably are ways to achieve this with Haskell's type system. The exact solution depends on what exactly you want. For just distinguishing between lists of different lengths you could use tuples like (a,a) (list of length 2) (a,a,a) (list of length 3) etc. A better solution might be: data EmptyList element = EmptyList data TrueList list element = TrueList element (list element) A list of four Ints for example would be represented by a value of type TrueList (TrueList (TrueList (TrueList EmptyList))) Int. You could define different types for different natural numbers: data Zero = Zero data Succ number = Succ number and do simple arithmetic with them at the type level: class Sum a b c | (a, b) -> c instance Sum 0 a a instance Sum a b c => Sum (Succ a) b (Succ c) At the moment, I cannot think of a way of defining a list type which is parameterized by such natural types. What I mean is having a type List :: * -> * -> * where for our above example of a list of four Ints we would have the type List (Succ (Succ (Succ (Succ Zero)))) Int What I can think of, is an association between our above list types (EmptyList and TrueList) and our natural number types by a multi-parameter class: class HasLength list length | list -> length instance HasLength EmptyList Zero instance HasLength list length => HasLength (TrueList list) (Succ length) It would be interesting to know if/how you could, e.g., define a concatenation function with a type like (Sum length1 length2 length, HasLength list1 length1, HasLength list2 length2, HasLength list length) => list1 -> list2 -> list.
Konrad.
Wolfgang
On Tuesday 05 August 2003 15:23, Wolfgang Jeltsch wrote:
There probably are ways to achieve this with Haskell's type system. The exact solution depends on what exactly you want.
For just distinguishing between lists of different lengths you could use tuples like (a,a) (list of length 2) (a,a,a) (list of length 3) etc.
What would be the advantage to using standard lists? In both cases I'd need explicit length checks everywhere.
A better solution might be: data EmptyList element = EmptyList data TrueList list element = TrueList element (list element) A list of four Ints for example would be represented by a value of type TrueList (TrueList (TrueList (TrueList EmptyList))) Int.
Isn't that just the Haskell list type by another name?
You could define different types for different natural numbers: data Zero = Zero data Succ number = Succ number and do simple arithmetic with them at the type level: class Sum a b c | (a, b) -> c instance Sum 0 a a instance Sum a b c => Sum (Succ a) b (Succ c)
That looks interesting, I need to look into multiple parameter classes...
At the moment, I cannot think of a way of defining a list type which is parameterized by such natural types. What I mean is having a type List :: * -> * -> * where for our above example of a list of four Ints we would have the type List (Succ (Succ (Succ (Succ Zero)))) Int
That's what I would like...
What I can think of, is an association between our above list types (EmptyList and TrueList) and our natural number types by a multi-parameter class: class HasLength list length | list -> length instance HasLength EmptyList Zero instance HasLength list length => HasLength (TrueList list) (Succ length)
Again those multi-parameter classes... and off I go to the Haskell Web site ;-) Thanks for your comments! Konrad.
A better solution might be: data EmptyList element = EmptyList data TrueList list element = TrueList element (list element) A list of four Ints for example would be represented by a value of type TrueList (TrueList (TrueList (TrueList EmptyList))) Int.
Isn't that just the Haskell list type by another name?
I think it's quite different. A Haskell list looks like this: 1 : 2 : 3 : 4 : [] :: [Int] Note that the type gives no indication of the length of the list. Wolfgang's lists look like this (I'm adding a 'T_' prefix to the names of the type constructors to remove some ambiguity) 1 `TrueList` 2 `TrueList` 3 `TrueList` 4 `TrueList` EmptyList :: T_TrueList (T_TrueList (T_TrueList (T_TrueList T_EmptyList))) Int Note that you can determine the length of the list from the _type_ by counting the occurences of T_TrueList in the type. You can see a fully worked use of this approach in Mark Jones' paper about typechecking Java bytecodes by translating them into a Haskell program using this kind of encoding. (I'm not sure if Mark would characterise the paper this way but it's what I remember him doing...) http://www.cse.ogi.edu/~mpj/pubs/funJava.html -- Alastair Reid
On Tue, 5 Aug 2003 15:23:09 +0200
Wolfgang Jeltsch
You could define different types for different natural numbers: data Zero = Zero data Succ number = Succ number
This resembles http://www.brics.dk/RS/01/10/ V.
participants (4)
-
Alastair Reid -
Konrad Hinsen -
Nick Name -
Wolfgang Jeltsch