[Haskell-cafe] Learn You a Haskell for Great Good - a few doubts

Alexander Solla alex.solla at gmail.com
Fri Mar 4 22:04:02 CET 2011

On Fri, Mar 4, 2011 at 8:45 AM, Markus Läll <markus.l2ll at gmail.com> wrote:

> Would this also have an uncomputable order type? At least for comparing
> tuples you'd just:

You can tell if an enumeration will have an uncomputable order type by
whether or not your enumeration has to "count to infinity" before it can
continue.  For example, let's use top-left to bottom-right diagonals.  Then
you would have to "count infinitely many steps" (0,0), (1,1), (2,2), (3,3)
... before you could go to the next diagonal.  This excludes an enumeration
from being computable in the usual sense (or having a computable order
type).  As Daniel pointed out, every countable set can be put in
*some* computable
order, since it can inherit the order of the naturals through the

> lt :: (Integer,Integer) -> (Integer,Integer) -> Bool
> (a,b) `lt` (c,d) = let
>       sum1 = (a + b)
>       sum2 = (c + d)
>    in if sum1 == sum2
>          then a < c
>          else sum1 < sum2

The order you impose is a bit broken, but the principle of using diagonals
is sound. (Consider (1,2) and (2,1):  under this order, (1,2) `lt` (2,1) and
(2,1) `lt` (1,2), so (1,2) == (2,1))

Indeed, the diagonal construction is how an enumeration of the rationals is
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110304/0c2b0d1a/attachment.htm>

More information about the Haskell-Cafe mailing list