Converting fix function to Fix data structure
Posted on April 23, 2019
That article derives the fix function – the essence of recursion – for Scala.
But as well as recursive functions, Fix also describes data structures. Let’s follow the process of converting the fix function to a data structure. As I showed in the original article, the Haskell function is defined:
First, replace the argument polymorphism with type polymorphism. This is more or less just capitalising the names and wrapping type parameters in square brackets:
This doesn’t quite compile, since F itself has to take a type parameter, so must be F[_]:
The fixed data item f is usually called unfix:
Sorted.