В эрланге есть паттернматчинх и эксепшены. Первым проверяешь идентичность, вторым вылазиш на начало и кричишь «неравны».

Можно на Scheme/Java/C++/чём угодно

Бросить исключение

Бросить исключение

А продолжить потом как?

Проблема вот в чём: обходчик walk-tree может вызвать функцию для каждого элемента дерева в заданном порядке. Алгоритм в теме передаёт в обходчик функцию, которая берёт элемент, запоминает продолжение, затем возвращает элемент. Затем запускается обходчик на втором дереве, который также после каждого элемента передаёт управление наверх, а потом через продолжение получает обратно. Так вот исключение бросить наверх я могу, а вернуться в ту же точку дерева потом как?

А продолжить потом как?

А зачем?

В эрланге есть паттернматчинх и эксепшены. Первым проверяешь идентичность, вторым вылазиш на начало и кричишь «неравны».

Можешь набросать пример? Основной вопрос, как вернуться в обходы деревьев, если равны.

(and

(walk-tree fn (car tree))

Это ещё зачем? Если в левой ветке нет элементов, то правую не проверяем? walk-tree — это for-each, но для дерева.

Я, честно, в код особо не вчитывался. Если смотреть с колокольни С++, то зачем куда-то возвращаться, когда обнаружили, что два узла в дереве не равны? Кинули исключение, наверху поймали и всё поняли.

А зачем?

Тогда как ещё получить элементы второго дерева? Если бы был просто поиск элемента, то проблем нет. Но нам надо после каждого элемента запустить обходчик по второму дереву на один элемент и вернуться обратно.

Так вот исключение бросить наверх я могу, а вернуться в ту же точку дерева потом как?

Очевидно, что уолкер должен быть объектом, запоминающим своё состояние.

Блин, я щас в кино и с телефона писать не удобно.

Если смотреть с колокольни С++,

Как с колокольни C++ одновременно запустить рекурсивный перебор для двух коллекций. Вот у тебя

struct Tree {
   Tree *left;
   Tree *right;
   int data;
}

Рекурсивный спуск пишется тривиально (walk-tree из примера). Но как из одной рекурсии получать соответствующие элементы из второй рекурсии?

Очевидно, что уолкер должен быть объектом, запоминающим своё состояние.

Типа делать стек вручную? Усложнение однако.

Если говорить о Common Lisp, а тебя как лиспера это должно интересовать), то generic-sequences для решения подобных задач и создавался. Продолжения можно тянуть и без call/cc, и без синтаксического сахара для монад.

KISS

static bool cmp(Tree* t1, Tree* t2) {
    if (t1 && !t2) throw OOPS;
    if (!t1 && t2) throw OOPS;
    if (!t1 && !t2) return true;
    if (t1->data != t2->data) throw OOPS;
    return cmp(t1->left, t2->left) && cmp(t1->right, t2->right);
}

Разве нет? Если же вопрос в том, чтобы при этом не жрать стэк (каюсь, код в ОП пристально не смотрел), то рекурсию же можно смоделировать на куче.

должен быть объектом, запоминающим своё состояние.

Что-то попытался из walk-tree такое сделать — сплошная фиггня выходит... Можешь написать, как он должен выглядеть, чтобы можно было элементы по одному получать (вроде этого достаточно). В смысле чтобы было что-то типа

(define (walk-tree fn tree)
  (define gen (walk-tree-gen tree))
  (let loop ((next (gen))
     (fn next)
     (loop)))

Как должен выглядеть walk-tree-gen?

Разве нет?

В минусе только то, что алгоритм обхода стал интегрирован в функцию сравнения. В остальном всё верно.

то generic-sequences для решения подобных задач и создавался.

А можешь для приведённой задачи решение на них набросать?

Раскрою мысль из предыдущего поста.

Создаем обобщеную последовательность, которая лениво обходит элементы дерева. Мутабельного явного состояния нет, но там хранятся продолжения. Вся сложная махинерия создается через простой макрос enum-cons. Поэтому обходить можно даже гигантские деревья.

А дальше все просто. Два дерева дают две обобщенные последовательности, которые и сравниваются через seq-equal.

Решение у меня было подобной задачи. Боюсь, сейчас уже не найду. Спать охота) А идею описал выше. Код был реальный, и он работал.

def compare(a, b):
  if a is None:
    return b is None
  if b is None:
    return False

  return a.data == b.data and compare(a.left, b.left) and compare(a.right, b.right)

в чем сложность-то?

Создаем обобщеную последовательность, которая лениво обходит элементы дерева

Вот на этом месте и проблемы. В C++ «создаём итератор для дерева...» и т.д. Но как должен работать итератор для дерева или для алгоритма Дейкстры по графу я не очень представляю. Если не считать вырожденного случая: из обходчика соберём все элементы в список, а затем по нему уже будет итератор.

