Anonymous Recursion

[Dallin Dahl]

I'm trying to implement a generic binary tree in shen.  My initial thought, coming from Standard ML was to store the comparison predicate with the tree, and then on the relevant functions load it and then call a recursive internal helper that closes over the order predicate.  It seems like the only way to do something like this is with the Y combinator currently?  Is there no support for recursion at anything but the top level?  The other approach is to define macros to compile the closures away, enabling top-level recursion.

It's also possible that this is intentionally the case, and there's a better way to do this.

Thanks!

--Dallin

[dr.mt...@gmail.com]

The best way to do it is to make the comparator non-recursive.

The tree walking operation is invariant wrt the tree - its uses the 

comparator when it needs to decide where to go so the walker is 

a higher-order function.

M.    

[Dallin Dahl]

I should have included an example.  My first instinct, coming from Standard ML, was the following:

(define tree LE -> (@v LE [] <>))

(define find (@v LE T <>) X -> (let loop
    (/. (@v Y [L | R]) ->
      (cases (and (LE X Y) (LE Y X)) Y
        (LE X Y) (loop L)
        (LE Y X) (loop R))
    [] -> (simple-error "not found"))
  (loop T)))

I recognize that we can't actually pattern match in lambdas, and that can be worked around with cases, and I could probably have made the cases that are there side conditions if I'm assuming uniform pattern matching, but the problem is loop can't reference itself and close over LE and X at the same time.  Either I hoist loop to the top level to make it recursive, or I close over LE and X, but not both.  Is that an intentional limitation?  No recursive closures?

[Bruno Deferrari]

You would probably have a `(tree-find-by Tree Predicate)` function instead, but for the shape you have defined I guess you would something like this:

(define tree
  LE -> (@v LE [] <>))

(define tree-find-loop-h
  LE _ [] -> (simple-error "not found")
  LE X (@v Y [L | R] <>) -> Y
    where (and (LE X Y) (LE Y X))
  LE X (@v Y [L | R] <>) -> (tree-find-loop-h LE X L)
    where (LE X Y)
  LE X (@v Y [L | R] <>) -> (tree-find-loop-h LE X R)
    where (LE Y X)
  _ _ _ -> (simple-error "not found"))

(define tree-find
  (@v LE T <>) X -> (tree-find-loop-h LE X T))

(let Tree (@v (fn <=)
              (@v 2
                  [(@v 1 [[] | []] <>) | (@v 3 [[] | []] <>)]
                  <>)
              <>)
  (tree-find Tree 3))

\\ => 3

--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.
To view this discussion, visit https://groups.google.com/d/msgid/qilang/b0c74465-a0e2-4056-80d3-59c39d84b74dn%40googlegroups.com.

--

BD

[dr.mt...@gmail.com]

Here is a typed solution.  Not to spoil your fun; it is an attachment.

M.

[nha...@gmail.com]

Shen needs a top level name for recursion, one way or another. Unless you use the various fix point combinators. 

I find myself often parameterizing the recursion operation, since this allows you to match, rewrite, and compose things easier.