let data = [4; 3; 8; 7; 10; 1; 9; 6; 5; 0; 2]

type Tree<'a> =
    | Node of Tree<'a> * 'a * Tree<'a>
    | Leaf

let rec insert tree element =
    match element, tree with
    | x, Leaf                       -> Node (Leaf, x, Leaf)
    | x, Node (l, y, r) when x <= y -> Node ((insert l x), y, r)
    | x, Node (l, y, r) when x > y  -> Node (l, y, (insert r x))
    | _ -> Leaf

let tree = List.fold insert Leaf data

let rec find goal queue =
    match queue with
    | [] -> None
    | (Leaf, _)::tail -> find goal tail
    | (Node (l, y, r), trace)::tail ->
        if y = goal then
            Some (List.rev (y::trace))
        else
            find goal (tail @ [l, y::trace; r, y::trace])

printfn "%A" (find 5 [tree, []])

app [main] {
    pf: platform "https://github.com/roc-lang/basic-cli/releases/download/0.10.0/vNe6s9hWzoTZtFmNkvEICPErI9ptji_ySjicO6CkucY.tar.br",
}

import pf.Stdout

data = [4, 3, 8, 7, 10, 1, 9, 6, 5, 0, 2]

Tree a : [Node (Tree a, a, Tree a), Leaf]

insert = \tree, element ->
    when (element, tree) is
        (x, Leaf)                     -> Node (Leaf, x, Leaf)
        (x, Node (l, y, r)) if x <= y -> Node ((insert l x), y, r)
        (x, Node (l, y, r)) if x > y  -> Node (l, y, (insert r x))
        _ -> Leaf

boom = List.walk data Leaf insert

find = \goal, queue ->
    when queue is
        [] -> None
        [(Leaf, _), .. as tail] -> find goal tail
        [(Node (l, y, r), trace), .. as tail] ->
            if y == goal then
                Some (List.reverse (List.prepend trace y))
            else
                find goal (List.concat tail [(l, List.prepend trace y), (r, List.prepend trace y)])

main =

    Stdout.line "$(Inspect.toStr (find 5 [boom, []] ))"

TYPE MISMATCH

This list contains elements with different types:

32│      Stdout.line "$(Inspect.toStr (find 5 [boom, []] ))"
                                                     ^^

Its 2nd element is a list of type:

    List *

However, the 1st element has the type:

    [
        Leaf,
        Node (
            a,
            Num *,
            a,
        )c,
    ] as a

Every element in a list must have the same type!

empty : Tree a
empty = []

find : Num a, List (Tree (Num a)) -> [Some (Num a), None]
find = \goal, queue ->
    when queue is
        [] -> None
        [(Leaf, _), .. as tail] -> find goal tail
        [(Node (l, y, r), trace), .. as tail] ->
            if y == goal then
                Some (List.reverse (List.prepend trace y))
            else
                find goal (List.concat tail [(l, List.prepend trace y), (r, List.prepend trace y)])

── TYPE MISMATCH in test.roc ───────────────────────────────────────────────────

This 2nd argument to find has an unexpected type:

26│                  find goal (List.concat tail [(l, List.prepend trace y), (r, List.prepend trace y)])
                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This concat call produces:

    List (
        *,
        List (Num a),
    )b

But find needs its 2nd argument to be:

    List [
        Leaf,
        Node (
            a,
            Num a,
            a,
        )b,
    ] as a

find : a, List (Tree a) -> [Some a, None] where a implements Eq

    Stdout.line "$(Inspect.toStr (find 5 [(boom, [])]))"