Структура данных словаря на языке логотипа (хранилище ключей / значений)

Question

Мне интересно, есть ли реализация структуры данных словаря первого класса, доступная для использования на языке Logo? Я не вижу ни одного доступного в документации логотипа UCB или логотипа FMS. Я вижу, что есть списки свойств, но они не относятся к первому классу, и похоже, что это списки ассоциаций с линейным поиском. Я ищу что-то на основе хешей или деревьев. Кажется, там было много исторических Логосов, и, возможно, кто-то реализовал что-то подобное. Кроме того, если кто-нибудь знает о хранилище кода логотипа, я был бы признателен за указатели (например, CPAN для логотипа).

Answer 1

Вот реальная упрощенная реализация чисто функционального дерева на основе списков. Ключи могут быть словами или цифрами. Пустой список - это пустой словарь. Это не самобалансировка, поэтому вам придется вызывать "rebalance" самостоятельно после выполнения вставок с помощью "dict_add". Не делайте этого много, так как "перебалансировка", как реализовано, занимает O(n) время. Процедура "тестирования" немного тренирует вещи.

to dict_lookup :dict :key
   if (empty? :dict) [output []]
   localmake "pair first :dict
   if (empty? :pair) [output []]
   localmake "test_k first :pair
   if (equal? :key :test_k) [output last :pair]
   output dict_lookup (ifelse (before? :key :test_k) [left_tree :dict] [right_tree :dict]) :key
end

to left_tree :dict
    output item 2 :dict
end

to right_tree :dict
    output item 3 :dict
end

to dict_add :dict :key :value
    localmake "new_pair (list :key :value)
    if (empty? :dict) [output (list :new_pair [] [])]
    localmake "old_pair first :dict 
    localmake "old_key first :old_pair

    localmake "l_tree left_tree :dict
    localmake "r_tree right_tree :dict

    if (equal? :key :old_key) [output (list :new_pair :l_tree :r_tree)] 
    ifelse (before? :key :old_key) [
        localmake "l_tree dict_add l_tree :key :value] [
        localmake "r_tree dict_add r_tree :key :value]
    output (list :old_pair :l_tree :r_tree)
end

to in_order :dict
    if (empty? :dict) [output []]
    output (sentence (in_order (left_tree :dict)) 
                     (list (first :dict))
                     (in_order (right_tree :dict)))
end

to draw_tree :dict :size
    if (empty? :dict) [label [[]] stop]
    rt 50 fd :size lt 50
        draw_tree (left_tree :dict) :size * 0.7 
    rt 50 bk :size lt 50
    label (first :dict)
    lt 50 fd :size rt 50 
        draw_tree (right_tree :dict) :size * 0.7
    lt 50 bk :size rt 50
end

to list_to_tree :l
    if (empty? :l) [output []]
    localmake "half int (count :l)/2
    localmake "firsts take :half :l
    localmake "rests drop :half :l
    output (list (first :rests) (list_to_tree :firsts) (list_to_tree bf :rests))
end

to take :n :l
    if (or (empty? :l) (:n < 1)) [output []]
    output fput (first :l) take :n-1 bf :l
end

to drop :n :l
    if (:n < 1) [output :l]
    output drop :n-1 bf :l
end

to rebalance :dict
   output list_to_tree in_order :dict
end

to testing
    localmake "test_dict []
    localmake "items [[apple 1] [ball 2] [banana 3] [cat 4] [zebra 5] 
                      [toy 6] [yak 7] [jump 8]]
    foreach :items [make "test_dict (dict_add :test_dict (first ?) (first bf ?))]
    cs pu
    lt 60 fd 500 setheading 180 pd 
        draw_tree :test_dict 200
    pu lt 90 fd 700 setheading 180 pd 
        draw_tree (rebalance :test_dict) 160
end

Answer 2

Это правда, что в списках недвижимости FMSLogo нет граждан первого класса. Тем не менее, список свойств "имена" первого класса. Также версия 6.32.0 FMSLogo реализует списки свойств в виде деревьев AVL. Это задокументировано здесь: http://sourceforge.net/p/fmslogo/feature-requests/94/