Implementing the ordinals in Haskell

user_9428700 0
Viewed 270

I've begun learning Haskell, and I thought I would implement the ordinal numbers, using the common ("von Neumann") definition. So I wrote:

ordinal 0 = []
ordinal x = [ ordinal n | n<-[1..(x-1)] ]

But the interpreter was not satisfied, and it told me instead that supposedly

    * Couldn't match type `a' with `[a]'
Expected: t -> a
Actual: t -> [a]
* Relevant bindings include
ordinal :: t -> a (bound at fist.hs:7:1)
|
1 | ordinal 0 = []
| ^^^^^^^^^^^^^^^...

Now what I imagine might have gone wrong here is that the list is not of homogeneous type. But how would I switch to tuples then? Is there such a thing as "tuple comprehension"?

haskell
2 Answers

The result of this function is a single empty value, or a list of such, or a list of lists, or a list of lists of lists, etc., depending on the input number. There is no single list type which can represent all these values.

... or is there? That type is not a list (i.e. []) which only represents a single flat sequences of values, but there is such a type:

data Ordinal = Zero | Ordinal [Ordinal] deriving Show

and your function should be modified to wrap each such level of list nesting in an Ordinal constructor:

ordinal 0 = Zero
ordinal x = Ordinal [ ordinal n | n<-[1..(x-1)] ]

Example:

*Main> ordinal 3
Ordinal [Ordinal [],Ordinal [Ordinal []],Ordinal [Ordinal []]
user_24070380

First, lists aren't sets.

Second, lists require all elements to have the same type, so you can't have lists of different nesting depth in one list.

But from the “everything is a set” perspective that such constructions as Von Neumann ordinals are based on, you can just define a “universal type” based on sets:

import qualified Data.Set as Set

newtype UntypedSet = UntypedSet { getUntypedSet :: Set.Set UntypedSet }
 deriving (Eq, Ord, Show)

ordinal :: Int -> UntypedSet
ordinal 0 = UntypedSet $ Set.empty
ordinal x = UntypedSet $ Set.fromList [ ordinal n | n <- [0..x-1] ]

Note the definition [1..x-1] was actually wrong in your implemetation, it should be [0..x-1].

If you want to go quirky (not necessarily recommended), you can actually still use “list” notation:

{-# LANGUAGE OverloadedLists #-}
{-# LANGUAGE TypeFamilies    #-}

import qualified Data.Set as Set
import GHC.Exts (IsList(..))

newtype UntypedSet = UntypedSet { getUntypedSet :: Set.Set UntypedSet }
 deriving (Eq, Ord)

instance IsList UntypedSet where
  type Item UntypedSet = UntypedSet
  fromList = UntypedSet . Set.fromList
  toList (UntypedSet s) = Set.toList s

instance Show UntypedSet where
  show = show . toList


ordinal :: Int -> UntypedSet
ordinal 0 = []
ordinal x = fromList [ ordinal n | n <- [0..x-1] ]

Then,

*Main> ordinal 4
[[],[[]],[[],[[]]],[[],[[]],[[],[[]]]]]
user_7459030
Related