¿Cómo decidir si se debe parametrizar a nivel de tipo o de módulo al diseñar módulos?

Estoy trabajando para lograr una comprensión profunda de los módulos de estilo ML: creo que el concepto es importante y me encanta el tipo de pensamiento que fomentan. Ahora estoy descubriendo la tensión que puede surgir entre los tipos paramétricos y los módulos paramétricos. Estoy buscando herramientas para pensar sobre el asunto que me ayudarán a tomar decisiones de diseño inteligentes a medida que desarrolle mis programas.

Puño Intentaré describir mi pregunta en general. Luego proporcionaré un ejemplo concreto de un proyecto de aprendizaje en el que estoy trabajando. Finalmente, volveré sobre la pregunta general para dibujarla en un punto.

(Lamento no saber lo suficiente como para plantear esta pregunta de manera más sucinta).

En términos generales, la tensión que he descubierto es esta: las funciones son más flexibles y están abiertas a la reutilización más amplia, cuando les proporcionamos firmas de tipo paramétrico (cuando corresponda). Sin embargo, los módulos son más flexibles y están abiertos a la reutilización más amplia cuando sellamos la parametrización de funciones dentro del módulo, y en su lugar parametrizamos todo el módulo en un tipo dado.

Un ejemplo listo de esta diferencia se puede encontrar al comparar módulos que implementanLIST firma con los que implementanORD_SET. Un moduloList:LIST proporciona un montón de funciones útiles, parametrizadas en cualquier tipo. Una vez que hemos definido o cargado unList módulo, podemos aplicar fácilmente cualquiera de las funciones que proporciona para construir, manipular o examinar listas de cualquier tipo. Por ejemplo, si estamos trabajando con cadenas y enteros, podemos usar el mismo módulo para construir y manipular valores de ambos tipos:

val strList = List.@ (["a","b"], ["c","d"])
val intList = List.@ ([1,2,3,4], [5,6,7,8])

Por otro lado, si queremos tratar con conjuntos ordenados, los asuntos son diferentes: los conjuntos ordenados requieren que una relación de orden se mantenga sobre todos sus elementos, y no puede haber una función concreta únicacompare : 'a * 'a -> order produciendo esa relación para cada tipo. En consecuencia, requerimos un módulo diferente que satisfaga elORD_SET firma para cada tipo que deseamos poner en conjuntos ordenados. Por lo tanto, para construir o manipular conjuntos ordenados de cadenas y enteros, debemos implementar diferentes módulos para cada tipo [1]:

structure IntOrdSet = BinarySetFn ( type ord_key = int
                                    val compare = Int.compare )
structure StrOrdSet = BinarySetFn ( type ord_key = string
                                    val compare = String.compare )

Y luego debemos usar la función de ajuste del módulo apropiado cuando deseamos operar en un tipo dado:

val strSet = StrOrdSet.fromList ["a","b","c"]
val intSet = IntOrdSet.fromList [1,2,3,4,5,6]

Hay una compensación bastante directa aquí:LIST los módulos proporcionan funciones que se extienden sobre cualquier tipo que desee, pero no pueden aprovechar las relaciones que se mantienen entre los valores de cualquier tipo en particular;ORD_SET Los módulos proporcionan funciones que están necesariamente restringidas al tipo suministrado en el parámetro functors, pero a través de esa misma parametrización, son capaces de incorporar información específica sobre la estructura interna y las relaciones de sus tipos de destino.

Es fácil imaginar casos en los que quisiéramos diseñar una familia alternativa de módulos de lista, utilizando functores para parametrizar tipos y otros valores para proporcionar tipos de datos similares a una lista con una estructura más complicada: por ejemplo, para especificar un tipo de datos para la lista ordenada , o para representar listas utilizando árboles de búsqueda binarios de equilibrio automático.

Al crear un módulo, creo que también es bastante fácil reconocer cuándo podrá proporcionar funciones polimórficas y cuándo deberá parametrizarse en algún tipo (s). Lo que me parece más difícil, para mí, es descubrir qué tipo de módulos debe depender cuando trabaje en algo más adelante.

En términos generales, mi pregunta es la siguiente: cuando estoy diseñando un sistema de módulos relacionados de diversas maneras, ¿cómo puedo determinar si diseñar alrededor de módulos que proporcionan funciones polimórficas o módulos generados usando functores parametrizados en tipos y valores?

Espero ilustrar el dilema y por qué es importante con el siguiente ejemplo, tomado de un proyecto de juguete en el que estoy trabajando.

tengo unfunctor PostFix (ST:STACK) : CALCULATOR_SYNTAX. Esto toma una implementación de una estructura de datos de pila y produce un analizador sintáctico que lee la notación concreta de postfix ("pulido inverso") en una sintaxis abstracta (para ser evaluada por un módulo de calculadora corriente abajo) y viceversa. Ahora, había estado usando una interfaz de pila estándar que proporciona un tipo de pila polimórfica y una cantidad de funciones para operar en ella:

signature STACK =
sig
    type 'a stack
    exception EmptyStack

    val empty : 'a stack
    val isEmpty : 'a stack -> bool

    val push : ('a * 'a stack) -> 'a stack
    val pop  : 'a stack -> 'a stack
    val top  : 'a stack -> 'a
    val popTop : 'a stack -> 'a stack * 'a
end

Esto funciona bien y me da cierta flexibilidad, ya que puedo usar una pila basada en listas o una pila basada en vectores, o lo que sea. Pero, digamos que quiero agregar una función de registro simple al módulo de la pila, para que cada vez que un elemento sea empujado o sacado de la pila, imprima el estado actual de la pila. Ahora necesitaré unfun toString : 'a -> string para el tipo recogido por la pila, y esto, según tengo entendido, no se puede incorporar en elSTACK módulo. Ahora necesito sellar el tipo en el módulo y parametrizar el módulo sobre el tipo recogido en la pila y untoString función que me permitirá producir una representación imprimible del tipo recopilado. Entonces necesito algo como

functor StackFn (type t
                 val toString: t -> string ) =
struct
   ...
end

y esto lo haráno producir un módulo que coincida con elSTACK firma, ya que no proporciona un tipo polimórfico. Por lo tanto, debo cambiar la firma requerida paraPostFix Functor Si tengo muchos otros módulos, también tengo que cambiarlos todos. Eso podría ser inconveniente, pero el verdadero problema es que ya no puedo usar mi simple lista o vector.STACK módulos en elPostFix Functor cuando yono lo hagas quiere iniciar sesión. Ahora, parece, tengo que regresar y reescribir esos módulos para tener un tipo sellado también.

Entonces, para volver, expandir y (afortunadamente) terminar mi pregunta:

¿Hay alguna forma de especificar la firma de los módulos producidos porStackFn para que terminen como "casos especiales" deSTACK?Alternativamente, ¿hay alguna forma de escribir una firma paraPostFix módulo que permitiría tanto los módulos producidos porStackFn y los que satisfacenSTACK?En términos generales, ¿hay alguna forma de pensar sobre la relación entre módulos que me ayudaría a captar / anticipar este tipo de cosas en el futuro?

(Si has leído hasta aquí. ¡Muchas gracias!)