Same fringe toy problem

1

The "Same Fringe" is a simple and known programming problem:
http://wiki.c2.com/?SameFringeProblem

The problem is:
"two binary trees have the same fringe if they have exactly the same leaves reading from left to right."

Solving that problem in Python is easy:

from itertools import zip_longest

class Leaf:
    def __init__(self, v):
        self.v = v

class Branch:
    def __init__(self, t1, t2):
        self.t1, self.t2 = t1, t2

def tree_values(t):
    if isinstance(t, Leaf):
        yield t.v
    elif isinstance(t, Branch):
        yield from tree_values(t.t1)
        yield from tree_values(t.t2)

def same_fringe(t1, t2):
    return all(v1 == v2 for v1, v2 in zip_longest(tree_values(t1), tree_values(t2)))

def main():
    L, B = Leaf, Branch

    t1 = B(B(L(1), L(2)), L(3))
    t2 = B(L(1), B(L(2), L(3)))
    print(same_fringe(t1, t2))

    t3 = B(L(1), L(2))
    print(same_fringe(t1, t3))

main()

I've tried to write a similar program in Rust Nightly with similar generators (but I think currently in Rust you can't do something like the Python yield from):

#![feature(generator_trait, generators, box_syntax, box_patterns)]

use std::ops::{Generator, GeneratorState};

fn generator_to_iterator<G>(g: G) -> impl Iterator<Item = G::Yield>
where G: Generator<Return = ()> {
    struct It<G>(G);

    impl<G: Generator<Return = ()>> Iterator for It<G> {
        type Item = G::Yield;

        fn next(&mut self) -> Option<Self::Item> {
            unsafe {
                match self.0.resume() {
                    GeneratorState::Yielded(y) => Some(y),
                    GeneratorState::Complete(()) => None,
                }
            }
        }
    }

    It(g)
}

enum Tree { Leaf(u32), Branch(Box<Tree>, Box<Tree>) }

fn tree_values<'a>(t: &'a Tree) -> impl Iterator<Item=u32> + 'a {
    generator_to_iterator(move || {
        match t {
            Tree::Leaf(v) => { yield *v; },
            Tree::Branch(ref t1, ref t2) => {
                for v in tree_values(t1) { yield v; }
                for v in tree_values(t2) { yield v; }
            },
        }
    })
}

fn same_fringe(t1: &Tree, t2: &Tree) -> bool {
    tree_values(t1).eq(tree_values(t2))
}

fn main() {
    use Tree::{Leaf as L, Branch as B};

    let t1 = B(box B(box L(1), box L(2)), box L(3));
    let t2 = B(box L(1), box B(box L(2), box L(3)));
    let t3 = B(box L(1), box L(2));

    println!("{}", same_fringe(&t1, &t2)); // True
    println!("{}", same_fringe(&t1, &t3)); // False
}

But it detects a type cycle error. So do I have to box?

2

Yes, you will need to box, this is because the generator will try to refer to itself (because of the recursive implementation).

This is analogous to

struct A {
    a: A
}

This means that the generator cannot be constructed. Using a box, you can erase the type (by using trait objects) and implement this.

This is analogous to

struct A {
    a: Box<A>
}

Actually any pointer indirection with a static lifetime will work (Arc, Rc, Vec, etc.), but in this case Box is the best choice.

1 Like
3

Solved the problem boxing:

for v in box tree_values(t1) { yield v; }
for v in box tree_values(t2) { yield v; }