Re: [xquery-talk] Purely recursive deduplication of sequence?
> > Of course, in the end, I am going to take the one, which has the > best performance. Do you expect it to be the `FLOWR` based or > the `fold-left#3` based, you demonstrated in the follow-up? > Solutions with fold-left are usually the most efficient ones, but it also depends on the XQuery processor you use. Feel free to share your test results. ___ talk@x-query.com http://x-query.com/mailman/listinfo/talk
Re: [xquery-talk] Purely recursive deduplication of sequence?
Am 01.08.2020 um 14:57 schrieb Christian Grün:
Thank you so much for all three examples!
Of course, in the end, I am going to take the one, which has the
best performance. Do you expect it to be the `FLOWR` based or
the `fold-left#3` based, you demonstrated in the follow-up?
Still, I am glad to see this one, since it surprises me, as to how
short this can be! My own ponderings started to get out of hand by
adding more and more code - to no avail. That was when I gave up
and just asked.
> declare function local:distinct-items($items as item()*) as item()* {
> if (empty($items)) then () else (
> head($items),
> local:distinct-items(tail($items)[not(deep-equal(., head($items)))])
> )
> };
--
Goody Bye, Minden jót, Mit freundlichen Grüßen,
Andreas Mixich
___
talk@x-query.com
http://x-query.com/mailman/listinfo/talk
Re: [xquery-talk] Purely recursive deduplication of sequence?
One more solution with fold-left (it’s faster than the recursive approach):
declare function local:distinct-items($items as item()*) as item()* {
fold-left($items, (), function($result, $item) {
$result, $item[empty($result[deep-equal(., $item)])]
})
};
local:distinct-items(('x', (1 to 100) ! 1, 'x'))
On 8/1/20, Christian Grün wrote:
> Hi Andreas,
>
> Try this:
>
> declare function local:distinct-items($items as item()*) as item()* {
> let $h := head($items)
> where exists($h)
> let $t := tail($items)[not(deep-equal(., $h))]
> return ($h, local:distinct-items($t))
> };
>
> If the FLWOR expression is avoided, it may increase the runtime:
>
> declare function local:distinct-items($items as item()*) as item()* {
> if (empty($items)) then () else (
> head($items),
> local:distinct-items(tail($items)[not(deep-equal(., head($items)))])
> )
> };
>
> Hope this helps,
> Christian
>
>
>
> On 8/1/20, Andreas Mixich wrote:
>> 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}
>> ,
>> ,
>> , array {"apples","oranges"}
>> , array {"apples","oranges"}
>> ,
>> , array {"One",5,}
>> , array {3,7,"Hello World!"}
>> , array {3,7,"Hello World!"}
>> , map{'key':'value'}
>> , false()
>> , false()
>> , array {"One","lorem",,2,"Naomi"}
>> , array {"One", "Two", 3}
>> , array {"One","lorem",,2,"Naomi"}
>> , array {,map{'key':'value'},true()}
>> , false()
>> )
>> return local:dedupe-pairs($a3)
>>
>> serializes to:
>>
>> ["One","Two",3]
>> ["One","Two",1]
>> ["One","Two",3]
>>
>> ["apples","oranges"]
>>
>> ["One",5,]
>> [3,7,"Hello World!"]
>> map{"key":"value"}
>> false
>> ["One","lorem",,2,"Naomi"]
>> ["One","Two",3]
>> ["One","lorem",,2,"Naomi"]
>> [,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
>> ___
>> talk@x-query.com
>> http://x-query.com/mailman/listinfo/talk
>
___
talk@x-query.com
http://x-query.com/mailman/listinfo/talk
Re: [xquery-talk] Purely recursive deduplication of sequence?
Hi Andreas,
Try this:
declare function local:distinct-items($items as item()*) as item()* {
let $h := head($items)
where exists($h)
let $t := tail($items)[not(deep-equal(., $h))]
return ($h, local:distinct-items($t))
};
If the FLWOR expression is avoided, it may increase the runtime:
declare function local:distinct-items($items as item()*) as item()* {
if (empty($items)) then () else (
head($items),
local:distinct-items(tail($items)[not(deep-equal(., head($items)))])
)
};
Hope this helps,
Christian
On 8/1/20, Andreas Mixich wrote:
> 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}
> ,
> ,
> , array {"apples","oranges"}
> , array {"apples","oranges"}
> ,
> , array {"One",5,}
> , array {3,7,"Hello World!"}
> , array {3,7,"Hello World!"}
> , map{'key':'value'}
> , false()
> , false()
> , array {"One","lorem",,2,"Naomi"}
> , array {"One", "Two", 3}
> , array {"One","lorem",,2,"Naomi"}
> , array {,map{'key':'value'},true()}
> , false()
> )
> return local:dedupe-pairs($a3)
>
> serializes to:
>
> ["One","Two",3]
> ["One","Two",1]
> ["One","Two",3]
>
> ["apples","oranges"]
>
> ["One",5,]
> [3,7,"Hello World!"]
> map{"key":"value"}
> false
> ["One","lorem",,2,"Naomi"]
> ["One","Two",3]
> ["One","lorem",,2,"Naomi"]
> [,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
> ___
> talk@x-query.com
> http://x-query.com/mailman/listinfo/talk
___
talk@x-query.com
http://x-query.com/mailman/listinfo/talk
