将列表分成等价类 [英] Partition a list into equivalence classes

问题描述

我试图在SML中编写一个函数，当它给出一个通用元素列表时，将它的元素重新排列成等价的类并返回这些类的列表（类型为列表列表）。这些类的顺序与原始列表中的顺序相同
给定的函数定义了元素的等价性，如果元素相等或否则返回true
我似乎无法控制解决方案。

  fun sample xy = x = y 
  

所需类型： fn：（''a - >''a - > bool） - >''列表 - >''列表列表

非常感谢您的帮助。

帮助功能无法正常工作，我只想要处理它是看给定的元素是否属于任何类，并将其放入内部或创建一个包含它的新子表。

  fun srt listoflists func new = 
 case listoflists of [] => [[]] 
 | a :: b =>如果func（new，hd a）= true then（new :: a）:: b 
 else if func（new，hd a）= false then：:( srt b func new）else [new]： ：a :: b 
  

示例函数检查两个元素除以11后的等价性。

测试并非全部正常，它不会将17添加到新类中。

  srt [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]]等式7; 
 val it = [[7,7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]]：int list list 
 -  srt [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]]等式5; 
 val it = [[7,7,7]，[5,5,5,5]，[11,11,11]，[13,13,13]]：int list list 
 -  srt [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]]等式11; 
 val it = [[7,7,7]，[5,5,5]，[11,11,11,11]，[13,13,13]]：int list list 
 -  srt [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]]等式13; 
 val it = [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13,13]]：int list list 
 -  srt [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]]等式17; 
 val it = [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]，[]]：int list list 
  -  srt [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]，[111,111,111]]公式111; 
 val it = [[7,7,7]，[5,5,5]，[11,11,11]，[13,13,13]，[111,111,111,111]] 
  

如何纠正这个问题，并且一旦这个辅助函数有效，如何将它精确地整合到所需的主函数中。

非常感谢。

解决方案

接近，但有几个问题

<1>基本情况是应该添加新>，你应该返回值 [[新]] 而不是 [[]]

2）你的问题描述表明 func 是类型''a - > ''a - > bool ，但是你的代码 srt 似乎假设它是（''a *''a）类型的 - >布尔。而不是像 func（new，hd a）这样的子表达式，您需要 func new（hd a）（注意圆括号的位置）。

$ b <3>如果 func 返回一个 bool 那么比较输出到 true 是不必要的冗长的，而不是 if func new（hd a）= true然后... 只要有 if func new（hd a）then ...

<4>由于您要添加 [new] 在基础情况下，你的第二个子句是不必要的冗长的。我没有理由有任何嵌套 if 表达式。

做作业，我不想多说了。一旦你得到帮助程序正常工作，它应该是相当直接的使用它（在递归情况下）的整体功能。请注意，您可以使用（a @ [new]）:: b 而不是（new :: a）:: b 如果你想避免在最终的返回值中包含 rev 的最终映射。 @ 比 :: （它是 O（n）而不是 O（1）），但对于小例子来说，它并不重要，甚至可能稍微好一些，因为它可以避免最后一步逆转列表。

I am trying to write a function in SML which when given a list of general elements, reorders its elements into equivalent classes and returns a list of these classes (type "a list list). Leave the elements in the classes in the same order as in the original list. A given function defines the equivalence of the elements and it returns true if the elements are equivalent or false otherwise. I cannot seem to get a grip on the solution.

fun sample x y = x = y

Required type: fn : (''a -> ''a -> bool) -> ''a list -> ''a list list

Thank you very much for the help.

The helper function does not work correctly, all I want to do with it is see if a given element belongs to any of the classes and put it accordingly inside or create a new sublist which contains it.

fun srt listoflists func new = 
        case listoflists of [] => [[]]
         |  a::b => if func (new, hd a) = true then (new::a)::b
                    else if func (new, hd a) = false then a::(srt b func new) else [new]::a::b

The sample functions checks equivalence of two elements when divided by 11.

Tests are not all working, it is not adding 17 into a new class.

 srt [[7,7,7],[5,5,5],[11,11,11],[13,13,13]] eq 7;
val it = [[7,7,7,7],[5,5,5],[11,11,11],[13,13,13]] : int list list
- srt [[7,7,7],[5,5,5],[11,11,11],[13,13,13]] eq 5;
val it = [[7,7,7],[5,5,5,5],[11,11,11],[13,13,13]] : int list list
- srt [[7,7,7],[5,5,5],[11,11,11],[13,13,13]] eq 11;
val it = [[7,7,7],[5,5,5],[11,11,11,11],[13,13,13]] : int list list
- srt [[7,7,7],[5,5,5],[11,11,11],[13,13,13]] eq 13;
val it = [[7,7,7],[5,5,5],[11,11,11],[13,13,13,13]] : int list list
- srt [[7,7,7],[5,5,5],[11,11,11],[13,13,13]] eq 17;
val it = [[7,7,7],[5,5,5],[11,11,11],[13,13,13],[]] : int list list
- srt [[7,7,7],[5,5,5],[11,11,11],[13,13,13],[111,111,111]] eq 111;
val it = [[7,7,7],[5,5,5],[11,11,11],[13,13,13],[111,111,111,111]]

How to correct this and also once this helper function works, how to encorporate it exactly into the main function that is required.

Thank you very much.

解决方案

Your example code seems like you are getting close, but has several issues

1) The basis cases is where new should be added, so in that case you should return the value [[new]] rather than [[]]

2) Your problem description suggests that func be of type ''a -> ''a -> bool but your code for srt seems to be assuming it is of type (''a * ''a) -> bool. Rather than subexpressions like func (new, hd a) you need func new (hd a) (note the parentheses location).

3) if func returns a bool then comparing the output to true is needlessly verbose, instead of if func new (hd a) = true then ... simply have if func new (hd a) then ...

4) Since you are adding [new] in the basis cases, your second clause is needlessly verbose. I see no reason to have any nested if expressions.

Since this seems to be homework, I don't want to say much more. Once you get the helper working correctly it should be fairly straightforward to use it (in the recursive case) of the overall function. Note that you could use (a @ [new])::b rather than (new::a)::b if you want to avoid the need for a final mapping of rev across the final return value. @ is more expensive than :: (it is O(n) rather than O(1)), but for small examples it really doesn't matter and could even be slightly better since it would avoid the final step of reversing the lists.

这篇关于将列表分成等价类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！