Могу ли я избежать фиксации определенных типов в типе модуля и при этом получить сопоставление с образцом?

Question

У меня есть два типа модулей:

module type ORDERED =
    sig
        type t
        val eq  : t * t -> bool
        val lt  : t * t -> bool
        val leq : t * t -> bool
    end
module type STACK =
    sig
        exception Empty 
        type 'a t
        val empty   : 'a t
        val isEmpty : 'a t -> bool  
        val cons        : 'a * 'a t -> 'a t
        val head        : 'a t -> 'a
        val tail        : 'a t -> 'a t
        val length  : 'a t -> int
    end

Я хочу написать функтор, который "поднимает" отношение порядка с базового типа ORDERED до STACKs этого типа.Это можно сделать, сказав, что, например, два стека элементов будут равны, если все его отдельные элементы равны.И что стеки s1 и s2 являются st s1

module StackLift (O : ORDERED) (S : STACK) : ORDERED =  
  struct
    type t = O.t S.t
    let rec eq (x,y) =
      if S.isEmpty x
        then if S.isEmpty y
        then true
            else false
    else if S.isEmpty y
        then false
        else if O.eq (S.head x,S.head y)
            then eq (S.tail x, S.tail y)
            else false
     (*  etc for lt and leq  *)
  end

, что является очень неуклюжим способом выполнения сопоставления с шаблоном.Альтернативой может быть навязывание определения типа STACK.t с использованием явных конструкторов, но это в некоторой степени связывает мой модуль general с конкретной реализацией, чего я не хочу делать.* Вопрос : могу ли я определить что-то другое выше, чтобы я мог все еще использовать сопоставление с образцом, сохраняя при этом общность типов модулей?

Answer 1

В качестве альтернативы или дополнения к другим функциям доступа модуль может предоставить функцию просмотра, которая возвращает тип варианта для использования при сопоставлении с образцом.

type ('a, 's) stack_view = Nil | Cons of 'a * 's

module type STACK =
sig
  val view : 'a t -> ('a , 'a t) stack_view
  ...
end

module StackLift (O : ORDERED) (S : STACK) : ORDERED =
struct
  let rec eq (x, y) =
    match S.view x, S.view y with
        Cons (x, xs), Cons (y, ys) -> O.eq (x, y) && eq (xs, ys)
      | Nil, Nil -> true
      | _ -> false
  ...
end

Любой стек с функциями head и tail также может иметь функцию view, независимо от базовой структуры данных.

Answer 2

Полагаю, вы ответили на свой вопрос.Тип модуля в ocaml - это интерфейс, за которым вы не можете смотреть.Иначе нет смысла.Вы не можете сохранить общность интерфейса, раскрывая детали реализации.Единственное, что вы можете использовать, - это то, что было открыто через интерфейс.

Мой ответ на ваш вопрос: да, возможно, вы можете сделать что-то с определением стека, что сделает тип стеканемного сложнее, что делает его соответствующим другому шаблону, чем просто одно значение, например, (val,val).Тем не менее, у вас есть точное определение стека, с которым можно работать, и добавление большего количества типов-пух, вероятно, является плохой идеей.

Некоторые предложения относительно ваших определений:

1. Переименуйте следующие функции: cons => push, head => peek, tail => pop_.Я бы также добавил функцию val pop : 'a t -> 'a * 'a t, чтобы объединить head и tail в одну функцию, а также отразить cons.Ваша текущая схема именования подразумевает, что список поддерживает ваш стек, что является ментальной утечкой реализации: D.
2. Почему eq, lt и leq принимают пару запервый параметр?Ограничивая тип eq значением val eq : 'a t * 'a t -> 'a t, вы заставляете программиста, который использует ваш интерфейс, держать одну сторону предиката равенства до тех пор, пока они не получат другую сторону, прежде чем, наконец, применить функцию.Если у вас нет веских причин, я бы использовал стандартную карри-форму функции, поскольку она предоставляет пользователю немного больше свободы (val eq : 'a t -> 'a t -> 'a t).Свобода заключается в том, что они могут частично применять eq и передавать функцию вместо значения и функции вместе.