parameters - How to decide whether to parameterize on the type-level or the module-level when designing modules? -

i'm working towards deep understanding of ml-style modules: think concept important , love kind of thinking encourage. discovering tension can arise between parametric types , parametric modules. seeking tools thinking matter me make smart design decisions build programs.

fist try describe question in general. provide concrete example learning project working on. finally, revisit general question in order draw point.

(i'm sorry don't yet know enough pose question more succinctly.)

in general terms, tension i've discovered this: functions flexible, , open widest reuse, when provide them parametric type signatures (where appropriate). however, modules flexible , open widest reuse when seal parameterization of functions inside module, , instead parameterize entire module on given type.

a ready example of difference can found in comparing modules implement list signature implement ord_set. module list:list provides bunch of useful functions, parameterized on type. once we've defined or loaded list module, can readily apply of functions provides construct, manipulate, or examine lists of type. e.g., if working both strings , integers, can use 1 , same module construct , manipulate values of both types:

val strlist = list.@ (["a","b"], ["c","d"]) val intlist = list.@ ([1,2,3,4], [5,6,7,8]) 

on other hand, if want deal ordered sets, matters different: ordered sets require ordering relation hold on of elements, , there can no single concrete function compare : 'a * 'a -> order producing relation every type. consequently, require different module satisfying ord_set signature each type wish put ordered sets. thus, in order construct or manipulate ordered sets of strings , integers, must implement different modules each type[1]:

structure intordset = binarysetfn ( type ord_key = int                                     val compare = int.compare ) structure strordset = binarysetfn ( type ord_key = string                                     val compare = string.compare ) 

and must use fitting function appropriate module when wish operate on given type:

val strset = strordset.fromlist ["a","b","c"] val intset = intordset.fromlist [1,2,3,4,5,6] 

there pretty straightforward tradeoff here: list modules provide functions range on type please, cannot take advantage of relations hold between values of particular type; ord_set modules provide functions constrained type supplied in functors parameter, through same parameterization, capable of incorporating specific information internal structure , relations of target types.

it easy imagine cases want design alternative family of list modules, using functors parameterize types , other values provide list-like data types more complicated structure: e.g., specify data type ordered list, or represent lists using self-balancing binary search trees.

when creating module, think easy recognize when able provided polymorphic functions , when need parameterized on type(s). seems more difficult, me, figuring out kind of modules should depend on when working on further down stream.

in general terms, question this: when designing system of variously related modules, how can figure out whether design around modules providing polymorphic functions or modules generated using functors parameterized on types , values?

i hope illustrate dilemma , why matters following example, taken toy project working on.

i have functor postfix (st:stack) : calculator_syntax. takes implementation of stack data structure , produces parser reads concrete postfix ("reverse polish") notation abstract syntax (to evaluated calculator module down stream), , vice-versa. now, had been using standard stack interface provides polymorphic stack type , number of functions operate on it:

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 

this works fine, , gives me flexibility, can use list-based stack or vector-based stack, or whatever. but, want add simple logging function stack module, every time element pushed to, or popped from, stack, prints out current state of stack. need fun tostring : 'a -> string type collected stack, , this, understand, cannot incorporated stack module. need seal type module, , parameterize module on type collected in stack , tostring function let me produce printable representation of collected type. need like

functor stackfn (type t                  val tostring: t -> string ) = struct    ... end 

and not produce module matching stack signature, since doesn't provide polymorphic type. thus, must change signature required postfix functor. if have lot of other modules, have change of them well. inconvenient, real problem can no longer use simple list-based, or vector-based stack modules in postfix functor when don't want logging. now, seems, have go , rewrite modules have sealed type well.

so return to, expand upon, , (mercifully) finish question:

1. is there way of specifying signature of modules produced stackfn they'll end "special cases" of stack?
2. alternatively, there way of writing signature postfix module allow both modules produced stackfn , satisfy stack?
3. generally speaking, there way of thinking relation between modules me catch/anticipate kind of thing in future?

(if you've read far. thank much!)

as discovered, there tension between parametric polymorphism , functors/module in sml , ocaml. due "two language" nature of modules , lack of ad hoc polymorphism. 1ml , modular implicits both provide different solutions problem. first unifying 2 kind of parametrism, later allowing sparkle ad-hoc polymorphism when needed.

back practical considerations. functors, it's easy (but verbose/annoying) monomorphise given datastructure. here example (in ocaml). this, can still write generic implementations , specialize them later on (by providing printing function).

module type polystack = 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   val tostring : ('a -> string) -> 'a stack -> string end  module type stack = sig   type elt   type t   exception emptystack    val empty : t   val isempty : t -> bool    val push : (elt * t) -> t   val pop  : t -> t   val top  : t -> elt   val poptop : t -> t * elt   val tostring : t -> string end  module type printable = sig   type t   val tostring : t -> string end  module make (e : printable) (s : polystack)   : stack type elt = e.t , type t = e.t s.stack = struct   type elt = e.t   type t = e.t s.stack   include s   let tostring = s.tostring e.tostring end  module addlogging (s : stack)   : stack type elt = s.elt , type t = s.t = struct   include s   let push (x, s) =     let s' = s.push (x, s) in print_string (tostring s') ; s' end