在标准 ML 中压缩和解压缩列表

Question

如何创建一个函数来将两个列表压缩和解压缩为标准 ML 中的元组列表？

示例：

unzip [[1,4],[2,5],[3,6]] -> [1,2,3] [4,5,6]

zip [1,2,3] [0,2,4] -> [[1,0],[2,2],[3,4]]

Answer 1

我发现我做错了什么。这是代码：

fun zip nil nil = nil
  | zip nil l = l
  | zip l nil = l
  | zip (h::t) (k::l) = [h,k]::(zip t l)
fun mapcan(f,nil) = nil | mapcan(f,h::t) = (f h)@(mapcan(f,t))
fun unzip (l) = if (l = nil) then nil else [(map head l),(mapcan tail l)]

解压缩稍微困难一些。我们需要映射函数 select 压缩列表上双元素列表的第一个和第二个元素。由于示例在某种程度上未指定问题，因此我们会将较长列表的其余部分放入第一个列表中。为了避免较短列表的空尾出现问题，我们使用附加尾列表的 mapcan 函数。

Answer 2

使用head和tail通常不是一个好主意，而是使用模式匹配。您可以按如下方式更优雅地编码解压缩：

fun unzip l = 
  case l
    of nil => (nil, nil)
     | (a,b)::tl => 
        let val (l1, l2) = unzip tl
        in (a::l1, b::l2) end

另外，作为上述评论者之一，zip 和 unzip 通常适用于列表对和列表对。

Answer 3

完全不需要let语句引入的词法范围。通过定义投影函数，实际上可以获得更加简洁和优雅的表示：

fun fst p =
   case p of 
      (x,_) => x

fun snd p =
   case p of
      (_,y) => y

fun unzip lp =
   case lp of 
      [] => ([], [])
    | (x,y) :: lp' => (x :: (fst (unzip lp')), y :: (snd (unzip lp')))

这是有充分理由的，因为来自 SML 编译器的类型推断足够强大，可以从 case 语句和 cons 语句中推断出术语的类型。之前推导了投影函数，类型约束的 CSP 是可解的。 IMO，这 far 比之前使用 let 语句提出的解决方案更优雅。

Compiler

在标准 ML 中压缩和解压缩列表

Zip and unzip lists in Standard ML

sml

smlnj