concept ordering in category idris

appears as: orderings, ordering, ordering, n Ordering
Type-Driven Development with Idris

This is an excerpt from Manning's book Type-Driven Development with Idris.

  • Define— For ?insert_rhs_2, you need to compare the value you’re inserting, x, with the value at the node, val. If x is smaller than val, you insert it into the left subtree. If it’s equal, it’s already in the tree, so you return the tree unchanged. If it’s greater than val, you insert it into the right subtree. To do this, you can use the compare function from the Prelude, which returns an element of an Ordering enumeration:
    data Ordering = LT | EQ | GT
    compare : Ord a => a -> a -> Ordering
    You’ll perform a match on the intermediate result of compare x val. Press Ctrl-Alt-M over insert_rhs_2:
    insert : Ord elem => elem -> Tree elem -> Tree elem
    insert x Empty = Node Empty x Empty
    insert x (Node left val right) = case _ of
                                          case_val => ?insert_rhs_2
  • 7.1.5. Constrained interfaces: defining orderings with Ord

    If you place a constraint on an interface definition, you’re effectively extending an existing interface. In the Prelude, for example, there’s an Ord interface, shown in the next listing, that extends Eq to support ordering of values.

  • The following (incomplete) type defines a command for a guessing game, where the input and output states are the number of remaining guesses allowed:
    data GuessCmd : Type -> Nat -> Nat -> Type where
         Try : Integer -> GuessCmd Ordering ?in_state ?out_state
    
         Pure : ty -> GuessCmd ty state state
         (>>=) : GuessCmd a state1 state2 ->
                 (a -> GuessCmd b state2 state3) ->
                 GuessCmd b state1 state3
    The Try command returns an Ordering that says whether the guess was too high, too low, or correct, and that changes the number of available guesses. Complete the type of Try so that you can only make a guess when there’s at least one guess allowed, and so that guessing reduces the number of guesses available. If you have a correct answer, the following definition should type-check:
    threeGuesses: GuessCmd () 3 0
    threeGuesses = do Try 10
                      Try 20
                      Try 15
                      Pure ()
    Also, the following definition shouldn’t type-check:
    noGuesses : GuessCmd () 0 0
    noGuesses = do Try 10
                   Pure ()