В Standard ML, как я могу определить функцию типа 'a *' a -> bool? - PullRequest
Новая
       48

В Standard ML, как я могу определить функцию типа 'a *' a -> bool?

1 голос
/ 15 марта 2012

Я пытаюсь создать функцию в Standard ML, которая принимает 2 параметра и возвращает логическое значение, и эти 2 параметра могут быть любого типа, в спецификациях написано, что это 'a * 'a -> bool, но всякий раз, когда я пытаюсь это сделать, 2 параметра вводятся автоматически. Как я могу заставить функцию принимать 2 параметра типа 'a.

следующее - функция, которую я пытался реализовать: 

fun lessThan (a, b) = 
    if a < b then true
    else false;

но после написания вышеупомянутой функции я получаю: 

val lessThan = fn : int * int -> bool

и что я хочу это: 

val lessThan = fn : 'a * 'a -> bool

Что я могу сделать, чтобы это работало?

Ответы [ 2 ]

6 голосов
/ 17 марта 2012

Если вы хотите, чтобы функции завершались и возвращали значение, Standard ML имеет только две функции типа 'a * 'a -> bool.Они 

fun ktrue  (_, _) = true
fun kfalse (_, _) = false

Все остальные чистые функции этого типа неотличимы от двух вышеприведенных.

И эти две функции на самом деле имеют более общий тип 'a * 'b -> bool.

Это на самом деле довольно глубокий результат теории языка программирования.Если вы хотите изучить основы, вы можете попробовать прочитать работу Джона Рейнольдса о независимости представления или работу Фила Уодлера о «свободных теоремах».

0 голосов
/ 22 апреля 2013

Я считаю, что такую ​​проблему мы можем решить с помощью функтора в SML.

Например, рассмотрим существование подписи TOTALORDER, которая определяет вашу функцию в вопросе (lt означает ниже, чем). 

signature TOTALORDER = 
sig
    type element
    val lt: element * element -> bool
end

Как видите, функция определена как element * element -> bool, а тип элемента здесь не определен.

Затем мы можем определить две разные реализации TOTALORDER для работы с разными типами следующим образом: 

structure String : TOTALORDER =
struct
    type element = string
    fun lt(a:string, b) = a < b
end

structure Integer: TOTALORDER = 
struct
    type element = int
    fun lt(a, b) = a < b
end

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

Теперь мы можем определить магию сменных типов в функторе следующим образом: 

functor MakeComparator(Lt: TOTALORDER):
    sig
        val descending : Lt.element * Lt.element -> Lt.element * Lt.element
        val ascending : Lt.element * Lt.element -> Lt.element * Lt.element
    end
    =
    struct
        open Lt;

        fun descending(a,b) = if lt(a,b) then (b,a) else (a,b)
        fun ascending(a,b) = if lt(a,b) then (a,b) else (b,a)
    end

И здесь мы видим, что функтор определяет сигнатуру с двумя функциями, называемыми восходящим и нисходящим, на основе нашего определения TOTALORDER. Функтор получает в качестве параметра реализацию такой подписи. А позже он использует его в реализации Struc для сортировки пары в порядке возрастания или убывания.

Таким образом, в конечном счете, типы a и b зависят от типа элемента в реализации TOTALORDER, предоставленной функтору.

Теперь мы можем создавать разные реализации, используя разные типы сравнения следующим образом: 

structure StringComparator = MakeComparator(String)
structure IntegerComparator = MakeComparator(Integer)

И мы можем использовать их соответственно с их типами. Например: 

val res01 = StringComparator.ascending("arm","house") (*(arm,house)*)
val res02 = StringComparator.descending("arm","house") (*(house,arm)*)
val res03 = IntegerComparator.ascending(1,2) (*(1,2)*)
val res04 = IntegerComparator.descending(1,2) (*(2,1)*)

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

...