![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
![]() | This article is based on material taken from algebraic data type at the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later. |
|
Can someone take a step back and add more "primer" to this? In particular, why is this called algebraic? What makes it that way?
What are some non-algebraic types that may provide the same features, or be used in competition with these?
What makes a type algebraic? When should I use the word "algebraic" in programming dialog?
Frankly, I don't care about (your favorite programming language). I only code in (some language you don't like). Please tell me how this applies to me.
-Austin Hastings 68.37.47.32 ( talk) 03:20, 24 September 2010 (UTC)
ADTs are called "Algebraic" because they represent algebraic theories, as defined in Model Theory. Vlad Patryshev ( talk) 08:01, 15 April 2021 (UTC)
I believe this page and tagged union refer to more or less the same concept, but they could be merged usefully. Does anyone disagree with this?
Derrick Coetzee 16:37, 4 Apr 2004 (UTC)
I think that would be a bad idea. A tagged union is different from an algebraic data type, but they can be used to implement algebraic data types, though this article probably needs more generalization. Dysprosia 22:05, 4 Apr 2004 (UTC)
Yes, I agree that these deserve different articles. I plan to clean this one up. Brighterorange 04:40, 13 May 2005 (UTC)
Which languages support algebraic data types? Using What links here, I only see Haskell, ML, Nemerle, Hope, Pizza.
So Haskell uses :
for list constructor operator and ML uses ::
and they use the other for type annotations. I suppose it's ok to give both alternatives then. But do we need to give Nil and Cons without capital letters as that makes them look like functions? I know Lisp has nil and cons but then again Lisp doesn't have algebraic data types and constructors. If it's meant to be mathematical notation, I must say I'm not a fan of it either in programming-related articles.
My proposal would be to revert Nil and Cons to have capital letters. -- TuukkaH 15:51, 15 February 2006 (UTC)
I just removed the following discussion from the article. See below for why.
map :: (a -> b) -> [a] -> [b] map Leaf [0 .. 9]
List.map : ('a -> 'b) -> 'a list -> 'b list List.map Leaf [0;1;2;3;4;5;6;7;8;9];; The constructor Leaf expects 1 argument(s), but is here applied to 0 argument(s)
List.map (fun x -> Leaf x) [0;1;2;3;4;5;6;7;8;9]
The problem is that map Leaf [0,1,2,3,4]
is legal
SML, even if it is not legal
OCaml (I wouldn't know about the latter). It follows that the reason for its being illegal in OCaml has nothing to do with predicativity or the restriction to prenex polymorphism, which is what the above seems to mean by being "System-F-based" -- that in itself, of course, is somewhere between misleading and false. Is there, in fact, a "reason" why OCaml cannot treat datatype constructors as values of function type, or is that just the way the language happened to be designed? --
Cjoev
17:22, 28 March 2006 (UTC)
data Triple a b c = MkTriple a b c deriving Show zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] foo = zipWith (\f x -> f x) (zipWith MkTriple [0..4] "abcd") ["foo","bar","baz","qux"] ... =>[MkTriple 0 'a' "foo",MkTriple 1 'b' "bar",MkTriple 2 'c' "baz",MkTriple 3 'd' "qux"] bar = let f = MkTriple f' = f 0 f'' = f' 'a' f''' = f'' "foo" in f''' ... => MkTriple 0 'a' "foo" baz = let f = MkTriple f' = f f f'' = f' f f''' = f'' f in case f''' of (MkTriple g h i) -> let g' = g 0 'a' "foo" h' = h 1 'b' "bar" i' = i 2 'c' "baz" in f g' h' i' ... => MkTriple (MkTriple 0 'a' "foo") (MkTriple 1 'b' "bar") (MkTriple 2 'c' "baz")
datatype ('a,'b,'c) triple = Triple of 'a * 'b * 'c fun mktriple a b c = Triple(a,b,c) val baz = let val f = mktriple val f' = f f val f'' = f' f val f''' = f'' f in case f''' of (Triple (g, h, i)) => let val g' = g 0 #"a" "foo" val h' = h 1 #"b" "bar" val i' = i 2 #"c" "baz" in f g' h' i' end end
*
. Example:data Triple a b c = MkTriple a b c -- not a type, but kind: * -> * -> * -> * type F = Triple -- ... kind: * -> * -> * -> * type F' = F Int -- ... kind: * -> * -> * type F'' = F' Char -- ... kind: * -> * type F''' = F'' String -- now a type, kind: * f :: Int -> Char -> String -> F''' f = MkTriple
Triple
, and then there are value constructors such as MkTriple
. The former has kind * -> * -> * -> *
; the latter is a term-level construct that (in Haskell) has type a -> b -> c -> Triple a b c
(which has kind *
). This type is universally quantified, but all the variables have kind * and so I maintain that it is not significantly different from the SML type 'a -> 'b -> 'c -> ('a,'b,'c) triple
, which is the type of mktriple
in my translation of your earlier example.type ('b,'c) F' = (int,'b,'c) triple type 'c F'' = (char,'c) F' type F''' = string F'' val f : int -> char -> string -> F''' = mktriple
This article appears to be talking about a concept specific to the ML family of languages. This should be mentioned somewhere near the top. -- macrakis ( talk) 16:57, 26 December 2008 (UTC)
![]() | This article may be too technical for most readers to understand.(September 2010) |
whoa. This is way beyond an average reader.
I'd like to make this understandable to guys like me, who live in the world of more applied languages like C++, Ruby, JavaScript, PHP. You say Pattern Matching and I say RegEx. Never used any of the languages you mention here, although I've heard of Haskell, and a lot of the concepts seem familiar. Don't roll your eyes and say it can't be done; it can.
Much of this seems like some of the symbolic algebra I did years ago. You give it "(x+1)^2", and instead of looking up the value of x, it would construct a tree like
Each node in the tree is like a constructor for a hypothetical calculation process, where the node 'integer 2' constructs the float number 2.000 into the calculation, etc. But the point of this pre-construction tree is to come up with other such trees, like x^2+2*x+1. Each node represents the potential for an object, but, by being unconstructed, you can do things not possible by calculation, like arrive at conclusions for all x, or prove things without roundoff error. More serious users work with linear algebra and functional values rather than just numbers, and these can only exist in pre-constructed form.
It would be nice to make an example, say in JavaScript, where you can make a char string of a JS expression, and then calculate it with eval(). All the while saying, "It's like if you could do this in JS, but without character strings". OsamaBinLogin ( talk) 00:15, 24 March 2009 (UTC)
The article could benefit from some pointers to more detailed discussion.
I came here looking for some information about the formal underpinnings of the type systems in languages like Haskell, ML and Typed Racket, but the bulk of the article proceeds by examples (which aren't particularly helpful unless someone already groks Haskell or ML syntax, in which case they probably don't have much of a problem), save a brief lurch into formality in the 'Theory' section.
The article does cross-refer to Type theory, but that's a very high level introduction to types in the context of formal logic. The formal parts (ie the algebra) in the 'Theory' section are what I'm after, but they're not really explained in the cross-referred article. A pointer to a review article or textbook-level introduction would be perfect. I don't have any suggestions for that (that's what I came here looking for).
Overall, the article is indeed uneven. Type theory is technical, and of interest only to people who are already at least vaguely familiar with algebraically typed languages and want to dig more. It would therefore be useful to have, at the top, a remark this is not the article you're looking for, addressed to people who want to know the difference between dynamic and static types, say, and pointing to Type system. NormanGray ( talk) 10:56, 17 August 2011 (UTC)
The explanation section mainly deals with the specifics of pattern matching but I think it's reasonable to assume the reader already knows what this is and/or how the Haskell code should be read. If they don't, they can read the article pattern matching (which is where the content under explanation could be moved to). The article is about algebraic data types after all; if you're not familiar with pattern matching, you should study that first before reading this article. Simeon ( talk) 15:46, 5 April 2009 (UTC)
I'd like to see one or two more sentences, in the first paragraph (or perhaps a new second paragraph), explaining what makes the Algebraic data type useful. Why should I like it?
The current opening paragraph is an excellent descriptive "what" statement. It nicely summarizes what the Algebraic data type is.
The second paragraph gets right into technical details, and does so very well.
But there's something missing in between -- after the "what" statement, before the technical details, I'd like to see a sentence or two about how this is useful, and who might find it of interest and why.
I'm a programmer myself, this is exactly the kind of thing that catches my attention, but I'm not familiar with the subject so I'll leave the editing to someone else.
Karl gregory jones ( talk) 03:35, 9 October 2010 (UTC)
This article could really use a section on how algebraic data types are implemented - that is, how they are represented in memory. I would start it, but I know almost nothing about the subject.
Anecdotally, I agree with the people that say this article is, if anything, not technical enough. It certainly isn't too technical. It reads too much like a tutorial or a textbook, as well. For a somewhat abstruse topic, though, it's a good start. Exercisephys ( talk) 01:38, 18 July 2014 (UTC)
In the 'Examples' section, for the 'Expression' data type Minus is defined as
Minus Expression Expression
yet it is used later in an expression as
(Minus (Number 1))
It should probably defined as unary in type definition, to allow for negation. — Preceding unsigned comment added by 2620:0:1047:0:97A:A78A:439B:DC43 ( talk) 10:22, 26 September 2016 (UTC)
@ STyx: This article mentions algebraic data types in Coq, but I'm not sure if the article's references describe them. Is there any documentation that describes this feature in Coq? Jarble ( talk) 01:38, 8 February 2019 (UTC)
Datatypes
and
Logic
. <
STyx
@ (I promote
Geolocation)
13:56, 8 February 2019 (UTC)The "binary tree" example does not correspond to the binary trees on the page of the subject (which is linked to.) A tree is either empty, or it is a node with a value and two subtrees. The tree as defined will hold values only in leaf nodes. That seems a bit silly. -- Lasse Hillerøe Petersen ( talk) 19:36, 3 April 2020 (UTC)
The page takes a rather ML-centric viewpoint. It would be good to take a broader perspective. A type-safe version of this type was first introduced by CLU (cf John Reynolds), where it was called a "oneof" type. "Variant type" is at least as standard a terminology as "algebraic data type", which I have always found to be verbose...and a little pompous. The "algebra" in question is a free algebra, which is to say that it has no equational theory. Personally, I don't find it enlightening to bake the connection to abstract algebra into the name; it feels like intellectual terrorism. -- Andrew Myers ( talk) 22:31, 7 May 2021 (UTC)
It says that an algebraic data type is a kind of composite type... and then not really much beyond that. What's the difference? AltoStev ( talk) 00:31, 22 December 2022 (UTC)
"Algebraic data types were introduced in Hope, a small functional programming language developed in the 1970s at the University of Edinburgh"
As if e.g. Algol didn't have any algebraic types.
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
![]() | This article is based on material taken from algebraic data type at the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later. |
|
Can someone take a step back and add more "primer" to this? In particular, why is this called algebraic? What makes it that way?
What are some non-algebraic types that may provide the same features, or be used in competition with these?
What makes a type algebraic? When should I use the word "algebraic" in programming dialog?
Frankly, I don't care about (your favorite programming language). I only code in (some language you don't like). Please tell me how this applies to me.
-Austin Hastings 68.37.47.32 ( talk) 03:20, 24 September 2010 (UTC)
ADTs are called "Algebraic" because they represent algebraic theories, as defined in Model Theory. Vlad Patryshev ( talk) 08:01, 15 April 2021 (UTC)
I believe this page and tagged union refer to more or less the same concept, but they could be merged usefully. Does anyone disagree with this?
Derrick Coetzee 16:37, 4 Apr 2004 (UTC)
I think that would be a bad idea. A tagged union is different from an algebraic data type, but they can be used to implement algebraic data types, though this article probably needs more generalization. Dysprosia 22:05, 4 Apr 2004 (UTC)
Yes, I agree that these deserve different articles. I plan to clean this one up. Brighterorange 04:40, 13 May 2005 (UTC)
Which languages support algebraic data types? Using What links here, I only see Haskell, ML, Nemerle, Hope, Pizza.
So Haskell uses :
for list constructor operator and ML uses ::
and they use the other for type annotations. I suppose it's ok to give both alternatives then. But do we need to give Nil and Cons without capital letters as that makes them look like functions? I know Lisp has nil and cons but then again Lisp doesn't have algebraic data types and constructors. If it's meant to be mathematical notation, I must say I'm not a fan of it either in programming-related articles.
My proposal would be to revert Nil and Cons to have capital letters. -- TuukkaH 15:51, 15 February 2006 (UTC)
I just removed the following discussion from the article. See below for why.
map :: (a -> b) -> [a] -> [b] map Leaf [0 .. 9]
List.map : ('a -> 'b) -> 'a list -> 'b list List.map Leaf [0;1;2;3;4;5;6;7;8;9];; The constructor Leaf expects 1 argument(s), but is here applied to 0 argument(s)
List.map (fun x -> Leaf x) [0;1;2;3;4;5;6;7;8;9]
The problem is that map Leaf [0,1,2,3,4]
is legal
SML, even if it is not legal
OCaml (I wouldn't know about the latter). It follows that the reason for its being illegal in OCaml has nothing to do with predicativity or the restriction to prenex polymorphism, which is what the above seems to mean by being "System-F-based" -- that in itself, of course, is somewhere between misleading and false. Is there, in fact, a "reason" why OCaml cannot treat datatype constructors as values of function type, or is that just the way the language happened to be designed? --
Cjoev
17:22, 28 March 2006 (UTC)
data Triple a b c = MkTriple a b c deriving Show zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] foo = zipWith (\f x -> f x) (zipWith MkTriple [0..4] "abcd") ["foo","bar","baz","qux"] ... =>[MkTriple 0 'a' "foo",MkTriple 1 'b' "bar",MkTriple 2 'c' "baz",MkTriple 3 'd' "qux"] bar = let f = MkTriple f' = f 0 f'' = f' 'a' f''' = f'' "foo" in f''' ... => MkTriple 0 'a' "foo" baz = let f = MkTriple f' = f f f'' = f' f f''' = f'' f in case f''' of (MkTriple g h i) -> let g' = g 0 'a' "foo" h' = h 1 'b' "bar" i' = i 2 'c' "baz" in f g' h' i' ... => MkTriple (MkTriple 0 'a' "foo") (MkTriple 1 'b' "bar") (MkTriple 2 'c' "baz")
datatype ('a,'b,'c) triple = Triple of 'a * 'b * 'c fun mktriple a b c = Triple(a,b,c) val baz = let val f = mktriple val f' = f f val f'' = f' f val f''' = f'' f in case f''' of (Triple (g, h, i)) => let val g' = g 0 #"a" "foo" val h' = h 1 #"b" "bar" val i' = i 2 #"c" "baz" in f g' h' i' end end
*
. Example:data Triple a b c = MkTriple a b c -- not a type, but kind: * -> * -> * -> * type F = Triple -- ... kind: * -> * -> * -> * type F' = F Int -- ... kind: * -> * -> * type F'' = F' Char -- ... kind: * -> * type F''' = F'' String -- now a type, kind: * f :: Int -> Char -> String -> F''' f = MkTriple
Triple
, and then there are value constructors such as MkTriple
. The former has kind * -> * -> * -> *
; the latter is a term-level construct that (in Haskell) has type a -> b -> c -> Triple a b c
(which has kind *
). This type is universally quantified, but all the variables have kind * and so I maintain that it is not significantly different from the SML type 'a -> 'b -> 'c -> ('a,'b,'c) triple
, which is the type of mktriple
in my translation of your earlier example.type ('b,'c) F' = (int,'b,'c) triple type 'c F'' = (char,'c) F' type F''' = string F'' val f : int -> char -> string -> F''' = mktriple
This article appears to be talking about a concept specific to the ML family of languages. This should be mentioned somewhere near the top. -- macrakis ( talk) 16:57, 26 December 2008 (UTC)
![]() | This article may be too technical for most readers to understand.(September 2010) |
whoa. This is way beyond an average reader.
I'd like to make this understandable to guys like me, who live in the world of more applied languages like C++, Ruby, JavaScript, PHP. You say Pattern Matching and I say RegEx. Never used any of the languages you mention here, although I've heard of Haskell, and a lot of the concepts seem familiar. Don't roll your eyes and say it can't be done; it can.
Much of this seems like some of the symbolic algebra I did years ago. You give it "(x+1)^2", and instead of looking up the value of x, it would construct a tree like
Each node in the tree is like a constructor for a hypothetical calculation process, where the node 'integer 2' constructs the float number 2.000 into the calculation, etc. But the point of this pre-construction tree is to come up with other such trees, like x^2+2*x+1. Each node represents the potential for an object, but, by being unconstructed, you can do things not possible by calculation, like arrive at conclusions for all x, or prove things without roundoff error. More serious users work with linear algebra and functional values rather than just numbers, and these can only exist in pre-constructed form.
It would be nice to make an example, say in JavaScript, where you can make a char string of a JS expression, and then calculate it with eval(). All the while saying, "It's like if you could do this in JS, but without character strings". OsamaBinLogin ( talk) 00:15, 24 March 2009 (UTC)
The article could benefit from some pointers to more detailed discussion.
I came here looking for some information about the formal underpinnings of the type systems in languages like Haskell, ML and Typed Racket, but the bulk of the article proceeds by examples (which aren't particularly helpful unless someone already groks Haskell or ML syntax, in which case they probably don't have much of a problem), save a brief lurch into formality in the 'Theory' section.
The article does cross-refer to Type theory, but that's a very high level introduction to types in the context of formal logic. The formal parts (ie the algebra) in the 'Theory' section are what I'm after, but they're not really explained in the cross-referred article. A pointer to a review article or textbook-level introduction would be perfect. I don't have any suggestions for that (that's what I came here looking for).
Overall, the article is indeed uneven. Type theory is technical, and of interest only to people who are already at least vaguely familiar with algebraically typed languages and want to dig more. It would therefore be useful to have, at the top, a remark this is not the article you're looking for, addressed to people who want to know the difference between dynamic and static types, say, and pointing to Type system. NormanGray ( talk) 10:56, 17 August 2011 (UTC)
The explanation section mainly deals with the specifics of pattern matching but I think it's reasonable to assume the reader already knows what this is and/or how the Haskell code should be read. If they don't, they can read the article pattern matching (which is where the content under explanation could be moved to). The article is about algebraic data types after all; if you're not familiar with pattern matching, you should study that first before reading this article. Simeon ( talk) 15:46, 5 April 2009 (UTC)
I'd like to see one or two more sentences, in the first paragraph (or perhaps a new second paragraph), explaining what makes the Algebraic data type useful. Why should I like it?
The current opening paragraph is an excellent descriptive "what" statement. It nicely summarizes what the Algebraic data type is.
The second paragraph gets right into technical details, and does so very well.
But there's something missing in between -- after the "what" statement, before the technical details, I'd like to see a sentence or two about how this is useful, and who might find it of interest and why.
I'm a programmer myself, this is exactly the kind of thing that catches my attention, but I'm not familiar with the subject so I'll leave the editing to someone else.
Karl gregory jones ( talk) 03:35, 9 October 2010 (UTC)
This article could really use a section on how algebraic data types are implemented - that is, how they are represented in memory. I would start it, but I know almost nothing about the subject.
Anecdotally, I agree with the people that say this article is, if anything, not technical enough. It certainly isn't too technical. It reads too much like a tutorial or a textbook, as well. For a somewhat abstruse topic, though, it's a good start. Exercisephys ( talk) 01:38, 18 July 2014 (UTC)
In the 'Examples' section, for the 'Expression' data type Minus is defined as
Minus Expression Expression
yet it is used later in an expression as
(Minus (Number 1))
It should probably defined as unary in type definition, to allow for negation. — Preceding unsigned comment added by 2620:0:1047:0:97A:A78A:439B:DC43 ( talk) 10:22, 26 September 2016 (UTC)
@ STyx: This article mentions algebraic data types in Coq, but I'm not sure if the article's references describe them. Is there any documentation that describes this feature in Coq? Jarble ( talk) 01:38, 8 February 2019 (UTC)
Datatypes
and
Logic
. <
STyx
@ (I promote
Geolocation)
13:56, 8 February 2019 (UTC)The "binary tree" example does not correspond to the binary trees on the page of the subject (which is linked to.) A tree is either empty, or it is a node with a value and two subtrees. The tree as defined will hold values only in leaf nodes. That seems a bit silly. -- Lasse Hillerøe Petersen ( talk) 19:36, 3 April 2020 (UTC)
The page takes a rather ML-centric viewpoint. It would be good to take a broader perspective. A type-safe version of this type was first introduced by CLU (cf John Reynolds), where it was called a "oneof" type. "Variant type" is at least as standard a terminology as "algebraic data type", which I have always found to be verbose...and a little pompous. The "algebra" in question is a free algebra, which is to say that it has no equational theory. Personally, I don't find it enlightening to bake the connection to abstract algebra into the name; it feels like intellectual terrorism. -- Andrew Myers ( talk) 22:31, 7 May 2021 (UTC)
It says that an algebraic data type is a kind of composite type... and then not really much beyond that. What's the difference? AltoStev ( talk) 00:31, 22 December 2022 (UTC)
"Algebraic data types were introduced in Hope, a small functional programming language developed in the 1970s at the University of Edinburgh"
As if e.g. Algol didn't have any algebraic types.