将列表拆分为 2 个奇偶位置列表 - SML？

Question

我需要编写一个函数，该函数接受一个列表并将其拆分为两个列表。第一个列表将把元素保持在奇数位置，第二个列表将元素保持在偶数位置。这是我的尝试，它给了我以下警告：

警告：由于值限制被实例化为伪类型(X1，X2，…)

如何改进？

fun splt (lst: int list) =
let
fun splt2 (lst: int list, count: int, lst1: int list, lst2: int list) =
if null lst
then []
else if (count mod 2 = 0)
then splt2 (tl lst, count+1, hd lst::lst1, lst2)
else splt2 (tl lst, count+1, lst1, hd lst::lst2)
in
splt2 (lst,1,[],[])
end

这是我发现的第二个正确的实现，但我主要感兴趣的是修复第一个！！我想把一个列表分成奇数和偶数元素的元组

fun split [] = ([], [])   
| split [x] = ([x], [])  
| split (x1::x2::xs) = 
let 
val (ys, zs) = split xs
in 
((x1::ys), (x2::zs))
end;

更新：改进只是取代

if null lst then
[] 

这个：

if null lst then
[lst1]@[lst2]

Answer 1

以下是对您的代码的一些反馈：

• 给函数一个合适的名称，比如split或partition。我对这些名称的含义是：拆分(或爆炸)获取一些东西并返回一个子组件列表(例如字符串→char-list)，而分区则根据谓词(例如List.partition)将某个事物的列表一分为二，但它们并不是一成不变的
• 编一些不是lst的变量名，因为这只是类型的缩写——即使有类型，也肯定是多余的。对于泛型方法，很难找到好的名称。许多ML代码使用xs之类的东西来暗示泛型的复数形式

• 去掉类型注释；你会得到一个更容易读取的多态函数：

  fun split input =
  let
  fun split' (xys, count, xs, ys) = ...
  in
  split' (input, 1, [], [])
  end
  

• 但实际上，您在网上找到的版本有一些优点：模式匹配确保在触发函数体之前，您的列表具有正确的形式，从而最大限度地减少运行时错误。函数hd和tl没有。

• 您可以稍微优化案例的顺序；即首先列出最常见的情况。x::xs和y::ys周围的括号是不必要的。此外，为了简洁起见，可以将另外两种情况(一个或零个元素)组合在一起，但这并不重要。

  fun split (x1::x2::xs) = 
  let 
  val (ys, zs) = split xs
  in 
  (x1::ys, x2::zs)
  end
  | split rest = (rest, [])   
  

• 您也可以使用的情况，而不是让结束：

  fun split (x1::x2::xs) =
  (case split xs of
  (ys, zs) => (x1::ys, x2::zs))
  | split rest = (rest, [])
  

• 最后，您可能想要使这个函数尾部递归：

  fun split xys =
  let fun split' (x1::x2::xs, ys, zs) = split' (xs, x1::ys, x2::zs)
  | split' (rest, ys, zs) = (rev (rest @ ys), rev zs)
  in
  split' (xys, [], [])
  end
  

Answer 2

帮助您克服遇到的错误你需要看看你给的函数类型

val splt = fn : int list -> 'a list

问问自己一份"a名单"包含什么？

- val foo = "foo"::(splt[1,2,3,4,5]);
val foo = ["foo"] : string list
- val bar = 52::splt[1,2,3,4,5];
val bar = [52] : int list

它可以容纳任何东西，但编译器不能自己判断。