[xquery-talk] Purely recursive deduplication of sequence?

[Andreas Mixich]

Hello,

I wonder, whether it could be possible to deduplicate a sequence by a
purely recursive approach,
without creating state in any form.

What I have, so far, is only capable of removing consecutive dupes, so,
nothing fancy.

  (:~
    Removes all consecutive duplicate items from a sequence, returning
    the deduped sequence.
  
    @param   $items  a sequence, that may contain duplicates
    @return  a sequence, in which all 'pairs' have been 'singled'
    :)
  declare function local:dedupe-pairs($items as item()*) as item()* {
    if (count($items) <= 1)
    then $items
    else if (deep-equal(head($items), head(tail($items))))
         then local:dedupe-pairs(tail($items))
         else (
                head($items)
              , local:dedupe-pairs(tail($items))
              )
  };

  (: following sequence has 19 items :)
  let $a3 := (
               array {"One", "Two", 3}
             , array {"One", "Two", 1}
             , array {"One", "Two", 3}
             , <xml></xml>
             , <xml></xml>
             , array {"apples","oranges"}
             , array {"apples","oranges"}
             , <xml></xml>
             , array {"One",5,<xml></xml>}
             , array {3,7,"Hello World!"}
             , array {3,7,"Hello World!"}
             , map{'key':'value'}
             , false()
             , false()
             , array {"One","lorem",<xml></xml>,2,"Naomi"}
             , array {"One", "Two", 3}
             , array {"One","lorem",<xml></xml>,2,"Naomi"}
             , array {<xml></xml>,map{'key':'value'},true()}
             , false()
             )
  return local:dedupe-pairs($a3)

serializes to:

  ["One","Two",3]
  ["One","Two",1]
  ["One","Two",3]
  <xml/>
  ["apples","oranges"]
  <xml/>
  ["One",5,<xml/>]
  [3,7,"Hello World!"]
  map{"key":"value"}
  false
  ["One","lorem",<xml/>,2,"Naomi"]
  ["One","Two",3]
  ["One","lorem",<xml/>,2,"Naomi"]
  [<xml/>,map{"key":"value"},true()]
  false

However, this is not what I want. I want to understand, whether a
function would be possible, that completely dedupes given sequence,
like `fn:distinct-values#1`, however, for any kind of item, not just
atomic ones:

  `local:distinct-items($items as item()*) as item()*`

It should no use state in any form (typically creating and revolving
a second list or sending a flag throughout recursion).

Also, I do not want to use any manipulative functions (like fn:remove#2)
and, ideally, no `FOR..IN..` construct.

The deduped list would be purely the result of the recursive walk through
the list, grown organically, so to say.

Only, I can not come up with such a thing. Is there a way to do it?

Thank you.

-- 
Goody Bye, Minden jót, Mit freundlichen Grüßen,
Andreas Mixich