Talk:Algebraic data types: Difference between revisions
m
no edit summary
m (moved Talk:Pattern Matching to Talk:Pattern matching) |
mNo edit summary |
||
| (8 intermediate revisions by 4 users not shown) | |||
Line 13:
There's also unification - when a variable name appears multiple times in a pattern, it must stand in for the (fsvo) same data in all cases. But pattern-matching is most commonly used in conjunction with languages with Hindley-Milner type checkers and should be understood in terms of these implementations. foobie-bletch 18:02, 6 August 2009 (UTC)
----
I don't understand the essence of the task.
<lang J>NB. comparisons of arbitrary data types in j
compare=: <:@:(-: + +:@:A.@:/:@:,:&:<)
assert _1 -: 0 compare 1 NB. less than
assert 0 -: compare~'abc' NB. equal
assert 1 -:'0'compare 0 NB. consistent order of
assert _1 -: 0 compare'0' NB. dissimilar data types
assert 1 -:'a'compare'@' NB. greater than
</lang>
If I were to implement red-black tree I'd hash to compare integers, and the result would be to provide associative array functionality. Does this prove algebraic data type? I suppose. Data can be recovered via j verbs.
--LambertDW 20:47, 27 February 2012 (UTC)
:I am uncertain, myself about this task. Here's what I believe I know:
::"algebraic data type" means that data types are represented by numbers which list the number of possible values that can be represented by that data type. A bit data type would be represented by the number 2. An 8 bit character would be represented by the number 256. A 32 bit integer would be represented by the number 4294967296. A type that represents the program being in an error state would be represented by the number 0. This system allows you to use algebra to work with the properties of composite and derived types.
::Implicitly, languages which support types often have syntax rules to prevent certain combinations of types from being used. Typically, these syntax rules get associated with defined words which represent functions, and these syntax rules approximate the domain of those functions. (In some cases you get an exact match , but this cannot be guaranteed without solving the halting problem.) This, I think, is what encourages a proliferation of types.
::I think that the task is encouraging the use of a type system which distinguishes between "red" and "black" nodes by using different types for them. I think that the implicit desire, here, is to use types which are represented syntactically (in code paths). (But to explicitly require specific syntax would conflict with what rosetta code tasks are.)
::I believe that there are also some other implicit statements here, which I would have to have a different background to appreciate.
:That said, I think the task is also incomplete (it includes no explicit feature tests). It's also going to be highly inefficient, in J, because of the low fan-out on each node. So don't worry about efficiency or usefulness if you implement this in J. --[[User:Rdm|Rdm]] 15:14, 2 March 2012 (UTC)
:: The "algebraic" part is not about underlying representation. It's because the data type itself forms a free algebra. "Algebra" here means a set with some operations (effectively the data type's constructors) on it. A "free" algebra is one where the only way two terms can represent the same element is by being the same term. On the programming side, two things are only the same if they're made by calling the same constructor with the same arguments. A simple example of a free algebra is Peano-encoded natural numbers: Z ("zero") is a 0-ary constructor, and S ("successor") is a unary constructor. Z, S(Z), S(S(Z)), etc. are all different things. If we introduce a P ("plus") constructor, it's no longer free because, e.g., P(Z, S(Z)) = P(S(Z), Z). Pattern matching is the usual way to consume this kind of data type. Pattern matching is a form of conditional where each case in a match expression specifies what the constructor must be and then gives names to the constructor's arguments. J doesn't really have built-in support for ADTs or pattern matching (this is possibly an argument in favor of splitting this page's task as suggested above -- keep the J implementation of red-black tree up, but it probably doesn't belong on a page about destructing an ADT by pattern matching). [[User:Jrslepak|Jrslepak]] ([[User talk:Jrslepak|talk]]) 16:20, 9 September 2014 (UTC)
::: After some thought, I believe this description is flawed. That said, the J implementation was also flawed in this context and I have replaced it. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 02:21, 22 June 2022 (UTC)
:J stores symbols in a red black tree. Maybe we need only show symbol code. Ha ha. An implementation detail, not a language feature. --LambertDW 16:31, 10 March 2012 (UTC)
| |||