Hi Radoslav,
On Fri, 12 Mar 2010, Radoslav Dorcik wrote:
At Thu, 11 Mar 2010 08:06:52 +0000,
Hi Ganesh,
Thanks for review comments. I'll try to re-think existing bi-sect
algorithm. Unforunatelly it will take time :)
I think the algorithm is fine, actually :-) It's just the data structure I
think is a bit over-complicated.
Appart the realization of the patch tree, the algorithm defined is
based on lazy binary tree. Each node represents state within history
of repository. The state here is the "list of applied patches".
Than there is traversing action which moves to given state and execute
test. The outcome of the test defines the next move within binary
tree:
1. If the test == OK than apply patches (move towards head)
2. If the test == ERROR than unpull patches (move towards first patch ever)
Nothing new here, but what is interesting:
1. The state is temporary repository on file system with some set
of patches applied. Here is unpure nature hidden.
2. Move operation may be either applying or unpulling the patches.
3. Node within tree have information about the move (list of patches),
not about the state on filesystem.
Do you like above approach in general or there is new clever idea ?
I think that's fine.
See my (probably stupid :)) questions inline related to your comments:
Ganesh Sittampalam wrote:
Ganesh Sittampalam <[email protected]> added the comment:
I'm still not very happy with the PatchTree type. Why does it actually
need to have both FL and RL pieces?
I would say that the type of the patch lists defines what to do with
them - if they are for moving forward within history (apply) or back
to big bang (unpull them). This type we needed because the moving
operation is done within child of the parent. If we do the
apply/unpull on the parent, we can use single type (eg. FL). I'll
check it.
I'm not quite sure I follow what you mean here, but my argument is that
you should be able to tell what to do just by which way you move in the
tree. Also, adding witnesses should help here as it should be impossible
to apply when you should have unapplied or vice versa.
Also there's an invariant on the
representation which could be expressed in the constructor - either the
list of patches is of length 1 and the list of child trees is of length
0, or the list is of length >1 and the list of child trees is of length 2.
Also, why store a copy of the list of patches as well as the tree? You
can traverse either in the same amount of time, modulo a small and
almost certainly irrelevant constant factor.
Why not something like
data PatchTree p = Leaf p | Fork (PatchTree p) (PatchTree p)
Do you mean here with the "p" the "patch" or the "FL/RL" ?
p is the patch type.
If the "Fork" is the place where the decision need to be done, question
here is what is the "move" operation afer the test upon current
"state" ? In original implementation the "move" is defined by the list
(RL or LF) of the patches within the node of the child.
Here, the move would be defined by traversing the entirety of
either the left branch or the right branch in the right order, and
applying or unapplying the patches as appropriate.
Whan is than meaning of the "Leaf p" ?
Is it "first patch which breaks the test" ?
Leaf p replaces FLNode (p :>: NilFL) [] and RLNode (p :<: NilFL) [] in
your code. So yes, if you reach it during the search, it is the patch that
is found to break the test.
Hope this helps. Will you be at the hackathon? If so perhaps we should
discuss further then if necessary, and I can also try to explain witnesses
then.
Cheers,
Ganesh
_______________________________________________
darcs-users mailing list
[email protected]
http://lists.osuosl.org/mailman/listinfo/darcs-users
