3 ms·

This is about as far as I got with this... "While it solves the problem of methods, and the mutation problem, it has a serious bug. We can’t have None as an el

This is about as far as I got with this... "While it solves the problem of methods, and the mutation problem, it has a serious bug. We can’t have None as an element in the tree!" Uhm... what?! Why not? You check that your left and right are None and if they are it is a leaf. And if they are not it is not. What your data value is doesn't matter and you can have as many None values in the tree as you like. Your tree doesn't need leaves to define where it ends, it ends when there are no more branches.

oisdk 7y ago
What about the singleton tree with just None in it? As in, what's the difference between `node(None, leaf(), leaf())` and `leaf()`? Or the following: x / \ / \ / \ y None / \ / \ / \ / \ Leaf Leaf Leaf Leaf
- MadWombat 7y ago
  This x / \ / \ / \ y None / \ / \ / \ / \ Leaf Leaf Leaf Leaf Looks like this. x / \ / \ / \ y None There is no reason to explicitly define leafs
  - oisdk 7y ago
    But then wouldn’t the right node with None in it be the same as a leaf? Could you specify what you mean in code maybe? If you don't explicitly define leaves than how can you represent the empty tree?
    - MadWombat 7y ago
      here, as I said, there is no need to represent an empty tree https://gist.github.com/MadWombat/798c6d993a7d2ac4ac74d6624a9a56b4 https://gist.github.com/MadWombat/798c6d993a7d2ac4ac74d6624a...
      - oisdk 7y ago
        So you just throw an error if you try and sort the empty list? Anyway, I'm pretty sure what you've said here was addressed in the article. The version you've presented here is exactly the first alternative I showed, which isn't as good as a version written with ADTs because you can't represent an empty tree.
        MadWombat 7y ago
        Doesn't have to throw an error, could just return an empty list, doesn't matter. All I am saying is that the problem the article describes, where lack of algebraic data types in python makes it impossible to describe the tree structure doesn't exist. There is no need to explicitly represent an empty tree. It is enough to know where your tree ends. Yes, it is more elegant with the ADTs, but it is not impossible without them. Also, if I really wanted to implement Leaf type, I would probably do it via __new__ and a bit of metaprogramming.

oisdk 7y ago

What about the singleton tree with just None in it? As in, what's the difference between `node(None, leaf(), leaf())` and `leaf()`? Or the following: x / \ / \ / \ y None / \ / \ / \ / \ Leaf Leaf Leaf Leaf

MadWombat 7y ago
This x / \ / \ / \ y None / \ / \ / \ / \ Leaf Leaf Leaf Leaf Looks like this. x / \ / \ / \ y None There is no reason to explicitly define leafs
- oisdk 7y ago
  But then wouldn’t the right node with None in it be the same as a leaf? Could you specify what you mean in code maybe? If you don't explicitly define leaves than how can you represent the empty tree?
  - MadWombat 7y ago
    here, as I said, there is no need to represent an empty tree https://gist.github.com/MadWombat/798c6d993a7d2ac4ac74d6624a9a56b4 https://gist.github.com/MadWombat/798c6d993a7d2ac4ac74d6624a...
    - oisdk 7y ago
      So you just throw an error if you try and sort the empty list? Anyway, I'm pretty sure what you've said here was addressed in the article. The version you've presented here is exactly the first alternative I showed, which isn't as good as a version written with ADTs because you can't represent an empty tree.
      - MadWombat 7y ago
        Doesn't have to throw an error, could just return an empty list, doesn't matter. All I am saying is that the problem the article describes, where lack of algebraic data types in python makes it impossible to describe the tree structure doesn't exist. There is no need to explicitly represent an empty tree. It is enough to know where your tree ends. Yes, it is more elegant with the ADTs, but it is not impossible without them. Also, if I really wanted to implement Leaf type, I would probably do it via __new__ and a bit of metaprogramming.