3 ms·

Playing statically-typed advocate for a moment: in Haskell, you wouldn't have had to put a type down for the function, and the compiler would have inferred the

Playing statically-typed advocate for a moment: in Haskell, you wouldn't have had to put a type down for the function, and the compiler would have inferred the type gcd :: Num a => a -> a -> a which means it is a function that takes 2 a's and returns an a, with the restriction that a is of typeclass[1] Num, that is numbers. So, very much possible and assumed without thinking about it too much. [1] A typeclass is a like an interface.

crntaylor 14y ago
Small correction; with the most common implementation of Euclid's algorithm the compiler would infer gcd :: Integral a => a -> a -> a since writing Euclid's algorithm requires using `mod` or `rem`, both of which only work for integral types (NB. there are many integral types beside ints, for example polynomials, formal power series and gaussian integers). The Integral class captures the mathematical idea of a Euclidean domain, which can loosely be thought of as "number systems for which the Euclidean algorithm works".
qznc 14y ago
Well, pray that the library function is general enough. Unfortunately, this is not the case for your gcd type, as gcd can be generalized to arbitrary commutative rings. Nevertheless, writing generic code is of course possible with static types.
- crntaylor 14y ago
  Well... kind of. You can define a gcd operation on arbitrary commutative rings, but two elements of the ring don't necessarily have a unique gcd. If you want a unique gcd for any pair of elements, you need to specialize your commutative ring to a unique factorization domain. If in addition you want to write your gcd function using the Euclidean algorithm, you need to specialize again to Euclidean domains (of which polynomials and power series are an example). The `gcd` function in the Haskell base library operators on Integral types, which are the programmatic representation of Euclidean domains, so I would argue that it is "general enough".

crntaylor 14y ago

Small correction; with the most common implementation of Euclid's algorithm the compiler would infer gcd :: Integral a => a -> a -> a since writing Euclid's algorithm requires using `mod` or `rem`, both of which only work for integral types (NB. there are many integral types beside ints, for example polynomials, formal power series and gaussian integers). The Integral class captures the mathematical idea of a Euclidean domain, which can loosely be thought of as "number systems for which the Euclidean algorithm works".

qznc 14y ago

Well, pray that the library function is general enough. Unfortunately, this is not the case for your gcd type, as gcd can be generalized to arbitrary commutative rings. Nevertheless, writing generic code is of course possible with static types.

crntaylor 14y ago
Well... kind of. You can define a gcd operation on arbitrary commutative rings, but two elements of the ring don't necessarily have a unique gcd. If you want a unique gcd for any pair of elements, you need to specialize your commutative ring to a unique factorization domain. If in addition you want to write your gcd function using the Euclidean algorithm, you need to specialize again to Euclidean domains (of which polynomials and power series are an example). The `gcd` function in the Haskell base library operators on Integral types, which are the programmatic representation of Euclidean domains, so I would argue that it is "general enough".