Node
                       /     \
                    Node      (Leaf 3)
                  /      \
              (Leaf 1)   (Leaf 2)

Expression(R) does not just have ONE representation, but the
representation depends on the parameter R.

As you can see from the nesting of this line
https://github.com/hemmecke/fricas-svn/blob/master/src/algebra/expr.s...
,,, in case R is Integer, FriCAS will use Fraction(MP) where
   MP  ==> SparseMultivariatePolynomial(R, K)
   K   ==> Kernel %

Looks like the documentation is not lying. It's "Kernel over Expression"
(% here stands for Expression(R)).

Then look into
https://github.com/hemmecke/fricas-svn/blob/master/src/algebra/kl.spa...
to find out what Kernel(S) can do with the parameter S.
It's only
     argument: % -> List S
     kernel  : (OP, List S, N) -> %
that are important.

So unless you construct an infinite kernel that refers from one of its
arguments back to itself (which is impossible without tricks, since the
arguments must be existing before you can give them to the "kernel"
function), there must be a base case (basically a symbol or nullary
operator) that does not involve any expression.

So yes, the Expression/Kernel data structures are recursive. But there
is no problem with the actual representation.

For a developer one can consider an Expression as a multivariate
polynomial where the variables might have a quite complicated structure.
But if you go down this complicated structure, you remove one complexity
level after the other.

If you need a concrete example, let us try first something simple.
For example, a  _binary search tree_.
Of course, it is for defining as a  _user type_, not of the library.
In Haskell, the user can define it, for example, as

------------------------------------------------------------------------
data STree key value =  
              Empty | Node key value (STree key value) (STree key value)
              deriving (Show)

-- key, value  are type parameters (parameters of a domain in Spad).
-- It is either  Empty  or  a node containing key, value, left subtree,
--                                                        right subtree.
-- `deriving (Show)'  means the default definition for printing of this
--                    data to String.

search :: Ord key => key -> STree key value -> Maybe value

-- `::'  is `:' of Spad,   `='  is  `==', `:=' of  Spad.    
-- `Ord key =>'  corresponds to the condition of
--               key : OrderedSet  in the domain declaration  in Spad.
--               The used  `compare'  operation is of the class Show.
-- `search' is a polymorphic function. And in Spad, it needs, probably,
--          to be exported by the domain STree.

search k tab = case tab
               of
               Empty                             -> Nothing
               Node k' v leftBranch rightBranch ->
                                    case compare k k'
                                    of
                                    EQ -> Just v
                                    LT -> search k leftBranch
                                    _  -> search k rightBranch

main = putStr (concat [show tree, "\n\nv = ", show v, "\n"])

       -- Example of usage. Buld some tree for  key = Int, value = Char,
       --                   search the value for 2 in it,  
       --                   print the tree and the found value.  
       where
       tree = Node 1 'a' Empty
                         (Node 2 'b' (Node 3 'c' Empty Empty) Empty)
       v = search 2 tree
------------------------------------------------------------------------

Compiling, running under GHC:

           > ghc --make -O Main  
           > ./Main

           Node 1 'a' Empty (Node 2 'b' (Node 3 'c' Empty Empty) Empty)

           v = Just 'b'

What is the Spad program for this?
This is not a flame war. Because
1) I respect Axiom, and even try to use it in the interface project,
2) you asked for an example,
3) if the Spad code occurs considerably more complex, this would not
   mean too much, for example, a) Haskell has not dynamic types, one can
               not program parsing a domain in Haskell as I did in Spad,
   b) Spad has considerably more of overloading,
4) if the Spad code is sufficiently simple, then I could return to my
   ConstructedDomain in Spad and see how can it be improved.

Regards,

------------------------------------------------------------------------
data STree key value =  
              Empty | Node key value (STree key value) (STree key value)
              deriving (Show)

search :: Ord key => key -> STree key value -> Maybe value
search k tab = case tab of
                        Empty                            -> Nothing
                        Node k' v leftBranch rightBranch ->
                                             case compare k k'
                                             of
                                             EQ -> Just v
                                             LT -> search k leftBranch
                                             _  -> search k rightBranch
------------------------------------------------------------------------

and the Spad code is

------------------------------------------------------------------------
)abbrev domain STREE STree
OF ==> OutputForm

STree(Key: OrderedSet, Value: CoercibleTo OF): CoercibleTo OF with

    search: (Key, %) -> Union("failed", Value)
    empty: () -> %
    node: (Key, Value, %, %) -> %
  == add
    Node == Record(key: Key, value: Value, left: %, right: %)
    Rep == Union("empty", Node)
    rep(x:%):Rep == x pretend Rep
    per(x:Rep):% == x pretend %

    empty(): % == per "empty"
    node(k: Key, v: Value, l: %, r: %): % == per [k, v, l, r]

    search(k: Key, t: %): Union("failed", Value) ==

                          rep(t) case "empty" => "failed"
                          n: Node := (rep t)::Node
                          n.key = k => n.value
                          n.key > k => search(k, n.left)
                          search(k, n.right)
-----------------------------------------------------------------------

I remove the implementation for `coerce' because a similar implementation
for `show' must be added to the Haskell program -- if we skip  
`deriving (Show)'.

Thank you for a useful sample of programming.
I am sorry:  it is not "considerably more complex",
it is _a bit more complex_.

As to my subjective opinion, it is considerably more complex, because it
is difficult for me to guess of adding  
                    `node: ...',  `Node == Record ...', `rep' and `per'.

But with CostructedDomain, it was more difficult
(I could show the code).
The necessity of type recursion is joint there with a particular
_tagged union_  to express the domain construction.

Regards,

That you *need*

     empty: () -> %
     node: (Key, Value, %, %) -> %

is clear. In Haskell you would get the constructors for free, in SPAD
you don't, i.e. no guessing.

You could also do without the extra Node type and simply put the RHS of

   Node == Record(...)

directly into the definition of Rep.

This line
    n: Node := (rep t)::Node
is also not necessary, but it makes the code more readable.

    Rep == Record(key: Key, value: Value, left: %, right: %)

and interpreted the NIL pointer as the empty tree, i.e.

    empty(): % == (NIL$Lisp) pretend %

but I wanted to make the program as similar to Haskell as possible.