我正在尝试用 SML 编写一个可以切片列表的函数。
Slice x y ls
前任。Slice 1 3 [0,1,2,3,4]和输出[1,2,3]
这就是我必须开始的
fun slice(aList, start, stop) = nil;
fun slice(nil, x, y) = []
| slice(ls, x, y) =
在 SML 中编写一个切片函数，其功能类似于 Python 列表切片运算符。
例如，slice ([11, 22, 3, 14, 5, 6], 1, 4)返回列表[22, 3, 14]
返回索引开始包含和停止之间的列表切片。假设列表的第一个元素位于索引0处。
谢谢！我感谢您的帮助！
基本解决方案
你怎么知道你目前在什么指数上？
您必须将该信息传递到函数中。让我们称其为"当前"的cur。
对空列表进行切片将返回一个空列表。切片非空列表应查看列表中的第一个元素和当前索引，如果当前索引落入start和stop提供的范围，则通过将其附加到在列表的其余部分运行相同函数的结果中，将其添加到输出中。
fun slice([], start, stop, cur) = []
| slice(x::xs, start, stop, cur) =
if cur >= start andalso cur <= stop then
x :: slice(xs, start, stop, cur + 1)
else
slice(xs, start, stop, cur + 1)
考虑一下当我们评估slice([1, 3, 8, 2, 9, 10, 47], 2, 4, 0)时会发生什么：
slice([1, 3, 8, 2, 9, 10, 47], 2, 4, 0)
slice([3, 8, 2, 9, 10, 47], 2, 4, 1)
slice([8, 2, 9, 10, 47], 2, 4, 2)
8 :: slice([2, 9, 10, 47], 2, 4, 3)
8 :: 2 :: slice([9, 10, 47], 2, 4, 4)
8 :: 2 :: 9 :: slice([10, 47], 2, 4, 5)
8 :: 2 :: 9 :: slice([47], 2, 4, 6)
8 :: 2 :: 9 :: slice([47], 2, 4, 6)
8 :: 2 :: 9 :: slice([], 2, 4, 7)
8 :: 2 :: 9 :: []
[8, 2, 9]
隐藏丑陋
这工作得很好，但是看到传递给函数的当前0索引是丑陋的。让我们用本地帮助程序函数隐藏它。
fun slice(lst, start, stop) =
let
fun aux([], start, stop, cur) = []
| aux(x::xs, start, stop, cur) =
if cur >= start andalso cur <= stop then
x :: aux(xs, start, stop, cur + 1)
else
aux(xs, start, stop, cur + 1)
in
aux(lst, start, stop, 0)
end
尾部调用优化
这很好，但是我们可以让它成为尾递归的吗？我们可以，但是我们需要一个累加器，我们从一个递归调用传递到下一个构建结果列表。此外，在aux的基本情况下，我们不需要命名start、stop或cur，因为它们与结果无关，因此我们可以改用_。
当我们积累结果时，它将反向建立，因此当我们返回累加器时，我们会反转它。
fun slice(lst, start, stop) =
let
fun aux([], _, _, _, acc) = List.rev(acc)
| aux(x::xs, start, stop, cur, acc) =
if cur >= start andalso cur <= stop then
aux(xs, start, stop, cur + 1, x::acc)
else
aux(xs, start, stop, cur + 1, acc)
in
aux(lst, start, stop, 0, [])
end
缩短递归的
短路现在，这将迭代整个列表。我们可以在cur大于stop时停止并返回累加器。这将节省一些精力。
fun slice(lst, start, stop) =
let
fun aux([], _, _, _, acc) = List.rev(acc)
| aux(x::xs, start, stop, cur, acc) =
if cur > stop then
List.rev(acc)
else if cur >= start andalso cur <= stop then
aux(xs, start, stop, cur + 1, x::acc)
else
aux(xs, start, stop, cur + 1, acc)
in
aux(lst, start, stop, 0, [])
end
使用折叠
这是我们可以应用折叠的另一个地方。List.foldl提供了一个工具，我们可以用来消除我们自己的函数中的递归迭代。
使用foldl我们可以将索引和累加器从一个迭代传递到下一个迭代。每次我们对该信息应用一个函数以对其进行转换以进行下一次迭代时。只有当索引介于start和stop之间时，我们才会将其添加到累加器中。
完成后，我们丢弃索引信息，并留下一个可以反转的结果列表。
fun slice'(lst, start, stop) =
let
val (_, lst') = foldl
(fn (v, (idx, acc)) =>
if idx >= start andalso idx <= stop then
(idx + 1, v::acc)
else
(idx + 1, acc))
(0, [])
lst
in
List.rev(lst')
end;
我们到底在做什么？
在这种情况下，"切片"列表是根据每个元素的索引是否在范围内过滤列表。 因此，让我们定义一些新函数。首先，inRange：
fun inRange(start, stop, x) =
x >= start andalso x <= stop
然后，我们将定义一个函数indexedFilter，该函数采用列表和谓词函数。谓词函数将接受两个参数：一个元素和一个索引。如果谓词返回 true，我们将保留该元素。
定义将按照foldl.
fun indexedFilter(lst, pred) =
let
val (lst', _) =
List.foldl
(fn (x, (acc, idx)) =>
if pred(x, idx) then (x :: acc, idx + 1)
else (acc, idx + 1))
([], 0)
lst
in
List.rev lst'
end
现在slice可以定义为：
fun slice(lst, start, stop) =
indexedFilter(lst, fn (_, idx) => inRange(start, stop, idx))
如果您使用的是 sml/nj，它在List结构上包含一组很好的内置函数，您可以这样做：
fun slice (a,b) xs = List.take (List.drop (xs,a), b-a)
这将匹配python切片运算符的基本(非负索引)功能。