// E# — a verified example from the E# language corpus (CLR language; .es, not ECMAScript).
// provenance: linked_list_and_tail.es   topic: pointers   status: verified
// hand-authored, idiomatic E# — verified through the E# compiler

namespace Demo

// ═════════════════════════════════════════════════════════════════════════════
// Two flavors of recursion, and a thing E# does that C# can't.
//
//   1. Structural recursion over a heap-linked list. A value `data` can't contain itself
//      by value (that would be infinitely large — a hard error), so the `next` link is a
//      pointer, `*Node`. `new Node { ... }` allocates a node on the heap and yields a
//      `*Node`; `nil` ends the list.
//
//   2. Tail recursion. When a recursive call is the LAST thing a function does
//      (`return f(...)`), E# emits the CLR `tail.` prefix — the frame is REUSED, not
//      stacked — and GUARANTEES it, so an accumulator loop written as recursion runs in
//      constant stack however deep. (Roslyn emits `tail.` only opportunistically and gives
//      C# no language-level control or guarantee, so you can't rely on TCO there; E#, like
//      F#, makes it a guarantee.)
// ═════════════════════════════════════════════════════════════════════════════

// The self-reference is a pointer — `next: Node` would be ES2002 (infinite-size value).
data Node {
    value: int
    next: *Node
}

// Structural recursion: this node's value plus the sum of the rest. NOT a tail call (the
// addition happens after the recursive call returns) — and that's fine for a short list.
func sumList(n: *Node) -> int {
    if n == nil {
        return 0
    }
    return n.value + sumList(n.next)
}

// Tail recursion: the recursive call is in tail position, so it compiles to a guaranteed
// CLR tail call. At large `n` a non-TCO'd version risks a StackOverflow; here it's flat.
func sumTo(n: int, acc: int) -> int {
    if n <= 0 {
        return acc
    }
    return sumTo(n - 1, acc + n)
}

func main() -> int {
    // Build 1 -> 2 -> 3 on the heap, tail first so each node can point at the next.
    let third  = new Node { value: 3, next: nil }
    let second = new Node { value: 2, next: third }
    let first  = new Node { value: 1, next: second }

    return sumList(first) + sumTo(100, 0)   // 6 + 5050 = 5056
}