Стандарт ML: функция поиска в двоичном дереве поиска

Question

Я прокладываю себе путь через элементы Ullman's ML программирования ML. Он вводит тип данных для BST в гл. 6 следующим образом:

datatype 'label btree = 
    Empty | 
    Node of 'label * 'label btree * 'label btree; 

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

fun lookup lt Empty x = false 
    | lookup lt (Node(y, left, right)) x = 
     if lt(x, y) then lookup lt left x 
     else if lt(y, x) then lookup lt right x 
     else true; 

ML говорит нам, что функция имеет тип:

val lookup = fn : ('a * 'a -> bool) -> 'a btree -> 'a -> bool 

1) У меня возникли проблемы с разбором того, что указано выше. Я знаю, что «->» ассоциируется справа, но у меня возникают проблемы при сортировке, как это сделать. Как бы вы знали, как это сделать, просто взглянув на вышеизложенное?

val lookup = fn : ('a * 'a -> bool) -> ('a btree) -> ('a) -> (bool) 

2) Я запутался, хотя, потому что я думал, выделанная функция создает цепочку функций, которые возвращают другую функцию с каждым последующим аргументом. Но, основываясь на типах ML, которые дают мне выше, похоже, что это не карри. Любая идея, что здесь происходит?

Спасибо за помощь, bclayman

Answer 1

val lookup = fn : ('a * 'a -> bool) -> 'a btree -> 'a -> bool Тип говорит нам, что он принимает аргумент типа ('a * 'a -> bool) и возвращает функцию типа 'a btree -> 'a -> bool. Затем эта функция принимает что-то типа 'a tree и возвращает функцию типа 'a -> bool, которая затем принимает аргумент типа 'a и возвращает bool. Так что да, функция lookup. Однако первый параметр (который также является функцией) не имеет значения, поскольку он принимает два аргумента, завернутых в пару. В общем, вы можете взять каррированной функцию (то есть один, который принимает аргумент и возвращает функцию) и превратить его в uncurried функцию следующим образом:

Допустим, у вас есть следующие функции

fun f e1 e2 e3 ... = e 

типа

'a -> 'b -> 'c -> ... -> 'res 

Мы можем uncurry этой функции путем обертывания всех входов в кортеже, такие как

fun f(e1, e2, e3, ...) = e 

Которые тогда будут иметь тип

'a * 'b * 'c * ... -> 'res