Re: PIZZA time again :-)

From: mAsterdam <mAsterdam_at_vrijdag.org>
Date: Fri, 02 Sep 2005 23:40:55 +0200
Message-ID: <4318c6d5$0$11080$e4fe514c@news.xs4all.nl>

VC wrote:
> mAsterdam wrote:

>>vc wrote:
>>>mAsterdam wrote:
[snip]

>>>Since 'merge' is commonly defined for lists with the same ordering, the
>>>function cannot be applied to lists with different orderings,  e.g [a,
>>>b] and [b,a,c] (ordering is defined by an element position in the list)
>>>clearly cannot be merged.
>>
>>That is the merge as used in some sorting algorithms, not a merge
>>in it's own right. But if you feel more comfortable calling the discussed 
>>merge mymerge, truemerge, falsemerge or
>>order_preserving_merge - ok.

>
> That is the merge function as used in functional languages like ML, Haskell
> or Lisp (not pure functional). My response relied on the common usage in
> those languages.
>
> Now, what is "a merge in its own right" ? Unless one defines
> 'merge_in_its_own_right', one cannot answer the question what
> 'merge_in_its_own_right' should do with lists where ordering is defined by
> an element position.

Let's see if we can come closer to a definition by listing desiderata:

merge_in_its_own_right merges a list of lists into a list. It

• should not have assumptions about an intrinsic order of the listed values.
• should preserve the order of the values and fail if it can't.

Should it also respect the order /of/ (as opposed to /in/) the lists?

order_preserving_merge would, I guess - but there are two different orders, and assumption 1 (in the original post) only declares the order /in/ the lists to be of consequence. Also declaring the order /of/ the list of consequence makes order_preserving_merge(+, -) determististic. I suspect that is an advantage - but is it a good enough reason? I don't know. Received on Fri Sep 02 2005 - 16:40:55 CDT