OOP is fine with functional if you make it immutable too, so I don't see the problem (I've not really got a problem with mutable OOP, or state generally, if it's done carefully).
This depends on your data model, of course. But for a list of integers you could do the following:
1. Have a unique data type that is the list of Deltas, plus the initial element (So for instance the list [5, 3, 6] would be encoded as (3, [2, 1]).
2. Provide a sort function that creates such a sorted list.
3. Make the sorted list your input parameter.
This is obviously oversimplified, but I hope you get the idea.
A cheaper alternative is to
1. Make an opaque datatype "sorted list", together with a function that translates this type to a normal list. Implemen this type just as a list, but keep the implementation private.
2. Provide a function sort, that is the only function that can yield that type.
3. Demand that type as input.
In Reason/OCaml, you can create a module interface (.rei or .mli) which makes the type opaque to functions outside the module. So instead of saying `type t('a) = list('a)`, it'll just say `type t`.
The compiler relies on this type information to decide whether functions are well-typed. So if an external module presumes to know the structure of the type and does an operation on it, it becomes a type error because the compiler simply doesn't know about the actual type. This is similar to encapsulation in OO where we don't expose a field to the outside world, but here it is done by virtue of the type signature itself, which I found to be a more powerful guarantee of encapsulation.
The module can then expose functions like `append` which would be the only way you can manipulate the list. This function in-turn can ensure the postcondition, guaranteeing that the list stays sorted. At the point in which we want to use the list for functions not supported by our SortedList module, we can turn it into a regular list with a `to_list` function. Since the underlying type is already a list, the operation is virtually free. The function would look like `let to_list = (xs: t('a)) => (xs: list('a))`. It is an identity function, with just the type changed for the compiler.
Similar rules about `append` applies to the constructor: we can create a new `SortedList` only with a `SortedList.make` which can ensure the postcondition. There will be no other way, thanks to the type being hidden, to create a value of the `SortedList.t` type.
Things like that require runtime logic, there’s no way around that.