(.module:
  [lux #*
   [abstract
    [functor (#+ Functor)]
    [monad (#+ Monad do)]
    [equivalence (#+ Equivalence)]
    [fold (#+ Fold)]]
   [control
    ["<>" parser
     ["<c>" code (#+ Parser)]]]
   [data
    [collection
     ["." list ("#@." monad fold)]]]
   [macro
    [syntax (#+ syntax:)]
    ["." code]]])

(type: #export (Tree a)
  {#value a
   #children (List (Tree a))})

(def: #export (flatten tree)
  (All [a] (-> (Tree a) (List a)))
  (#.Cons (get@ #value tree)
          (list@join (list@map flatten (get@ #children tree)))))

(def: #export (leaf value)
  (All [a] (-> a (Tree a)))
  {#value value
   #children (list)})

(def: #export (branch value children)
  (All [a] (-> a (List (Tree a)) (Tree a)))
  {#value value
   #children children})

(type: #rec Tree-Code
  [Code (List Tree-Code)])

(def: tree^
  (Parser Tree-Code)
  (|> (|>> <>.some <c>.record (<>.and <c>.any))
      <>.rec
      <>.some
      <c>.record
      (<>.and <c>.any)
      <c>.tuple))

(syntax: #export (tree {root tree^})
  {#.doc (doc "Tree literals."
              (tree Int [+10 {+20 {}
                              +30 {}
                              +40 {}}]))}
  (wrap (list (` (~ (loop [[value children] root]
                      (` {#value (~ value)
                          #children (list (~+ (list@map recur children)))})))))))

(structure: #export (equivalence Equivalence<a>)
  (All [a] (-> (Equivalence a) (Equivalence (Tree a))))
  
  (def: (= tx ty)
    (and (:: Equivalence<a> = (get@ #value tx) (get@ #value ty))
         (:: (list.equivalence (equivalence Equivalence<a>)) = (get@ #children tx) (get@ #children ty)))))

(structure: #export functor
  (Functor Tree)
  
  (def: (map f fa)
    {#value (f (get@ #value fa))
     #children (list@map (map f)
                         (get@ #children fa))}))

(structure: #export fold
  (Fold Tree)
  
  (def: (fold f init tree)
    (list@fold (function (_ tree' init') (fold f init' tree'))
               (f (get@ #value tree)
                  init)
               (get@ #children tree))))