Проблемы реализации полиморфного стека

Question

Я пытаюсь написать PolishCalculator в качестве функтора, который получает реализацию стека, придерживаясь интерфейса StackADT, и использует его для вычисления выражений, записанных в этой записи.

Итак, я начал писатьинтерфейс для стека, и это выглядит так:

module type StackADT = 
sig
    type 'a stack
    val empty : 'a stack
    val pop : 'a stack -> 'a
    val push : 'a -> 'a stack -> unit
    val is_empty : 'a stack -> bool
end;;

А потом я попробовал конкретную реализацию следующим образом:

module MyStack : StackADT = 
struct
    type 'a stack = {mutable c: 'a list}

    exception EmptyStackException

    let empty = {c = []}

    let pop stack = match stack.c with
    |[]-> raise EmptyStackException
    |h::tl -> stack.c <- tl; h

    let is_empty stack = match stack.c with
    |[] -> true
    |_ -> false 

    let push n stack = stack.c <- n::stack.c
end;;

Моя проблема сейчас заключается в том, что когда я пытаюсь скомпилировать MyStackмодуль я получаю сообщение об ошибке:

   Values do not match:
     val empty : '_weak5 stack
   is not included in
     val empty : 'a stack
   File "StackADT.mli", line 4, characters 1-21: Expected declaration
   File "MyStack.ml", line 7, characters 5-10: Actual declaration

Я понимаю, что проблема заключается в том, что в конкретной реализации тип стека не определяется, пока мы не поместим элемент в стек, в то время как интерфейс требуетстек, который должен быть набран уже после вызова empty, но есть ли способ заставить эту штуку работать?

Спасибо

Answer 1

В вашем интерфейсе, когда вы пишете:

val empty: 'a stack

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

Это не то, что происходит в вашей реализации, поскольку тип 'a stack является изменяемым.

Одно из исправлений заключается в замене этого пустого общего значения на пустой генератор значений:

val empty: unit -> 'a stack