Question: I need this question done in the OCaml language: An ordered list is a list in which an element that appears later in the list
I need this question done in the OCaml language:
An ordered list is a list in which an element that appears later in the list is never smaller than an element that appears earlier in the list, where the notion of "smaller than" is given by a specific chosen relation. For example, the list
[1; 5; 7; 12; 13]
is an ordered list relative to the usual < relation on numbers, the list
[17; 14; 9; 6; 2]
is an ordered list relative to the > relation on numbers but not relative to the < order and the list
[17; 14; 9; 13; 2]
is an ordered list relative to neither the usual < nor the usual > relation on numbers.
1. Clearly, whether or not a list is ordered is dependent also on the ordering relation in use. Define a type constructor olist that is like the list type constructor except that values of this type carry enough information to determine whether or not they are ordered lists relative to the intended ordering relation.
2. Define a function
initOList : ('a -> 'a -> bool) -> 'a olist that takes an ordering relation over a given type and returns an empty olist of that type.
3. Using let declarations, bind list1 and list2 to two different values of int olist type that use different ordering relations and that satisfy the invariant based on that ordering relation. Then bind list3 to a value of int olist that does not satisfy the necessary invariant.
4. Define a function
isOrderedList : ('a olist) -> bool that takes an ordered list and determines whether or not it satisfied the required ordering invariant based on the intended ordering relation. Test this function using the identifiers list1, list2 and list3.
5. Define a function
insertOList : 'a -> ('a olist) -> ('a olist) that takes an element and an ordered list and returns an ordered list that has all the original elements plus the new one and that continues to satisfy the invariant based on the relevant ordering property.
6. Define a function
olistToList : 'a olist -> 'a list
that takes an ordered list and converts it into an ordinary list with the same elements and in the same order as in the given olist.
Language: Ocaml
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
