recursive predicates

[hanwenguo]

does our languages on hand support recursive predicates?

on a fast web search, this article says the following definition is okay for TypeScript:

interface TreeNode {
    value: number;
    children?: TreeNode[];
    // Recursive reference to the same type
}

function isTreeNode(node: any): node is TreeNode {
    if (typeof node !== 'object' || node === null) {
        return false;
    }
    
    if (typeof node.value !== 'number') {
        return false;
    }

    if (node.children) {
        if (!Array.isArray(node.children)) {
            return false;
        }
        
        // Recursively check each child
        for (const child of node.children) {
            if (!isTreeNode(child)) {
                return false;
            }
        }
    }
    
    return true;
}

// Example Usage
const tree = {
    value: 10,
    children: [
        { value: 5 },
        { value: 15, children: [{ value: 12 }, { value: 18 }] }
    ]
};

console.log(isTreeNode(tree));
// Output: true

[bennn]

Typed Racket edition:

#lang typed/racket

(define-type TreeNode (Pairof Number (Listof TreeNode)))

(: IsTreeNode? (-> Any Any : TreeNode))
(define (IsTreeNode? node)
  (if (not (pair? node))
    #f
    (if (not (number? (car node)))
      #f
      (if (not (list? (cdr node)))
        #f
        (and (andmap IsTreeNode? (cdr node)) #t)))))

Error messages for bad versions:

;; --- if 1st #f is #t (same error if 2nd #f changes to #t)
foo.rkt:8:4: Type Checker: type mismatch;
 mismatch in proposition
  expected: ((: node TreeNode) | (! node TreeNode))
  given: (Top | Bot)
  in: #t

;; --- if number? is boolean? instead
foo.rkt:10:6: Type Checker: type mismatch;
 mismatch in proposition
  expected: ((: node TreeNode) | (! node TreeNode))
  given: (Bot | Top)
  in: #f