алгоритм обхода стал интегрирован в функцию сравнения

Я бы сказал, наоборот, сравнение внутри функции обхода. Так его можно и коллбэком сделать.

в чем сложность-то

Можешь сделать compare независимым от алгоритма обхода? В смысле, обход в одной функции, а сравнение в другой. Например, чтобы обход можно было в поиске использовать. И в получении списка элементов. Единообразно.

Так его можно и коллбэком сделать

Пусть у нас несколько (много) структур. Надо для них сделать поиск, сравнение, преобразование в список, ...

Как отделить в сравнении/поиске/... (коллбэком?) нужные данные, чтобы для каждого типа не переписывать все алгоритмы.

В общем задача свелась к «как написать итератор для дерева или другой рекурсивнообходимой структуры».

Под generic-sequences ты имеешь в виду конкретную библиотеку или общую идею? Если библиотеку, то хочу ссылку. Series, вроде, не совсем то.

Я не вчитывался в код, но, может, попробовать реализовать продолжения посредством continuation-passing style? Суть должна получиться такой же, как и с call/cc, но над кодом придётся поломать голову. Правда, такой подход прокатит разве что для Common Lisp, во всех других языках на тебя потом будут ругаться, потому что там принято делать такие вещи через объект с явным хранением состояния.

А продолжить потом как?

Проблема вот в чём: обходчик walk-tree может вызвать функцию для каждого элемента дерева в заданном порядке. Алгоритм в теме передаёт в обходчик функцию, которая берёт элемент, запоминает продолжение, затем возвращает элемент. Затем запускается обходчик на втором дереве, который также после каждого элемента передаёт управление наверх, а потом через продолжение получает обратно. Так вот исключение бросить наверх я могу, а вернуться в ту же точку дерева потом как?

SICP Lecture 6 — Streams.

Я не вчитывался в код, но, может, попробовать реализовать продолжения посредством continuation-passing style?

Тогда уж сразу cl-cont. Будут те же продолжения.

делать такие вещи через объект с явным хранением состояния.

Состояние может быть большим и неудобным. Например, для того же алгоритма Дейкстры состоянием будет множество точек графа. С другой стороны, объём памяти на итератор и на продолжение полностью сопадает. Вот только алгоритм итератора будет гораздо более громоздкий, так как алгоритм перестаёт быть рекурсивным. А при наличии call/cc можно вообще делать такие вещи:

