Определяется порядок над множеством:

signature Ordered =
  (* a totally ordered type and its compairsion functions *)
sig
  type T

  val eq:  T * T -> bool
  val lt:  T * T -> bool
  val leq: T * T -> bool
end

Затем определяется множество с операциями insert и member:

functor UnbalancedSet (Element: Ordered): Set =
struct
  type Elem = Element.T
  datatype Tree  = E | T of Tree * Elem * Tree
  type Set = Tree

  val empty = E

  fun member (x, E) = false
    | member (x, T (a,y,b)) =
        if      Element.lt (x,y) then member (x,a)
        else if Element.lt (y,x) then member (x,b)
        else true

  fun insert (x, E) = T (E, x, E)
    | insert (x, s as T (a, y, b)) =
        if Element.lt (x,y) then T (insert (x,a), y, b)
        else if Element.lt (y,x) then T (a, y, insert (x,b))
        else s
end

Exercise 2.2

In the worst case member performs approximately 2d comparisons, where d is the depth of the tree. Rewrite member to take no more than d+1 comparisons by keeping track of a candidate element that might be equal to the query element (say, the last element for which < returned false of <= returned true) and checking for equality only when you hit bottom of the tree.

> checking for equality only when you hit bottom of the tree.

В таком случае member будет корректно работать только x вида Tree (E, x, E), а для остальных - нет.

Как можно управиться за d+1, если проверку на равенство придётся делать на каждой итерации?

Задание, видимо, совершенно дебильное. Жаль непонятно, что предполагается реализовать автором.

Объясните.

ну и

>>27164
У меня вытекли глоза от твоего ml'я и я не стал ничего отвечать. Либо автор имел ввиду leaf tree... Нет. Он наверно подразумевал что надо складывать x в список, аккумулировать в процессе спуска, и только когда спустились до листа глядеть в списочек.
`member :: a -> UnbalancedSet a -> Bool
member x = go
   where go :: UnbalancedSet a -> [a] -> Bool

    go E acc         = elem x acc
    go (T a y b) acc | x < y     = go a (y : acc)
                     | otherwise = go b (y : acc)`

Алсо два месяца прошло...

>>25080
Ну, собственно говоря тут написано как - by keeping track of a candidate element that might be equal to the query element (say, the last element for which < returned false of <= returned true), хотя, согласен, несколько неочевидно. Автор предлагает сравнивать, допустим, только на "меньше" (соответственно вторая ветвь условия будет на "больше-равно"), но при этом передавать в member ещё и последнего возможного кандидата на равенство (того, для которого сравнение на "меньше" вернуло ложь). А дойдя до листа, проверять на равенство с этим кандидатом (лишь один раз за спуск).

Теперь остаётся немного поразмыслить, чтобы понять, что последний возможный кандидат является ещё и единственным. Если в сравнении искомого элемента с неким A проверка дала "больше-равен", то A - первый наш кандидат. Дальше идём в правое поддерево и сравниваем с B. Если результат - "меньше", то всё в порядке, A остаётся нашим кандидатом. А вот если результат опять "больше-равен", то A уже никак не может являться кандидатом, ведь если A равен искомому элементу, то этот элемент при сравнении с B обязан дать "меньше". Соответственно новый и единственный кандидат на равенство - B.

Этот алгоритм всегда спускается до низу.
member x = let go E (y:_) = y == x

           go E _           = False
           go (T a y b) acc = if x < y then go a acc else go b (y : acc)  
       in flip go []

>>27175
>>27179

Может сперва обратите внимание на заданный вопрос? Вопрос был в том, как уменьшить число сравнений с 2d до d + 1, где d - глубина дерева.
  
'fun member (x, E, eq) = Element.eq (x, eq)
   | member (x, T (a,y,b), eq) =

   if Element.lt (x, y)then member (x, a, eq)
   else member (x, b, y)'

Ты нажрался там что ли? В >>27179 d + 1 сравнений.

>>27184
Сравнений то там d + 1, но список игреков то зачем с собой по всем вызовам таскать, когда достаточно лишь последнего?

>>27185
А в чем проблема? Можно и не список таскать. а дерево :3