Разбиране на признаци и структури с прехвърляне на вграден тип списък към персонализиран тип стек

Да предположим, че имам началото на дефиницията за стек като следното:

signature STACK = sig
  type 'a stack
end;

structure Stack :> STACK = struct
  type 'a stack = 'a list
end;

Очевидно това не работи, защото не мога да прехвърля списък към стек:

- [5] : int Stack.stack;
stdIn:1.2-1.23 Error: expression doesn't match constraint [tycon mismatch]
  expression: int list
  constraint: int Stack.stack
  in expression:
    5 :: nil: int Stack.stack

Което означава, че ако направя функция Stack.push или Stack.pop, не мога да предам int списъка, защото ще очаква стек.

Иска ми се да знам повече за Standard ML, за да формулирам истински въпрос, просто знам, че това не работи и не съм сигурен как да подходя към подписите и структурите.


sml smlnj
person AJcodez    schedule 25.08.2013    source източник

Отговори (2)


arrow_upward
5
arrow_downward

Когато декларирате структурата си, вие го правите чрез непрозрачно съвпадение на подпис (:>).

Това, което означава съпоставяне на непрозрачен подпис, е, че основният тип зад всички типове, декларирани вътре в структурата, е скрит.

Можете да използвате прозрачно съвпадение на подпис (:), ако не желаете това да е така.

Пример с прозрачно съпоставяне на подписа:

structure Stack : STACK = struct
  type 'a stack = 'a list
end;

Преди да направите това, помислете за предимствата да не го правите: Ако използвате непрозрачно съпоставяне на подписи, основната реализация е скрита. Ако желаете да промените основната реализация (на дървовидна структура, например), можете да го направите, като знаете, че нищо извън структурата не може да използва други функции освен тези, които предоставяте.

Може вместо това да предоставите функция toList и fromList за извършване на преобразуването:

(* in the signature *)
val toList : 'a stack -> 'a list
val fromList : 'a list -> 'a stack

(* in your structure *)
fun toList s = s
fun fromList s = s

Ако след това промените основната си реализация, ще трябва да промените само тези две функции, вместо да правите промени в цялата си програма.

person Sebastian Paaske Tørholm    schedule 25.08.2013

arrow_upward
3
arrow_downward

Създаването на функции toList и fromList, както предлага Себастиан, е много добре. Като алтернатива можете да създадете по-рестриктивен интерфейс, който не позволява директно импортиране и експортиране, а само създаване от push, pop и empty:

signature STACK =
sig
  type 'a stack
  val push : 'a -> 'a stack -> 'a stack
  val pop : 'a stack -> ('a * 'a stack)
  val peek : 'a stack -> 'a
  val empty : 'a stack
end

structure LStack :> STACK =
struct
  type 'a stack = 'a list
  fun push = ...
  fun pop = ...
  fun peek = ...
  val empty = []
end
person Simon Shine    schedule 29.08.2013