(define (walker->iterator walker collection)
  (define caller #f)
  (define (yield-cont)
    (walker proc collection)
    (caller #f))     
  (define (yield)
    (call/cc
     (lambda (k)
       (set! caller k)
       (yield-cont))))
  (define (proc x)
    (call/cc
     (lambda (continue)
       (set! yield-cont (lambda () (continue #f)))
       (caller x))))
  yield)

> (define gen (walker->iterator map '(1 2 3 4 5)))
> (gen)
1
> (gen)
2
> (gen)
3
> (gen)
4
> (gen)
5
> (gen)
#f

Из любого обходчика делает итератор.

SICP Lecture 6 — Streams.

Ну и как сделать stream из walk-tree?

Это ещё зачем?

Чтобы сделать то, что ты хочешь:

Надо сравнить два дерева. Причём деревья большие. Поэтому, если не равны, то алгоритм должен прерываться на первом несовпавшем элементе

Замени begin на and и получишь в точности то, что нужно.

Тогда как ещё получить элементы второго дерева?

А зачем их получать?

Если бы был просто поиск элемента, то проблем нет. Но нам надо после каждого элемента запустить обходчик по второму дереву на один элемент и вернуться обратно.

Объясни конкретно что тебе надо сделать. Потому что по описанию из первого поста задача решается полностью заменой begin на and

В сравнении деревьев нет ничего сложного. Видимо, тебе нужно что-то еще? В твоем коде ничего не понял, ибо про продолжения знаю только в теории, а лисповый синтаксис сводит меня с ума. Можешь более четко сформулировать?

Например, чтобы обход можно было в поиске использовать. И в получении списка элементов. Единообразно.

Сделать обход ленивым.

Проблема вот в чём: обходчик walk-tree может вызвать функцию для каждого элемента дерева в заданном порядке. Алгоритм в теме передаёт в обходчик функцию, которая берёт элемент, запоминает продолжение, затем возвращает элемент. Затем запускается обходчик на втором дереве, который также после каждого элемента передаёт управление наверх, а потом через продолжение получает обратно. Так вот исключение бросить наверх я могу, а вернуться в ту же точку дерева потом как?

Ну так сделай так же на плюсах. Через сопрограмы. Со стеком или без на твое усмотрение. Но вообще это не нужно. Напиши просто рекурсивную шляпу для сравнения деревьев.

у тебя тут escape continuations, не более, т.е. эксепшны

Но как из одной рекурсии получать соответствующие элементы из второй рекурсии?

Зачем это? Просто обходишь:

struct tree {
    tree * left;
    tree * right;
    int data;
};

bool tree_cmp(const tree * t1, const tree * t2)
{
    if (!t1 || !t2) return t1 == t2;
    if (t1->data != t2->data) return false;
    return tree_cmp(t1->left, t2->left)
        && tree_cmp(t1->right, t2->right);
}

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

-module(tree).

-export([eq1/2, eq2/3]).


eq1({Left, Right}, {Left, Right}) ->
  eq1(Left, Left),
  eq1(Right, Right);
eq1(Value, Value) -> equal;
eq1(_M, _N) -> throw (not_equal).

eq2({L1, R1}, {L2, R2}, Comp) ->
  case {Comp(L1, L2), Comp(R1, R2)} of
    {true, true} ->
      eq2(L1, L2, Comp),
      eq2(R1, R2, Comp);
    _ ->
      throw (not_equal)
  end;
eq2(Value1, Value2, Comp) ->
  case Comp(Value1, Value2) of
    true -> equal;
    _ -> throw (not_equal)
  end.

Если я правильно понял твою задачу то вот. eq2 от eq1 отличается наличием ф-ей сравнения. Ну и деревья должны быть сбалансированы, в смысле одинаковую структуру иметь. Но я подозреваю, что я что-то не понял, потому-что слишком просто же вроде.

Ну и как сделать stream из walk-tree?

В лекции же пример есть.

Потому что по описанию из первого поста задача решается полностью заменой begin на and

(define (walk-tree fn tree)
  (if (cons? tree)
      (and
        (walk-tree fn (car tree))
        (walk-tree fn (cdr tree)))
      (fn tree)))
(define (compare-trees tree1 tree2)
  (walk-tree {что написать здесь чтобы сравнивать с tree2?} tree1)

yield from iwalk(tree.left)

Продолжения на питоне симпатичные. Синтаксис проще и для большинства практических применений достаточны в таком виде.

у тебя тут escape continuations, не более, т.е. эксепшны

(define (yield)
       (call/cc
        (lambda (k)
          (set! caller k)
          (yield-cont))))
...
(define (yield-cont)
       (walk-tree proc1 tree1)
       (caller #f))

Сделай аналогичный caller на эксепшенах.

Но я подозреваю, что я что-то не понял, потому-что слишком просто же вроде.

Слишком просто, потому что в задаче неявно подразумевалось требование отделить функцию обхода от функции сравнения. Но так как неявно, то и вопросов нет. То есть должно быть что-то вроде

eq1(Value, Value) -> equal;
eq1(Tree1, Tree2) ->
  case {isTree(Tree1), isTree(Tree2)} of
    {true, true} => eq1(Val(Tree1), Val(Tree2)),
                    eq1(Next(Tree1), Next(Tree2));
    _ -> throw (not_equal)
  end.

Надо придумать функцию Next для дерева. Впрочем, для цели задачи возможно проще делать отдельный алгоритм для каждого типа, а не изобретать универсальный. Так что задача снимается.

Ничего, очевидно. У тебя walk-tree неправильный - ты же два дерева обходишь, вот два и принимай. Или надо кроме fn принимать еще g:

(define (walk-tree g fn tree)
  (if (cons? tree)
      (and
        (walk-tree g (g fn) (car tree))
        (walk-tree g (g fn) (cdr tree)))
      (fn tree)))

У тебя walk-tree неправильный - ты же два дерева обходишь, вот два и принимай.

Я уже в предыдущем сообщении ответил. При формулировке задачи неявно ставил ограничения но не описывал.

Или надо кроме fn принимать еще g

А это как спасёт? В смысле, что передать в g и fn для обхода по двум деревьям?

Это библиотека из комплекта quicklisp:

http://quickdocs.org/generic-sequences/api

Да элементарно обходится дерево. Действительно, получается что-то среднее между итератором .NET и ячейкой cons из лиспа. Просто думай о enum-cons как о чем-то близком к функции cons. Только первая сущность - макрос.

Там создается аналог ячейки cons, только вместо ячейки cdr внутри находится функция (ленивость, задержка и т.п.). Подобно итераторам, эта функция перевычисляется при обходе. Но если очень хочется, то можно и мемоизировать с помощью готовой библиотечной функции, и тогда будет то, что называют потоком (как в clojure, например).

З.Ы. ну и этот автокорректор сафари!