Я пытаюсь сделать так, чтобы каждый узел имел вес, равный числу его детей. - PullRequest
Новая
       36

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

0 голосов
/ 26 мая 2019

Мне нужно сделать три, чтобы рассчитать выигрышный приз лотерейных билетов с фиксированной функцией Для функции мне нужно знать, сколько детей имеет каждый узел. Сначала мне нужно создать три, а затем выполнить поиск, чтобы найти, сколько билетов выиграно. Обратите внимание, что я новичок в SML, поэтому у меня действительно нет большого опыта. Я нашел похожий код (ссылка ниже) в другом посте, который я пытаюсь изменить. Вставка значений в Trie

Проблема с этим кодом в том, что я не могу изменить вес узла, когда я прохожу через дерево. Например: если я уже вставил число 1234 (начиная слева направо), каждый узел будет иметь вес 1. Если я хочу добавить число 1255, я бы хотел изменить вес узлов 1 и 2, которые являются то же самое к 2 (+1 в основном).

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

Я попытался снова вызвать функцию вставки с узлом, я хочу увеличить его вес на 1, но я получаю сообщение об ошибке, относящееся к типам данных. Я пытался изменить типы данных узла, но я получаю больше ошибок 

signature DICT = sig
  type key = string                 (* concrete type *)
  type 'a entry = key * 'a          (* concrete type *)

  type 'a dict                      (* abstract type *)

  val empty : 'a dict
  val lookup : 'a dict -> key -> 'a option
  val insert : 'a dict * 'a entry -> 'a dict
  val toString : ('a -> string) -> 'a dict -> string
end;  (* signature DICT *)

exception InvariantViolationException

structure Trie :> DICT = 
struct
  type key = string
  type 'a entry = key * 'a

  datatype 'a trie = 
    Root of 'a option * 'a trie list
  | Node of 'a option * char * 'a trie list

  type 'a dict = 'a trie

  val empty = Root(NONE, nil)

  (* val lookup: 'a dict -> key -> 'a option *)
  fun lookup trie key =
    let
      (* val lookupList: 'a trie list * char list -> 'a option *)
      fun lookupList (nil, _) = NONE
        | lookupList (_, nil) = raise InvariantViolationException
        | lookupList ((trie as Node(_, letter', _))::lst, key as letter::rest) =
            if letter = letter' then lookup' (trie, rest)
            else lookupList (lst, key)
        | lookupList (_, _) =
            raise InvariantViolationException
      (*
        val lookup': 'a trie -> char list
      *)
      and lookup' (Root(elem, _), nil) = elem
        | lookup' (Root(_, lst), key) = lookupList (lst, key)
        | lookup' (Node(elem, _, _), nil) = elem
        | lookup' (Node(elem, letter, lst), key) = lookupList (lst, key)
    in
      lookup' (trie, explode key)
    end

  (*
    val insert: 'a dict * 'a entry -> 'a dict
  *)
  fun insert (trie, (key, value)) = 
    let
      (*
        val insertChild: 'a trie list * key * value -> 'a trie list
        Searches a list of tries to insert the value. If a matching letter 
        prefix is found, it peels of a letter from the key and calls insert'. 
        If no matching letter prefix is found, a new trie is added to the list.
        Invariants:
          * key is never nil.
          * The trie list does not contain a Root.
        Effects: none
      *)
      fun insertChild (nil, letter::nil, value) =[ Node(SOME(value), letter, nil) ]
        | insertChild (nil, letter::rest, value) = [ Node(SOME(value), letter, insertChild (nil, rest, value)) ]
        | insertChild ((trie as Node(SOME(oldvalue), letter', _))::lst, key as letter::rest, value) = 
            if letter = letter' then
                let
                    val newvalue = oldvalue+1
                    val ltrie=insertChild(trie::lst,letter'::nil, newvalue)
                    val trie = hd ltrie
                in
                    insert' (trie, rest, value) :: lst
                end
            else
              trie :: insertChild (lst, key, value)
        | insertChild (Root(_,_)::lst, letter::rest, value) = raise InvariantViolationException
        | insertChild (_, nil, _) = (* invariant: key is never nil *)raise InvariantViolationException

      (*val insert': 'a trie * char list * 'a -> 'a trie
Invariants:* The value is on the current branch, including potentially the current node we're on.* If the key is nil, assumes the current node is the destination.Effects: none*)

      and insert' (Root(_, lst), nil, value) = Root(SOME(value), lst)
        | insert' (Root(elem, lst), key, value)=Root(elem,insertChild(lst,key, value))
        | insert' (Node(_, letter, lst), nil, value)=Node(SOME(value),letter,lst)
        | insert' (Node(elem, letter, lst), key, value)=Node(elem,letter,insertChild (lst, key, value))
    in
      insert'(trie, explode key, value)
    end

Я получил ошибку в следующих строках: 

val newvalue = oldvalue+1
val ltrie = insertChild (trie::lst, letter'::nil, newvalue)

Результат: 

Error:
lott.sml:72.10-72.31 Error: operator and operand do not agree [overload conflict]
  operator domain: [+ ty] * [+ ty]
  operand:         'Z option * [int ty]
  in expression:
  oldvalue + 1
...